Query-Reward Tradeoffs in Multi-Armed Bandits

2021-10-12 · Nadav Merlis, Yonathan Efroni, Shie Mannor

We consider a stochastic multi-armed bandit setting where reward must be actively queried for it to be observed. We provide tight lower and upper problem-dependent guarantees on both the regret and the number of queries. Interestingly, we prove that there is a fundamental difference between problems with a unique and multiple optimal arms, unlike in the standard multi-armed bandit problem. We also present a new, simple, UCB-style sampling concept, and show that it naturally adapts to the number of optimal arms and achieves tight regret and querying bounds.

📄 PDF Abstract BibTeX arXiv:2110.05724

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-Armed Bandits

Multi-Armed Bandits and Quantum Channel Oracles

2023-01-20 · Simon Buchholz, Jonas M. Kübler, Bernhard Schölkopf

Multi-armed bandits are one of the theoretical pillars of reinforcement learning. Recently, the investigation of quantum algorithms for multi-armed bandit problems was started, and it was found that a quadratic speed-up …

Multi-Armed Bandits reinforcement-learning Reinforcement Learning (RL)

Balancing Act: Prioritization Strategies for LLM-Designed Restless Bandit Rewards

2024-08-22 · Shresth Verma, Niclas Boehmer, Lingkai Kong, Milind Tambe

LLMs are increasingly used to design reward functions based on human preferences in Reinforcement Learning (RL). We focus on LLM-designed rewards for Restless Multi-Armed Bandits, a framework for allocating limited resou…

Language Modeling Language Modelling Multi-Armed Bandits Reinforcement Learning (RL)

Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits

2023-01-26 · Nikolai Karpov, Qin Zhang

In this paper, we study the collaborative learning model, which concerns the tradeoff between parallelism and communication overhead in multi-agent multi-armed bandits. For regret minimization in multi-armed bandits, we …

Multi-agent Reinforcement Learning Multi-Armed Bandits reinforcement-learning Reinforcement Learning (RL)

Active Reinforcement Learning: Observing Rewards at a Cost

2020-11-13 · David Krueger, Jan Leike, Owain Evans, John Salvatier

Active reinforcement learning (ARL) is a variant on reinforcement learning where the agent does not observe the reward unless it chooses to pay a query cost c > 0. The central question of ARL is how to quantify the long-…

Multi-Armed Bandits reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits

2025-09-18 · Shaoang Li, Jian Li arxiv

Non-stationary multi-armed bandits enable agents to adapt to changing environments by incorporating mechanisms to detect and respond to shifts in reward distributions, making them well-suited for dynamic settings. Howeve…