More Like this

1. Can Probabilistic Feedback Drive User Impacts in Online Platforms?

   Dai, Jessica; Flanigan, Bailey; Haghtalab, Nika; Jagadeesan, Meena; Podimata, Chara (May 2024, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:2512-2520, 2024.)

   A common explanation for negative user impacts of content recommender systems is misalignment between the platform’s objective and user welfare. In this work, we show that misalignment in the platform’s objective is not the only potential cause of unintended impacts on users: even when the platform’s objective is fully aligned with user welfare, the platform’s learning algorithm can induce negative downstream impacts on users. The source of these user impacts is that different pieces of content may generate observable user reactions (feedback information) at different rates; these feedback rates may correlate with content properties, such as controversiality or demographic similarity of the creator, that affect the user experience. Since differences in feedback rates can impact how often the learning algorithm engages with different content, the learning algorithm may inadvertently promote content with certain such properties. Using the multi-armed bandit framework with probabilistic feedback, we examine the relationship between feedback rates and a learning algorithm’s engagement with individual arms for different no-regret algorithms. We prove that no-regret algorithms can exhibit a wide range of dependencies: if the feedback rate of an arm increases, some no-regret algorithms engage with the arm more, some no-regret algorithms engage with the arm less, and other no-regret algorithms engage with the arm approximately the same number of times. From a platform design perspective, our results highlight the importance of looking beyond regret when measuring an algorithm’s performance, and assessing the nature of a learning algorithm’s engagement with different types of content as well as their resulting downstream impacts. 

   more » « less
2. More Adaptive Algorithms for Adversarial Bandits.

   Wei, Chen-Yu; Luo, Haipeng (July 2018, Proceedings of Machine Learning Research)

   We develop a novel and generic algorithm for the adversarial multi-armed bandit problem (or more generally the combinatorial semi-bandit problem). When instantiated differently, our algorithm achieves various new data-dependent regret bounds improving previous work. Examples include: 1) a regret bound depending on the variance of only the best arm; 2) a regret bound depending on the first-order path-length of only the best arm; 3) a regret bound depending on the sum of the first-order path-lengths of all arms as well as an important negative term, which together lead to faster convergence rates for some normal form games with partial feedback; 4) a regret bound that simultaneously implies small regret when the best arm has small loss {\it and} logarithmic regret when there exists an arm whose expected loss is always smaller than those of other arms by a fixed gap (e.g. the classic i.i.d. setting). In some cases, such as the last two results, our algorithm is completely parameter-free. The main idea of our algorithm is to apply the optimism and adaptivity techniques to the well-known Online Mirror Descent framework with a special log-barrier regularizer. The challenges are to come up with appropriate optimistic predictions and correction terms in this framework. Some of our results also crucially rely on using a sophisticated increasing learning rate schedule. 

   more » « less
3. Interactive Learning with Pricing for Optimal and Stable Allocations in Markets

   Erginbas, Yigit Efe; Phade, Soham; Ramchandran, Kannan (April 2023, Proceedings of the International Workshop on Artificial Intelligence and Statistics)

   Large-scale online recommendation systems must facilitate the allocation of a limited number of items among competing users while learning their preferences from user feedback. As a principled way of incorporating market constraints and user incentives in the design, we consider our objectives to be two-fold: maximal social welfare with minimal instability. To maximize social welfare, our proposed framework enhances the quality of recommendations by exploring allocations that optimistically maximize the rewards. To minimize instability, a measure of users' incentives to deviate from recommended allocations, the algorithm prices the items based on a scheme derived from the Walrasian equilibria. Though it is known that these equilibria yield stable prices for markets with known user preferences, our approach accounts for the inherent uncertainty in the preferences and further ensures that the users accept their recommendations under offered prices. To the best of our knowledge, our approach is the first to integrate techniques from combinatorial bandits, optimal resource allocation, and collaborative filtering to obtain an algorithm that achieves sub-linear social welfare regret as well as sub-linear instability. Empirical studies on synthetic and real-world data also demonstrate the efficacy of our strategy compared to approaches that do not fully incorporate all these aspects. 

   more » « less
4. Reinforcement Learning Content Generation for Virtual Reality Applications

   Lopez, Christian E; Ashour, Omar M; Tucker, Conrad (August 2019, ASME IDETC-CIE)

   This work presents a Procedural Content Generation (PCG) method based on a Neural Network Reinforcement Learning (RL) approach that generates new environments for Virtual Reality (VR) learning applications. The primary objective of PCG methods is to algorithmically generate new content (e.g., environments, levels) in order to improve user experience. Researchers have started exploring the integration of Machine Learning (ML) algorithms into their PCG methods. These ML approaches help explore the design space and generate new content more efficiently. The capability to provide users with new content has great potential for learning applications. However, these ML algorithms require large datasets to train their generative models. In contrast, RL based methods do not require any training data to be collected a priori since they take advantage of simulation to train their models. Moreover, even though VR has become an emerging technology to engage users, there have been few studies that explore PCG for learning purposes and fewer in the context of VR. Considering these limitations, this work presents a method that generates new VR environments by training an RL in a simulation platform. This PCG method has the potential to maintain users’ engagement over time by presenting them with new environments in VR learning applications. 

   more » « less
5. Learning from a Learning User for Optimal Recommendations

   Yao, Fan; Li, Chuanhao; Nekipelov, Denis; Wang, Hongning; Xu, Haifeng (July 2022, Proceedings of the 39th International Conference on Machine Learning)

   Chaudhuri, Kamalika; Jegelka, Stefanie; Song, Le; Szepesvari, Csaba; Niu, Gang; Sabato, Sivan (Ed.)

   In real-world recommendation problems, especially those with a formidably large item space, users have to gradually learn to estimate the utility of any fresh recommendations from their experience about previously consumed items. This in turn affects their interaction dynamics with the system and can invalidate previous algorithms built on the omniscient user assumption. In this paper, we formalize a model to capture such ”learning users” and design an efficient system-side learning solution, coined Noise-Robust Active Ellipsoid Search (RAES), to confront the challenges brought by the non-stationary feedback from such a learning user. Interestingly, we prove that the regret of RAES deteriorates gracefully as the convergence rate of user learning becomes worse, until reaching linear regret when the user’s learning fails to converge. Experiments on synthetic datasets demonstrate the strength of RAES for such a contemporaneous system-user learning problem. Our study provides a novel perspective on modeling the feedback loop in recommendation problems. 

   more » « less