Adaptation to the Range in $K$-Armed Bandits

• URL: http://arxiv.org/abs/2006.03378v3
• Date: Wed, 15 Jun 2022 10:34:03 GMT
• Title: Adaptation to the Range in $K$-Armed Bandits
• Abstract summary: We consider bandit problems with $K$ arms associated with a bounded distribution supported on the range $[m,M]$. A new trade-off between distribution-dependent and distribution-free regret bounds arises, which prevents from simultaneously achieving the typical $ln T$ and $sqrtT$ bounds.
• Score: 1.14219428942199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider stochastic bandit problems with $K$ arms, each associated with a bounded distribution supported on the range $[m,M]$. We do not assume that the range $[m,M]$ is known and show that there is a cost for learning this range. Indeed, a new trade-off between distribution-dependent and distribution-free regret bounds arises, which prevents from simultaneously achieving the typical $\ln T$ and $\sqrt{T}$ bounds. For instance, a $\sqrt{T}$}distribution-free regret bound may only be achieved if the distribution-dependent regret bounds are at least of order $\sqrt{T}$. We exhibit a strategy achieving the rates for regret indicated by the new trade-off.

Related papers

• Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits [13.075031222564535]
  Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs.<n>We study the trade-off between worst-case regret $mathcalR_K,T$ and instability $mathcal S_K,T$, defined as the largest standard deviation of a terminal pull count, for $K$ arms and $T$ rounds.
  arXiv  Detail & Related papers  (2026-08-18T14:38:47Z)
• Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
  We consider a multi-objective bandit problem where, at each round, the agent selects a slate of $k$ arms and observes their $d$-dimensional reward vectors under semi-bandit feedback.<n>We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an $$-approximate hypervolume regret with respect to the best size-$k$ subset achievable in hindsight.<n>We establish a gap-free regret bound $tildeO(dsqrtnkT)$ that holds on every instance, together with a gap
  arXiv  Detail & Related papers  (2026-07-28T21:10:39Z)
• Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning [39.8867004581646]
  We formalize a distributional regret bound as a probabilistic guarantee that holds uniformly over all confidence levels $in (0,1]$.<n>We present a simple UCBVI-style algorithm with exploration bonus $minc_1,k/N, c_2,k/sqrtN$, where $N$ denotes the visit count and $(c_1,k,c_2,k)$ are user-specified parameters.<n>Our bounds achieve optimal trade-offs between expected and distributional regret in both minimax and instance-dependent regimes
  arXiv  Detail & Related papers  (2026-05-06T16:38:30Z)
• Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach [26.085126064745378]
  We study distributed adversarial bandits, where $N$ agents cooperate to minimize the global average loss while observing only their own local losses.<n>We show that the minimax regret for this problem is $tilde(sqrt(-1/2+K/N)T)$, where $T$ is the horizon, $K$ is the number of actions, and $$ is the spectral gap of the communication matrix.
  arXiv  Detail & Related papers  (2026-02-06T05:53:38Z)
• Prior Diffusiveness and Regret in the Linear-Gaussian Bandit [25.66105507730649]
  We prove that Thompson sampling exhibits $tildeO(d sqrtT + d r sqrtmathrmTr(_0))$ Bayesian regret in the linear-Gaussian bandit.<n>We establish these results via a new elliptical potential'' lemma, and also provide a lower bound indicating that the burn-in term is unavoidable.
  arXiv  Detail & Related papers  (2026-01-05T11:30:08Z)
• Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks [16.410227280444285]
  We study the distributed multi-agent multi-armed bandit problem with heterogeneous rewards over random communication graphs.<n>We propose a fully distributed algorithm that integrates the arm elimination strategy with the random gossip algorithm.
  arXiv  Detail & Related papers  (2025-10-26T19:53:52Z)
• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [20.47953854427799]
  We consider a common case of the semi-bandit problem, where the learner exactly selects $m$ arms from the total $d$ arms. We show that FTPL with a Fr'echet perturbation also enjoys the near optimal regret bound $mathcalO(sqrtnmdlog(d))$ in the adversarial setting.
  arXiv  Detail & Related papers  (2025-04-09T22:07:01Z)
• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  Variance-dependent regret bounds for linear contextual bandits, which improve upon the classical $tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$.
  arXiv  Detail & Related papers  (2025-03-15T07:09:36Z)
• Near-optimal Per-Action Regret Bounds for Sleeping Bandits [8.261117235807607]
  We derive near-optimal per-action regret bounds for sleeping bandits. In a setting with $K$ total arms and at most $A$ available arms in each round over $T$ rounds, the best known upper bound is $O(KsqrtTAlnK)$. We extend our results to the setting of bandits with advice from sleeping experts, generalizing EXP4 along the way.
  arXiv  Detail & Related papers  (2024-03-02T21:22:46Z)
• Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback [9.771002043127728]
  We consider a multi-armed bandit problem for maximum value reward function under maximum value and index feedback. We propose an algorithm and provide a regret bound for problem instances with arm outcomes according to arbitrary distributions with finite supports. Our algorithm achieves a $O((k/Delta)log(T))$ distribution-dependent and a $tildeO(sqrtT)$ distribution-independent regret.
  arXiv  Detail & Related papers  (2023-05-25T14:02:12Z)
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  We consider the adversarial linear contextual bandit setting, which allows for the loss functions associated with each of $K$ arms to change over time without restriction. Since $V_T$ or $L_T*$ may be significantly smaller than $T$, these improve over the worst-case regret whenever the environment is relatively benign.
  arXiv  Detail & Related papers  (2023-05-01T14:00:15Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  Worst-case minimax regret for sparse linear bandits is $widetildeThetaleft(sqrtdTright)$. In the benign setting where there is no noise and the action set is the unit sphere, one can use divide-and-conquer to achieve an $widetildemathcal O(1)$ regret. We develop a general framework that converts any variance-aware linear bandit algorithm to a variance-aware algorithm for sparse linear bandits.
  arXiv  Detail & Related papers  (2022-05-26T15:55:44Z)
• An Experimental Design Approach for Regret Minimization in Logistic Bandits [26.674062544226636]
  The main challenge of logistic bandits is reducing the dependence on a potentially large problem dependent constant $kappa$. We propose a new warmup sampling algorithm that can dramatically reduce the lower order term in the regret in general.
  arXiv  Detail & Related papers  (2022-02-04T21:56:40Z)
• On Submodular Contextual Bandits [92.45432756301231]
  We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
  arXiv  Detail & Related papers  (2021-12-03T21:42:33Z)
• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
  We consider the Scale-Free Adversarial Multi Armed Bandit (MAB) problem with unrestricted feedback delays. textttSFBanker achieves $mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps and $D$ is the total feedback delay.
  arXiv  Detail & Related papers  (2021-10-26T04:06:51Z)
• Bandit Phase Retrieval [45.12888201134656]
  We prove that the minimax cumulative regret in this problem is $smashtilde Theta(d sqrtn)$. We also show that the minimax simple regret is $smashtilde Theta(d / sqrtn)$ and that this is only achievable by an adaptive algorithm.
  arXiv  Detail & Related papers  (2021-06-03T08:04:33Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  We present a reward model that captures set-dependent reward distribution and assumes no total order for arms. We develop a novel regret analysis and show an $Oleft(frack2 n log Tepsilonright)$ gap-dependent regret bound as well as an $Oleft(k2sqrtn T log Tright)$ gap-independent regret bound.
  arXiv  Detail & Related papers  (2021-03-03T23:08:59Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

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.