COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents

• URL: http://arxiv.org/abs/2505.23720v1
• Date: Thu, 29 May 2025 17:53:12 GMT
• Title: COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents
• Authors: Arun Verma, Indrajit Saha, Makoto Yokoo, Bryan Kian Hsiang Low,
• Abstract summary: Existing work in contextual bandits assumes that agents truthfully report their arms, which is unrealistic in many real-life applications.<n>We propose an algorithm, COBRA, for contextual bandit problems involving strategic agents that disincentivize their strategic behavior without using any monetary incentives.
• Score: 41.57721032039409
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper considers a contextual bandit problem involving multiple agents, where a learner sequentially observes the contexts and the agent's reported arms, and then selects the arm that maximizes the system's overall reward. Existing work in contextual bandits assumes that agents truthfully report their arms, which is unrealistic in many real-life applications. For instance, consider an online platform with multiple sellers; some sellers may misrepresent product quality to gain an advantage, such as having the platform preferentially recommend their products to online users. To address this challenge, we propose an algorithm, COBRA, for contextual bandit problems involving strategic agents that disincentivize their strategic behavior without using any monetary incentives, while having incentive compatibility and a sub-linear regret guarantee. Our experimental results also validate the different performance aspects of our proposed algorithm.

Related papers

• Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits [15.700062892888084]
  We introduce a novel probing framework that strategically gathers information about selected arms before allocation.<n>In the offline setting, where reward distributions are known, we leverage submodular properties to design a greedy probing algorithm with a provable performance bound.<n>For the more complex online setting, we develop an algorithm that achieves sublinear regret while maintaining fairness.
  arXiv  Detail & Related papers  (2025-06-17T21:43:21Z)
• Learning to Lead: Incentivizing Strategic Agents in the Dark [50.93875404941184]
  We study an online learning version of the generalized principal-agent model.<n>We develop the first provably sample-efficient algorithm for this challenging setting.<n>We establish a near optimal $tildeO(sqrtT) $ regret bound for learning the principal's optimal policy.
  arXiv  Detail & Related papers  (2025-06-10T04:25:04Z)
• Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies [41.57721032039409]
  We consider a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item.<n>Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs.<n>We propose algorithms that model online fair division as a contextual bandit problem, with sub-linear regret guarantees.
  arXiv  Detail & Related papers  (2024-08-23T05:25:58Z)
• Fast Peer Adaptation with Context-aware Exploration [63.08444527039578]
  We propose a peer identification reward for learning agents in multi-agent games. This reward motivates the agent to learn a context-aware policy for effective exploration and fast adaptation. We evaluate our method on diverse testbeds that involve competitive (Kuhn Poker), cooperative (PO-Overcooked), or mixed (Predator-Prey-W) games with peer agents.
  arXiv  Detail & Related papers  (2024-02-04T13:02:27Z)
• Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents [52.75161794035767]
  We introduce a class of bandit algorithms that meet the two objectives of performance incentivization and robustness simultaneously.<n>We show that settings where the principal has no information about the arms' performance characteristics can be handled by combining ideas from second price auctions with our algorithms.
  arXiv  Detail & Related papers  (2023-12-13T06:54:49Z)
• Bandit Social Learning: Exploration under Myopic Behavior [54.767961587919075]
  We study social learning dynamics motivated by reviews on online platforms.<n>Agents collectively follow a simple multi-armed bandit protocol, but each agent acts myopically, without regards to exploration.<n>We derive stark learning failures for any such behavior, and provide matching positive results.
  arXiv  Detail & Related papers  (2023-02-15T01:57:57Z)
• Incentive-Aware Recommender Systems in Two-Sided Markets [49.692453629365204]
  We propose a novel recommender system that aligns with agents' incentives while achieving myopically optimal performance. Our framework models this incentive-aware system as a multi-agent bandit problem in two-sided markets. Both algorithms satisfy an ex-post fairness criterion, which protects agents from over-exploitation.
  arXiv  Detail & Related papers  (2022-11-23T22:20:12Z)
• Robust Multi-Agent Multi-Armed Bandits [26.26185074977412]
  Recent works have shown that agents facing independent instances of a $K$-armed bandit can collaborate to decrease regret. We show that collaboration indeed decreases regret for this algorithm, assuming $m$ is small compared to $K$ but without assumptions on malicious agents' behavior.
  arXiv  Detail & Related papers  (2020-07-07T22:27:30Z)
• Adversarial Attacks on Linear Contextual Bandits [87.08004581867537]
  Malicious agents may have incentives to attack the bandit algorithm to induce it to perform a desired behavior. We show that a malicious agent can force a linear contextual bandit algorithm to pull any desired arm $T - o(T)$ times over a horizon of $T$ steps. We also investigate the case when a malicious agent is interested in affecting the behavior of the bandit algorithm in a single context.
  arXiv  Detail & Related papers  (2020-02-10T15:04:09Z)

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.