Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting

• URL: http://arxiv.org/abs/2501.16018v1
• Date: Mon, 27 Jan 2025 13:01:34 GMT
• Title: Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting
• Authors: Ahmed Ben Yahmed, Clément Calauzènes, Vianney Perchet,
• Abstract summary: We consider the classical multi-armed bandit problem, but with strategic arms. We introduce a new mechanism that establishes an equilibrium wherein each arm behaves truthfully and discloses as much of its rewards as possible. 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)
• Score: 21.14355421498382
• License:
• Abstract: We consider the classical multi-armed bandit problem, but with strategic arms. In this context, each arm is characterized by a bounded support reward distribution and strategically aims to maximize its own utility by potentially retaining a portion of its reward, and disclosing only a fraction of it to the learning agent. This scenario unfolds as a game over $T$ rounds, leading to a competition of objectives between the learning agent, aiming to minimize their regret, and the arms, motivated by the desire to maximize their individual utilities. To address these dynamics, we introduce a new mechanism that establishes an equilibrium wherein each arm behaves truthfully and discloses as much of its rewards as possible. 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(\sqrt{T\log(T)})$ (worst-case).

Related papers

• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  We study EgalMAB, an egalitarian assignment problem in the context of multi-armed bandits. We design and analyze a UCB-based policy EgalUCB and establish upper bounds on the cumulative regret.
  arXiv  Detail & Related papers  (2024-10-08T09:49:47Z)
• Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
  Graph-Triggered Bandits is a framework to generalize rested and restless bandits. In this work, we focus on two specific types of monotonic bandits: rising, where the expected reward of an arm grows as the number of triggers increases, and rotting, where the opposite behavior occurs.
  arXiv  Detail & Related papers  (2024-09-09T18:23:07Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  We develop a general framework for clustering and distribution matching problems with bandit feedback. We derive a non-asymptotic lower bound on the average number of arm pulls for any online algorithm with an error probability not exceeding $delta$. Our refined analysis uncovers a novel bound on the speed at which the average number of arm pulls of our algorithm converges to the fundamental limit as $delta$ vanishes.
  arXiv  Detail & Related papers  (2024-09-08T12:19:12Z)
• Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents [57.627352949446625]
  We consider a variant of the multi-armed bandit problem. Specifically, the arms are strategic agents who can improve their rewards or absorb them. We identify a class of MAB algorithms which satisfy a collection of properties and show that they lead to mechanisms that incentivize top level performance at equilibrium.
  arXiv  Detail & Related papers  (2023-12-13T06:54:49Z)
• Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation [50.469872635246176]
  We study a strategic variant of the multi-armed bandit problem, which we coin the strategic click-bandit. This model is motivated by applications in online recommendation where the choice of recommended items depends on both the click-through rates and the post-click rewards.
  arXiv  Detail & Related papers  (2023-11-27T09:19:01Z)
• Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
  We study the Budgeted Multi-Armed Bandit (MAB) problem, where a player chooses from $K$ arms with unknown expected rewards and costs. We propose a new upper confidence bound (UCB) sampling policy, $omega$-UCB, that uses asymmetric confidence intervals. These intervals scale with the distance between the sample mean and the bounds of a random variable, yielding a more accurate and tight estimation of the reward-cost ratio.
  arXiv  Detail & Related papers  (2023-06-12T12:35:16Z)
• Competing for Shareable Arms in Multi-Player Multi-Armed Bandits [29.08799537067425]
  We study a novel multi-player multi-armed bandit (MPMAB) setting where players are selfish and aim to maximize their own rewards. We propose a novel Selfish MPMAB with Averaging Allocation (SMAA) approach based on the equilibrium. We establish that no single selfish player can significantly increase their rewards through deviation, nor can they detrimentally affect other players' rewards without incurring substantial losses for themselves.
  arXiv  Detail & Related papers  (2023-05-30T15:59:56Z)
• Modelling Cournot Games as Multi-agent Multi-armed Bandits [4.751331778201811]
  We investigate the use of a multi-agent multi-armed bandit (MA-MAB) setting for modeling repeated Cournot oligopoly games. We find that an $epsilon$-greedy approach offers a more viable learning mechanism than other traditional MAB approaches. We propose two novel approaches that take advantage of the ordered action space: $epsilon$-greedy+HL and $epsilon$-greedy+EL.
  arXiv  Detail & Related papers  (2022-01-01T22:02:47Z)
• Incentivized Bandit Learning with Self-Reinforcing User Preferences [9.233886766950054]
  We investigate a new multi-armed bandit (MAB) online learning model that considers real-world phenomena in many recommender systems. We propose two MAB policies termed "At-Least-$n$ Explore-Then-Commit" and "UCB-List" We prove that both policies achieve $O(log T)$ expected regret with $O(log T)$ expected payment over a time horizon $T$.
  arXiv  Detail & Related papers  (2021-05-19T01:06:32Z)
• 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)
• Combinatorial Bandits under Strategic Manipulations [25.882801456026584]
  We study the problem of multi-armed bandits (CMAB) under strategic manipulations of rewards, where each arm can modify the emitted reward signals for its own interest. Our setting elaborates a more realistic model of adaptive arms that imposes relaxed assumptions compared to adversarial corruptions and adversarial attacks.
  arXiv  Detail & Related papers  (2021-02-25T07:57:27Z)

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.