Research map / Bandits and online learning / Multi-armed bandits
Replication-proof Bandit Mechanism Design with Bayesian Agents
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies replication-proof (truthful) bandit mechanisms where Bayesian agents know only the prior over their arms' mean rewards, giving necessary and sufficient conditions in the single-agent case and a sublinear-regret replication-proof ETC-based hierarchical algorithm for multiple agents.
Problem
Designing bandit algorithms where strategic agents who register arms (and may replicate them for free) have no incentive to replicate, when agents only know the prior distribution of their arms' mean rewards rather than the realized means.
Approach
Introduces random-permutation regret and the TRP (truthful under random permutation) plus permutation-invariance conditions, shown to be necessary and sufficient for single-agent replication-proofness; ETC satisfies them, and a hierarchical two-phase ETC with a restarting round extends this to multiple agents with sublinear regret.
Key results
- UCB1 is shown not replication-proof in the single-agent setting, and H-UCB is not replication-proof for any number of agents under the Bayesian setting.
- In the single-agent setting, ETC with exploration length m >= (2/Delta^2) l ln(2T) is TRP and permutation invariant, hence replication-proof, with regret bound sum_a (2 delta_a l ln(2T)/Delta^2 + 1).
- The multi-agent algorithm (hierarchical ETC with restarting round) is replication-proof and achieves expected regret O(n L^3 sqrt(T ln T) / Delta^3), matching H-UCB's sublinear rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ETC in both phases and add a restarting round | HBB · Multi-agent bandit | expected regret: O(\frac{nL^3\sqrt{T \ln T}}{\Delta^3}) | Helped |
| Use ETC with exploration length m ≥ 2l ln(2T)/Δ² | Single-agent ETC · Single-agent bandit | regret: \sum_{a\in [l]} \Big( \frac{2\delta_a l\ln{(2T)}}{\Delta^2} + 1 \Big) | Helped |
| Use standard UCB1 | UCB1 · Single-agent bandit | replication-proofness | Hurt |
| Use hierarchical UCB | H-UCB · Multi-agent bandit | replication-proofness | Hurt |
| Use uniform-random agent selection in the first phase | Hierarchical algorithm with a TRP, permutation-invariant second phase · Multi-agent bandit | regret | Hurt |
| Require truthfulness under random permutation and permutation invariance | Single-agent bandit algorithm · Single-agent bandit | replication-proofness | Helped |
| Use ETC with exploration length m ≥ 2l ln(2T)/Δ² | ETC · Single-agent bandit | replication-proofness | Helped |
Surprising findings
- Standard UCB, which is replication-proof when agents are fully informed, fails to be replication-proof in the Bayesian single-agent setting regardless of its exploration parameter.
Limitations
- Results assume discrete prior supports with known minimum gap Delta and known number of arms; prior-independence is only achieved with polylogarithmic loss under extra assumptions.
- Whether non-adaptive structure is necessary for TRP is left as an open problem.
- Analysis assumes a stochastically ordered family of arms (e.g., Bernoulli, Gaussian).
Experimental setup
Metrics: expected regret replication-proofness (dominant strategy equilibrium)
Baselines: UCB1 H-UCB
Builds on: H-UCB (Shin et al. 2022) UCB1 exploration-then-commit
Closest papers by meaning
- Adaptive Sample Sharing for Multi Agent Linear Bandits (ICML 2025 · similarity 0.88)
- Replicable Constrained Bandits (NeurIPS 2026 · similarity 0.87)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.87)
- Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting (NeurIPS 2024 · similarity 0.86)
- Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents (ICML 2025 · similarity 0.86)
- Protocols for Verifying Smooth Strategies in Bandits and Games (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.