Latent Bandits Revisited
- URL: http://arxiv.org/abs/2006.08714v1
- Date: Mon, 15 Jun 2020 19:24:02 GMT
- Title: Latent Bandits Revisited
- Authors: Joey Hong and Branislav Kveton and Manzil Zaheer and Yinlam Chow and
Amr Ahmed and Craig Boutilier
- Abstract summary: A latent bandit problem is one in which the learning agent knows the arm reward distributions conditioned on an unknown discrete latent state.
We propose general algorithms for this setting, based on both upper confidence bounds (UCBs) and Thompson sampling.
We provide a unified theoretical analysis of our algorithms, which have lower regret than classic bandit policies when the number of latent states is smaller than actions.
- Score: 55.88616813182679
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A latent bandit problem is one in which the learning agent knows the arm
reward distributions conditioned on an unknown discrete latent state. The
primary goal of the agent is to identify the latent state, after which it can
act optimally. This setting is a natural midpoint between online and offline
learning---complex models can be learned offline with the agent identifying
latent state online---of practical relevance in, say, recommender systems. In
this work, we propose general algorithms for this setting, based on both upper
confidence bounds (UCBs) and Thompson sampling. Our methods are contextual and
aware of model uncertainty and misspecification. We provide a unified
theoretical analysis of our algorithms, which have lower regret than classic
bandit policies when the number of latent states is smaller than actions. A
comprehensive empirical study showcases the advantages of our approach.
Related papers
- PageRank Bandits for Link Prediction [72.61386754332776]
Link prediction is a critical problem in graph learning with broad applications such as recommender systems and knowledge graph completion.
This paper reformulates link prediction as a sequential decision-making process, where each link prediction interaction occurs sequentially.
We propose a novel fusion algorithm, PRB (PageRank Bandits), which is the first to combine contextual bandits with PageRank for collaborative exploitation and exploration.
arXiv Detail & Related papers (2024-11-03T02:39:28Z) - Leveraging Offline Data in Linear Latent Bandits [16.006405951752903]
We show that $textitevery$ exchangeable and coherent stateless decision process is a latent bandit.
We present a principled method to learn this subspace from short offline trajectories with guarantees.
We provide two methods to leverage this subspace online: LOCAL-UCB and ProBALL-UCB.
arXiv Detail & Related papers (2024-05-27T16:23:34Z) - Online learning in bandits with predicted context [8.257280652461159]
We consider the contextual bandit problem where at each time, the agent only has access to a noisy version of the context.
This setting is motivated by a wide range of applications where the true context for decision-making is unobserved.
We propose the first online algorithm in this setting with sublinear regret guarantees under mild conditions.
arXiv Detail & Related papers (2023-07-26T02:33:54Z) - Last Switch Dependent Bandits with Monotone Payoff Functions [8.860629791560198]
We take a step towards understanding the approximability of planning LSD bandits, namely, the (NP-hard) problem of computing an optimal arm-pulling strategy.
In particular, we design the first efficient constant approximation algorithm for the problem and show that, under a natural monotonicity assumption on payoffs, its approximation guarantee almost matches the state-of-the-art.
We develop new tools and insights for this class of problems, including a novel higher-dimensional relaxation and the technique of mirroring the evolution of virtual states.
arXiv Detail & Related papers (2023-06-01T04:38:32Z) - Bandit Social Learning: Exploration under Myopic Behavior [58.75758600464338]
We study social learning dynamics motivated by reviews on online platforms.
Agents collectively follow a simple multi-armed bandit protocol, but each agent acts myopically, without regards to exploration.
We derive stark learning failures for any such behavior, and provide matching positive results.
arXiv Detail & Related papers (2023-02-15T01:57:57Z) - Thompson Sampling with Virtual Helping Agents [0.0]
We address the problem of online sequential decision making, i.e., balancing the trade-off between exploiting current knowledge to maximize immediate performance and exploring the new information to gain long-term benefits.
We propose two algorithms for the multi-armed bandit problem and provide theoretical bounds on the cumulative regret.
arXiv Detail & Related papers (2022-09-16T23:34:44Z) - Non-Stationary Latent Bandits [68.21614490603758]
We propose a practical approach for fast personalization to non-stationary users.
The key idea is to frame this problem as a latent bandit, where prototypical models of user behavior are learned offline and the latent state of the user is inferred online.
We propose Thompson sampling algorithms for regret minimization in non-stationary latent bandits, analyze them, and evaluate them on a real-world dataset.
arXiv Detail & Related papers (2020-12-01T10:31:57Z) - A New Bandit Setting Balancing Information from State Evolution and
Corrupted Context [52.67844649650687]
We propose a new sequential decision-making setting combining key aspects of two established online learning problems with bandit feedback.
The optimal action to play at any given moment is contingent on an underlying changing state which is not directly observable by the agent.
We present an algorithm that uses a referee to dynamically combine the policies of a contextual bandit and a multi-armed bandit.
arXiv Detail & Related papers (2020-11-16T14:35:37Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean.
We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
arXiv Detail & Related papers (2020-03-05T21:29:27Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.