Lower Bounds for Multi-armed Bandit with Non-equivalent Multiple Plays

2015-07-17 · Aleksandr Vorobev, Gleb Gusev

We study the stochastic multi-armed bandit problem with non-equivalent multiple plays where, at each step, an agent chooses not only a set of arms, but also their order, which influences reward distribution. In several problem formulations with different assumptions, we provide lower bounds for regret with standard asymptotics $O(\log{t})$ but novel coefficients and provide optimal algorithms, thus proving that these bounds cannot be improved.

📄 PDF Abstract BibTeX arXiv:1507.04910

Code (0)

등록된 구현이 없습니다.

A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning

2021-06-22 · ICLR 2022 4 · Yunchang Yang, Tianhao Wu, Han Zhong, Evrard Garcelon 외

In this paper, we present a reduction-based framework for conservative bandits and RL, in which our core technique is to calculate the necessary and sufficient budget obtained from running the baseline policy. For lower …

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

Regret Lower Bounds in Multi-agent Multi-armed Bandit

2023-08-15 · Mengfan Xu, Diego Klabjan

Multi-armed Bandit motivates methods with provable upper bounds on regret and also the counterpart lower bounds have been extensively studied in this context. Recently, Multi-agent Multi-armed Bandit has gained significa…

Imprecise Multi-Armed Bandits

2024-05-09 · Vanessa Kosoy

We introduce a novel multi-armed bandit framework, where each arm is associated with a fixed unknown credal set over the space of outcomes (which can be richer than just the reward). The arm-to-credal-set correspondence …

Multi-Armed Bandits

Building Bridges: Viewing Active Learning from the Multi-Armed Bandit Lens

2013-09-26 · Ravi Ganti, Alexander G. Gray

In this paper we propose a multi-armed bandit inspired, pool based active learning algorithm for the problem of binary classification. By carefully constructing an analogy between active learning and multi-armed bandits,…

Active Learning Binary Classification General Classification Multi-Armed Bandits

Tight Lower Bounds for Combinatorial Multi-Armed Bandits

2020-02-13 · Nadav Merlis, Shie Mannor

The Combinatorial Multi-Armed Bandit problem is a sequential decision-making problem in which an agent selects a set of arms on each round, observes feedback for each of these arms and aims to maximize a known reward fun…

Decision Making Multi-Armed Bandits Sequential Decision Making