240 citations · 931 across the 63 of their papers we have counts for
25 papers · 1 filter
Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
Aleksandrs Slivkins, Yunzong Xu, Shiliang Zuo
We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure. We allow arbitrary finite reward structures, while prior work focused on a few s…
Should You Use Your Large Language Model to Explore or Exploit?
Keegan Harris, Aleksandrs Slivkins
We evaluate the ability of the current generation of large language models (LLMs) to help a decision-making agent facing an exploration-exploitation tradeoff. While previous work h…
Can large language models explore in-context?
Akshay Krishnamurthy, Keegan Harris, Dylan J. Foster +2
We investigate the extent to which contemporary Large Language Models (LLMs) can engage in exploration, a core capability in reinforcement learning and decision making. We focus on…
Impact of Decentralized Learning on Player Utilities in Stackelberg Games
Kate Donahue, Nicole Immorlica, Meena Jagadeesan +2
When deployed in the world, a learning agent such as a recommender system or a chatbot often repeatedly interacts with another learning agent (such as a user) over time. In many su…
Incentivized Exploration via Filtered Posterior Sampling
Anand Kalvit, Aleksandrs Slivkins, Yonatan Gur
We study "incentivized exploration" (IE) in social learning problems where the principal (a recommendation algorithm) can leverage information asymmetry to incentivize sequentially…
Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits
Lequn Wang, Akshay Krishnamurthy, Aleksandrs Slivkins
We consider offline policy optimization (OPO) in contextual bandits, where one is given a fixed dataset of logged interactions. While pessimistic regularizers are typically used to…
Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression
Aleksandrs Slivkins, Xingyu Zhou, Karthik Abinav Sankararaman +1
We consider contextual bandits with linear constraints (CBwLC), a variant of contextual bandits in which the algorithm consumes multiple resources subject to linear constraints on…
Incentivizing Combinatorial Bandit Exploration
Xinyan Hu, Dung Daniel Ngo, Aleksandrs Slivkins +1
Consider a bandit algorithm that recommends actions to self-interested users in a recommendation system. The users are free to choose other actions and need to be incentivized to f…
Sayer: Using Implicit Feedback to Optimize System Policies
Mathias Lécuyer, Sang Hoon Kim, Mihir Nanavati +4
We observe that many system policies that make threshold decisions involving a resource (e.g., time, memory, cores) naturally reveal additional, or implicit feedback. For example,…
Exploration and Incentives in Reinforcement Learning
Max Simchowitz, Aleksandrs Slivkins
How do you incentivize self-interested agents to when they prefer to ? We consider complex exploration problems, where each agent faces the sam…
Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
Chara Podimata, Aleksandrs Slivkins
Lipschitz bandits is a prominent version of multi-armed bandits that studies large, structured action spaces such as the interval, where similar actions are guaranteed to h…
Efficient Contextual Bandits with Continuous Actions
Maryam Majzoubi, Chicheng Zhang, Rajan Chari +3
We create a computationally tractable algorithm for contextual bandits with continuous actions having unknown structure. Our reduction-style algorithm composes with most supervised…
Constrained episodic reinforcement learning in concave-convex and knapsack settings
Kianté Brantley, Miroslav Dudik, Thodoris Lykouris +4
We propose an algorithm for tabular episodic reinforcement learning with constraints. We provide a modular analysis with strong theoretical guarantees for settings with concave rew…
Greedy Algorithm almost Dominates in Smoothed Contextual Bandits
Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan +1
Online learning algorithms, widely used to power search and content optimization on the web, must balance exploration and exploitation, potentially sacrificing the experience of cu…
Bandits with Knapsacks beyond the Worst-Case
Karthik Abinav Sankararaman, Aleksandrs Slivkins
Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present thre…
Corruption-robust exploration in episodic reinforcement learning
Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins +1
We initiate the study of multi-stage episodic reinforcement learning under adversarial corruptions in both the rewards and the transition probabilities of the underlying system ext…
Introduction to Multi-Armed Bandits
Aleksandrs Slivkins
Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, co…
The Externalities of Exploration and How Data Diversity Helps Exploitation
Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan +1
Online learning algorithms, widely used to power search and content optimization on the web, must balance exploration and exploitation, potentially sacrificing the experience of cu…
Combinatorial Semi-Bandits with Knapsacks
Karthik Abinav Sankararaman, Aleksandrs Slivkins
We unify two prominent lines of work on multi-armed bandits: bandits with knapsacks (BwK) and combinatorial semi-bandits. The former concerns limited "resources" consumed by the al…
Contextual Dueling Bandits
Miroslav Dudík, Katja Hofmann, Robert E. Schapire +2
We consider the problem of learning to choose actions using contextual information when provided with limited feedback in the form of relative pairwise comparisons. We study this p…
Resourceful Contextual Bandits
Ashwinkumar Badanidiyuru, John Langford, Aleksandrs Slivkins
We study contextual bandits with ancillary constraints on resources, which are common in real-world applications such as choosing ads or dynamic pricing of items. We design the fir…
Dynamic Ad Allocation: Bandits with Budgets
Aleksandrs Slivkins
We consider an application of multi-armed bandits to internet advertising (specifically, to dynamic ad allocation in the pay-per-click model, with uncertainty on the click probabil…
Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem
Ittai Abraham, Omar Alonso, Vasilis Kandylas +1
Very recently crowdsourcing has become the de facto platform for distributing and collecting human computation for a wide range of tasks and applications such as information retrie…
Adapting to the Shifting Intent of Search Queries
Umar Syed, Aleksandrs Slivkins, Nina Mishra
Search engines today present results that are often oblivious to abrupt shifts in intent. For example, the query `independence day' usually refers to a US holiday, but the intent o…