Trading off rewards and errors in multi-armed bandits

• URL: http://arxiv.org/abs/2605.00488v1
• Date: Fri, 01 May 2026 07:54:27 GMT
• Title: Trading off rewards and errors in multi-armed bandits
• Abstract summary: In multi-armed bandits, the most-explored arms are the most informative, while reward typically pulls only the best arm.<n>We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives.
• Score: 67.17373523809844
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Related papers

• Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting [21.14355421498382]
  We consider the classical multi-armed bandit problem, but with strategic arms.<n>We introduce a new mechanism that establishes an equilibrium wherein each arm behaves truthfully and discloses as much of its rewards as possible.<n>With this mechanism, the agent can attain the second-highest average (true) reward among arms, with a cumulative regret bounded by $O(log(T)/Delta)$ (problem-dependent) or $O(sqrtTlog(T))$ (worst-case)
  arXiv  Detail & Related papers  (2025-01-27T13:01:34Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  We consider a multi-armed bandit setting in which each arm yields an $M$-dimensional vector reward upon selection.<n>The end goal is to identify the best arm of em every objective in the shortest (expected) time subject to an upper bound on the probability of error.<n>We propose an algorithm that uses the novel idea of em surrogate proportions to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step.
  arXiv  Detail & Related papers  (2025-01-23T12:28:09Z)
• Imprecise Multi-Armed Bandits [0.0]
  We introduce a novel multi-armed bandit framework, where each arm is associated with a fixed unknown credal set over the space of outcomes. We then define a notion of regret corresponding to the lower prevision defined by these credal sets.
  arXiv  Detail & Related papers  (2024-05-09T10:58:40Z)
• Information-Gathering in Latent Bandits [79.6953033727455]
  We present a method for information-gathering in latent bandits. We show that choosing the best arm given the agent's beliefs about the states incurs higher regret. We also show that by choosing arms carefully, we obtain an improved estimation of the state distribution.
  arXiv  Detail & Related papers  (2022-07-08T01:15:12Z)
• Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
  We study the setting when, despite the means being unknown, there is a known additive relationship between the source and target MAB instances. We propose and theoretically analyze an LUCB-style algorithm to identify an $epsilon$-optimal target arm with high probability.
  arXiv  Detail & Related papers  (2021-12-08T02:20:18Z)
• Bandit problems with fidelity rewards [7.154621689269006]
  The fidelity bandits problem is a variant of the $K$-armed bandit problem in which the reward of each arm is augmented by a fidelity reward depending on how 'loyal' the player has been to that arm in the past. In the loyalty-points model the amount of extra reward depends on the number of times the arm has previously been played. In the subscription model the additional reward depends on the current number of consecutive draws of the arm.
  arXiv  Detail & Related papers  (2021-11-25T11:09:43Z)
• Generic Outlier Detection in Multi-Armed Bandit [44.11480686973274]
  We propose a novel pulling algorithm named GOLD to identify such generic outlier arms. In the experiments conducted on both synthetic and real-world data sets, the proposed algorithm achieves 98 % accuracy.
  arXiv  Detail & Related papers  (2020-07-14T18:42:44Z)
• Fair Algorithms for Multi-Agent Multi-Armed Bandits [29.68201160277817]
  We propose a multi-agent variant of the classical multi-armed bandit problem. The goal is not to learn the "best arm"; indeed, each agent may perceive a different arm to be the best for her personally. We show that multi-agent variants of three classic multi-armed bandit algorithms achieve sublinear regret.
  arXiv  Detail & Related papers  (2020-07-13T21:20:04Z)
• 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)
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
  The Combinatorial Multi-Armed Bandit problem is a sequential decision-making problem in which an agent selects a set of arms on each round. We show that the recently proposed Gini-weighted smoothness parameter determines the lower bounds for monotone reward functions.
  arXiv  Detail & Related papers  (2020-02-13T08:53:43Z)

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.