Prior-Agnostic Incentive-Compatible Exploration

Ramya Ramalingam; Osbert Bastani; Aaron Roth

cs.GTFeb 24, 2026

Prior-Agnostic Incentive-Compatible Exploration

Authors: Ramya Ramalingam, Osbert Bastani, Aaron Roth

Organizations: Department of Computer and Information Sciences, University of Pennsylvania

Abstract

In bandit settings, optimizing long-term regret metrics requires exploration, which corresponds to sometimes taking myopically sub-optimal actions. When a long-lived principal merely recommends actions to be executed by a sequence of different agents (as in an online recommendation platform) this provides an incentive misalignment: exploration is "worth it" for the principal but not for the agents. Prior work studies regret minimization under the constraint of Bayesian Incentive-Compatibility in a static stochastic setting with a fixed and common prior shared amongst the agents and the algorithm designer. We show that (weighted) swap regret bounds on their own suffice to cause agents to faithfully follow forecasts in an approximate Bayes Nash equilibrium, even in dynamic environments in which agents have conflicting prior beliefs and the mechanism designer has no knowledge of any agents beliefs. To obtain these bounds, it is necessary to assume that the agents have some degree of uncertainty not just about the rewards, but about their arrival time -- i.e. their relative position in the sequence of agents served by the algorithm. We instantiate our abstract bounds with concrete algorithms for guaranteeing adaptive and weighted regret in bandit settings.

Explore similar work

May 13, 2026

Collaborating in Multi-Armed Bandits with Strategic Agents

We study collaborative learning in multi-agent Bayesian bandit problems, where strategic agents collectively solve the same bandit instance. While multiple agents can accelerate learning by sharing information, strategic agents might prefer to free-ride and avoid exploration. We consider a setting with persistent agents that participate in multiple time periods. This is in contrast to most previous works on incentives in multi-agent MAB, which assume short-lived agents, namely each agent has a single decision to make and optimizes their expected reward in that single decision. As in the multi-agent MAB model with incentives, our model does not have monetary transfers, and the only incentives are through information sharing. We propose CAOS, a mechanism that sustains collaboration as a Nash equilibrium while achieving strong regret guarantees. Our results demonstrate that collaborative exploration can be sustained purely through information sharing, achieving performance close to that of fully cooperative systems despite strategic behavior.

Idan Barnea, Ofir Schlisselberg, Yishay Mansour

Tel Aviv University · Google Research

Multi-Armed Bandits Mechanism Design Game Theory Multi-Agent Collaboration

Ask PDF

Aug 2, 2026

Sharp Characterization of Bias in Post-Bandit Inference

Bandit algorithms generate data for downstream inference, but adaptive sampling biases post-bandit sample means. We analyze this bias for stable index algorithms, including UCB1 and its generalizations, and derive sharp leading-order expressions for the sample-mean bias and expected

Z

-statistic, in bandit experiments of fixed horizon

T

. Our characterization reveals the algorithmic origin of bias through a key index-function-dependent quantity, which we term effective exploration rate. For example, under UCB1, the effective exploration rate is of order

\sqrt{\log T}

, and the standardized bias of any arm (that is not uniquely optimal) decays at the extremely slow rate

1/\sqrt{\log T}

. We also show how the choice of the index function affects both regret and bias, which reveals a regret-bias trade-off: more exploratory algorithm reduces bias but increases regret. We further show how bias most severely distorts confidence intervals and hypothesis tests when the tested arm is one of the tied-optimal arms. Our sharp characterization for bias uses a novel empirical fluid approximation of the algorithm's sampling dynamics, which may be of independent interest.

Lisu Wang, Yilun Chen, Jiaqi Lu

School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen

Multi-Armed Bandits Algorithmic Bias UCB Algorithms

Ask PDF

Sep 17, 2026

Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits

Exploration in centralized serial-dictatorship matching bandits must use complete matchings, so learning one player-arm pair can impose regret on others. We study this externality under a known common priority order and Gaussian rewards with unit variance. We show that the matching-level Graves-Lai constraints reduce to finitely many pairwise exploration quotas and, at top-choice-separated instances, yield a polynomial-size marginal linear program. At these instances, the exact attainable set of expected logarithmic regret coefficients is

G(θ)\mathcal{X}(θ)

, where

\mathcal{X}

is the feasible matching-allocation set and

G

maps allocations to player regret. The usual upper-closed Graves-Lai region can be strictly larger despite having the same Pareto-minimal boundary. We further show that identical exploration quotas can induce very different regret through their scheduling. Finally, we construct estimate-solve-track policies, uniformly good on the full row-strict class, that attain every fixed positively weighted optimum without assuming optimizer uniqueness. Every Pareto-minimal point is pointwise attainable, possibly through an instance-calibrated target.

Lishang Xu, Guodong Ma, Pengcheng Weng +1

University of Bern · EPFL

Multi-Armed Bandits Regret Minimization Combinatorial Multi-Armed Bandits Pareto Optimization

Ask PDF