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 (in query complexity) is possible when the arms and the randomness of the rewards of the arms can be queried in superposition. Here we introduce further bandit models where we only have limited access to the randomness of the rewards, but we can still query the arms in superposition. We show that then the query complexity is the same as for classical algorithms. This generalizes the prior result that no speed-up is possible for unstructured search when the oracle has positive failure probability.

📄 PDF Abstract BibTeX arXiv:2301.08544

Code (0)

등록된 구현이 없습니다.

Tasks

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

Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

2022-05-30 · Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang 외

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon $T$ suffer $\Omega(\sqrt{T})$ regret.…

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

Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Bandits

2026-03-19 · Zhuoyue Chen, Kechao Cai arxiv

Quantum multi-armed bandits (MAB) and stochastic linear bandits (SLB) have recently attracted significant attention, as their quantum counterparts can achieve quadratic speedups over classical MAB and SLB. However, most …

Multi-Armed Bandits

Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities

2025-07-06 · Yuexin Su, Ziyi Yang, Peiyuan Huang, Tongyang Li 외 arxiv

Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon $T$ achieve a problem-independent…

Multi-Armed Bandits

Adapting multi-armed bandits policies to contextual bandits scenarios

2018-11-11 · David Cortes

This work explores adaptations of successful multi-armed bandits policies to the online contextual bandits scenario with binary rewards using binary classification algorithms such as logistic regression as black-box orac…

Binary Classification Classification General Classification Multi-Armed Bandits+2

Regression Oracles and Exploration Strategies for Short-Horizon Multi-Armed Bandits

2021-02-10 · Robert C. Gray, Jichen Zhu, Santiago Ontañón

This paper explores multi-armed bandit (MAB) strategies in very short horizon scenarios, i.e., when the bandit strategy is only allowed very few interactions with the environment. This is an understudied setting in the M…

Multi-Armed Bandits regression