Bayesian Exploration: Incentivizing Exploration in Bayesian Games

1 Introduction

• The model adds multiple agents per round interacting through an arbitrary Bayesian game, where recommendations may need to be randomized to maintain incentive compatibility.This extends prior work that assumed one agent per round or utilities unaffected by other agents’ choices (Kremer et al., 2014; Mansour et al., 2015).Source: §1 · pp. 3–4
• The principal’s objective need not align with agents’ cumulative utility; under BIC, the principal can still lower expected social welfare relative to the worst Bayes-Nash equilibrium without the principal.The principal may instead pursue fairness, such as maximizing minimum utility, or even minimize cumulative utility.Source: §1 · p. 4
• The model assumes the same game in every round and standard economic assumptions.Source: §1 · p. 5
• Regret is constant for deterministic utilities and logarithmic for stochastic utilities, with asymptotic constants depending on the Bayesian prior.The policies’ time-averaged expected reward asymptotically approaches the benchmark.Source: §1 · p. 5
• The stochastic-utility policy does not require knowing the distribution of utility noise.The analysis addresses incentive distortion from estimation error and an exponentially growing number of possible observations by moving between the original instance and a deterministic-utility instance.Source: §1 · pp. 5–6
• The principal explores joint actions that some BIC policy can recommend with positive probability, identifying them inductively before computing an optimal randomized recommendation.Utilities revealed by exploring one joint action may enable exploration of others; the paper also gives an explicit BIC policy identifying all explorable actions, including in the single-agent case.Source: §1 · pp. 5–6
• The recommendation game generalizes Bayesian Persuasion by allowing the principal’s history signal to be distinct from, but correlated with, the unknown state.A more informative signal can only improve the principal’s optimal reward and increase the set of explorable joint actions.Source: §1 · p. 5
• The model’s motivating applications include ticket pricing, shared computing resources, and recommendations coordinating people toward experiences with groups they prefer.These examples require learning about demand, resource requirements, or tastes while keeping recommendations compatible with agents’ incentives.Source: §1 · p. 6

2 Related Work

• Kremer et al. (2014) study two actions with one agent per round; Mansour et al. (2015, 2020) obtain optimal stochastic-utility regret rates and reduce arbitrary non-BIC policies to BIC.Source: §2 · p. 7
• Without strategic constraints and with agents following recommendations, Bayesian Exploration reduces to stochastic-reward multi-armed bandits with the principal’s utility as reward.This setting has optimal regret-minimizing algorithms and matching lower bounds (Lai and Robbins, 1985; Auer et al., 2002a,b).Source: §2 · p. 7
• A single round is related to Bayesian Persuasion with multiple agents and a principal’s signal correlated with the state; BIC is a version of Bayes Correlated Equilibrium.The broader connections include information design and social learning.Source: §2 · p. 7
• Incentivized exploration also appears in dynamic pricing, auctions, pay-per-click advertising, human computation, and competition between firms.These scenarios are described as technically incomparable to the paper’s setting.Source: §2 · pp. 7–8
• Subsequent single-agent-per-round work generalizes the economic model, refines stochastic-reward results, and extends incentivized exploration to reinforcement learning.The cited developments include Immorlica et al. (2019, 2020), Sellke and Slivkins (2021), and Simchowitz and Slivkins (2021).Source: §2 · p. 8

3 Bayesian Exploration: our model and results

• The model has a fixed, initially hidden state drawn from a common prior, and each round brings a fresh group of agents into the same simultaneous game.The principal recommends a joint action, and agents observe only their own recommended actions; the principal observes chosen actions and realized utilities.Source: §3 · p. 8
• A BIC policy requires each agent, conditional on following recommendations in prior rounds, to have no incentive to deviate from their current recommendation.The principal maximizes expected total reward subject to this constraint; the reward function may differ from social welfare.Source: §3 · p. 9

3.1 Statement of the main results

• The deterministic-utility policy’s regret bound has a constant depending on the utility structure, not the time horizon.Its per-round running time is polynomial in the generic input size.Source: §3.1 · p. 10
• The stochastic-utility guarantee competes against δ-BIC policies, whereas the deterministic-utility guarantee uses the class of BIC policies.Utilities are bounded in [0,1]; stochastic realized utilities are drawn from distributions with the stated expected utility functions.Source: §3 · p. 9, §3.1 · p. 10
• For stochastic utilities, a BIC policy has a regret guarantee whose constant Cδ depends on the utility structure and δ, but not on the time horizon.The policy does not take the utility distributions D(a,θ) as input.Source: §3.1 · p. 11

3.2 Discussion of the benchmarks

• The one-round OPT benchmark equals the time-averaged benchmark for deterministic utilities with ΠBIC and stochastic utilities with Πδ for δ > 0.For deterministic utilities, OPT(ΠBIC) is characterized by the maximal per-round expected reward of a BIC policy with access to utilities of all explorable joint actions; these benchmarks can generally be weaker than the best-action benchmark because actions may not be explorable or implementable with high probability.Source: §3.2 · p. 11

4 Warm-up and tools

• After a BIC policy explores every joint action by a fixed time, another BIC policy can preserve its history and achieve at least OPT(ΠBIC) in every later round.The resulting later-round reward is at least (T − Tπ) OPT(ΠBIC).Source: §4 · p. 12

4.1 The recommendation game: a single round of Bayesian Exploration

• In the recommendation game, the principal observes a signal and recommends a joint action; BIC means each agent prefers following their recommendation when others do so.The signal represents information from previous rounds and may be correlated with the unknown state.Source: §4.1 · pp. 12–13

4.2 Optimality in the recommendation game

• An LP represents recommendation probabilities, enforces BIC, and computes an optimal policy in polynomial time; when prior actions are restricted to B, round reward is bounded by REW*[AllInfo(B)].The bound applies to stochastic utilities as well.Source: §4.2 · pp. 14–15

4.3 Recommendation game with coupled signals

• With coupled signals, a signal at least as informative as another yields weakly greater optimal reward under the paper’s state-relevant information comparison.The comparison requires the posterior over the state given the more informative signal to be unchanged by also observing the less informative signal.Source: §4.3 · p. 15

4.4 Composition of subroutines

• A BIC subroutine followed by a valid sequel remains BIC when durations are fixed in advance; state-dependent termination can leak information and break incentives.A sequel is valid when the first subroutine’s signal and history determine the next subroutine’s signal.Source: §4.4 · p. 16

4.5 Proof of Lemma 4.1

• The proof of Lemma 4.1 truncates the exploring policy and composes it with repeated optimal policies, preserving BIC through the composition result.The composed policy receives the optimal policy’s expected reward after exploration ends.Source: §4.4 · p. 16, §4.5 · p. 17

5 Bayesian Exploration with deterministic utilities

• A BIC maximally-exploring subroutine followed by optimal recommendations achieves the regret bound of Theorem 3.2 for deterministic utilities.The exploitation policy is optimal for the signal containing information about all explorable joint actions.Source: §5 · pp. 17–18
• For deterministic utilities, OPT(ΠBIC) = REW∗[Adetθ0], the maximal per-round expected reward of a BIC policy informed by all explorable joint actions.The set Adetθ0 includes actions that some BIC policy can recommend with positive probability in some round, conditional on the realized state.Source: §5 · pp. 17–18

5.1 Explorability in the recommendation game

• An action is signal-explorable when some BIC recommendation policy assigns it positive probability for a feasible signal, and the explorable set can only grow with more informative signals.The set for a fixed signal realization is fixed, while the set induced by the random signal depends on its realization.Source: §5.1 · pp. 18–19
• ComputeMaxSupport uses linear programs to identify each signal’s explorable set and computes a max-support policy in time polynomial in |A|, |X|, and |Θ|.MaxExplore then explores all actions in that set while remaining BIC, in at most |A|·|X| / psig[S] rounds.Source: §5.1 · pp. 19–20

5.2 A maximally-exploring subroutine

• RepeatMaxExplore repeatedly applies maximal exploration to signals updated with newly observed utilities, using |A| phases to reach a set of all explorable actions.The explored-action sets are non-decreasing and stabilize by phase |A| + 1.Source: §5.2 · pp. 20–22
• RepeatMaxExplore is BIC, maximally-exploring, and has per-round running time polynomial in |A|·|Θ| and duration at most |A|2 · |Θ|/p∗sig rounds.The parameter p∗sig is the minimum psig[Sℓ] over phases ℓ ≤ |A|.Source: §5.2 · pp. 21–22
• Any policy π can explore only joint actions in B|A+1|, exactly the set explored by RepeatMaxExplore.Source: §5.2 · p. 23

5.3 Putting this all together: proof of Theorem 3.2 and Theorem 5.5

• Composing RepeatMaxExplore with T − T0 copies of an optimal recommendation policy π* yields the reward guarantee of Theorem 3.2.T0 is the duration of RepeatMaxExplore.Source: §5.3 · p. 23
• The supremum defining OPT(ΠBIC) is attained by π ∈ ΠBIC, establishing Theorem 5.5.Source: §5.3 · p. 23
• Each round is polynomial-time computable: RepeatMaxExplore uses Claim 5.11, while π* is computable for S because its realized-state signal has support at most |Θ|.The signal structure for S is also polynomial-time computable using a version of RepeatMaxExplore without calls to MaxExplore.Source: §5.3 · p. 23

6 Bayesian Exploration with stochastic utilities

• The solution combines δ-BIC tools, utility-sampling approximations, and maximal exploration to achieve logarithmic regret against all δ-BIC policies.The policy uses a separation parameter: whenever an agent’s utility changes across states for a fixed joint action, the change is at least ζsep.Source: §6 · p. 24

6.1 Preliminaries: from BIC to δ-BIC

• δ-eventually-explorable actions are those recommendable with positive probability by some δ-BIC policy, and a δ-maximally-exploring subroutine explores all such actions.The section extends recommendation-policy machinery to δ-BIC policies, including δ-signal-explorability and δ-max-support.Source: §6.1 · p. 25

6.2 Approximating the expected utilities

• With d ≥ ζsep^-2 ln(2n|B|/β) samples per joint action, DeNoise recovers AllInfo(B) with probability at least 1 − β in every state.A δ-BIC policy for AllInfo(B) remains BIC for DeNoise(UB) when β ≤ δ^2 · pmin(π)/|Θ|.Source: §6.2 · p. 26

6.3 Approximate signals in a recommendation game

• For coupled signals, a δ-BIC policy for S remains BIC for its β-approximation S′ when β ≤ δ^2 · pmin(π)/|X|.This generalizes the guarantee used to replace full-information signals with denoised utility samples.Source: §6.2 · p. 26, §6.3 · p. 27

6.4 Maximal exploration in a recommendation game

• MaxExploreδ explores EXδ[S] using an approximate input signal and outputs a (β + β′)-approximation to the full-information signal for the explored actions.The subroutine accesses stochastic utilities and collects multiple samples of each explored joint action.Source: §6.4 · p. 28

6.5 Maximal exploration in a repeated game

• The repeated-game maximal-exploration subroutine uses only stochastic utilities yet explores every action explorable by a δ-strictly BIC policy with deterministic utilities.It proceeds in phases, using each approximate signal to explore and construct the signal for the next phase.Source: §6.5 · p. 29
• RepeatMaxExploreδ is BIC when its parameter satisfies Lemma 6.15’s condition.The proof treats it as a composition of phase-wise MaxExploreδ subroutines.Source: §6.5 · p. 29
• With probability at least 1−β, RepeatMaxExploreδ is δ-maximally exploring and outputs a β-signal approximation to AllInfo(Aδ).The guarantee is over the randomness of the stochastic utilities.Source: §6.5 · pp. 30–31

6.6 Putting this all together: proof of Theorem 3.3

• In the final T−Tσ rounds, the composition’s expected reward is at least (1−β)OPTdet(Πdetδ).Here σ is the signal-producing subroutine and Tσ its duration.Source: §6.6 · p. 32
• An approximate signal for AllInfo(Aδ) can be followed by an optimal δ-BIC policy to obtain a BIC composition under Lemma 6.17’s condition on β.RepeatMaxExploreδ is the subroutine used for Theorem 3.3, with duration upper-bounded by Tβ,δ.Source: §6.5 · p. 30, §6.6 · p. 32

7 Conclusions and open questions

• The policies are computationally efficient, with per-round running time polynomial in input size; the number of rounds is also polynomial in input size and depends on the Bayesian prior.The paper presents this alongside its contributions on explorability and constant/logarithmic regret.Source: §7 · p. 32
• The model assumes the game stays fixed across rounds; extending it to changing contexts, such as weather or traffic routes, is left as a direction for future work.The paper relates this extension to contextual bandits and notes prior work for the single-agent-per-round case.Source: §7 · p. 33
• The analysis assumes the principal can commit to a policy and that agents respond rationally to its incentives.The paper describes these assumptions as standard in theoretical economics and notes a subsequent result for the basic one-agent-per-round version.Source: §7 · p. 33
• For stochastic utilities, the results compete with δ-BIC policies for fixed δ > 0, not standard BIC policies, which correspond to δ = 0.The approach requires at least log(1/δ) samples from each explorable joint action; competing with strictly-BIC policies remains elusive.Source: §7 · p. 33
• The model makes no succinct-representation or inference assumptions, so optimizing recommendations typically requires exploring all explorable joint actions and computation polynomial in game-matrix size.A succinct game representation could potentially enable faster exploration or computation.Source: §7 · p. 33

A Monotonicity in information: formulations and proofs

• The proof compares policies through coupled signals and applies the same monotonicity lemma to δ-BIC policies, including in the stochastic-utilities analysis.Expectations in this section range over signals, the state, and any policy randomness.Source: A Monotonicity in information:… · p. 38
• The induced policy for signal S randomizes over actions according to the less-informed policy's action distribution conditional on S.This construction lets a policy using S′ be implemented using S.Source: A Monotonicity in information:… · p. 38
• A more informative signal weakly increases optimal expected reward and preserves δ-BIC: the induced policy has the same reward and remains δ-BIC.The monotonicity result applies to any δ ≥ 0, including BIC when δ = 0.Source: A Monotonicity in information:… · p. 39
• Every action explorable under signal S′ remains explorable under the more informative signal S.The appendix establishes the inclusion EXδ[S′] ⊂ EXδ[S].Source: A Monotonicity in information:… · p. 40

B Approximating the expected utilities: proof of Lemma 6.8

• The proof uses the Chernoff-Hoeffding bound for independent, identically distributed random variables with bounded range to control sample averages.It applies the bound to the stochastic utilities and combines it with a union bound.Source: B Approximating the expected… · p. 40
• When the approximation error is below ζ, the denoised signal S′ equals the signal S based on expected utilities, with probability at least 1 − β.The proof conditions on the event that the utility averages are sufficiently accurate.Source: B Approximating the expected… · p. 40
• With probability at least 1 − β, the average utilities approximate the expected utilities within ζ/2 for every agent and joint action in B.The utilities are bounded in [0,1].Source: B Approximating the expected… · p. 40

• The lower-bound argument draws on the logarithmic Lai–Robbins lower bound for multi-armed bandits.Source: C Lower bound for stochastic utilities · p. 41
• The section first presents a simpler formulation, then points to a stronger result later in the section.Source: C Lower bound for stochastic utilities · p. 41
• For every C > 0, some stochastic-utility instance makes any iterative recommendation policy incur regret of at least C · log t for infinitely many rounds t.The instance uses δ ∈ (0, δ0), where δ0 is an absolute constant.Source: C Lower bound for stochastic utilities · p. 41

• Bandit lower bounds may assert high regret on some instance, in expectation over instances, or on every instance, sometimes with assumptions on the algorithm.The distributional form is stronger than the some-instance form; the unconditional every-instance form is stronger than the distributional form.Source: §C.1 · p. 41
• Bandit lower bounds often rely on lengthy KL-divergence analyses, motivating reduction to an existing lower bound rather than a first-principles proof.Source: §C.1 · p. 41
• Bayesian Exploration lower bounds must match the δ-BIC benchmark, and the authors use Mansour et al. (2020) to argue all actions are explorable in their chosen instances.The benchmark concerns δ-BIC policies for δ > 0, while the cited prior result is stated for δ = 0.Source: §C.1 · p. 41
• Using Mansour et al. (2020), the authors conclude that OPT(Πδ) equals the best-action benchmark for sufficiently small δ-BIC policies.The supplied passage also says the result follows from the cited technique for sufficiently small δ.Source: §C.1 · p. 42
• The authors adapt Lai–Robbins because Bayesian Exploration policies receive a prior, unlike the algorithms in the standard lower bound, and the standard argument includes a regret assumption.They derive the needed assumption within the proof and focus on a carefully constructed instance.Source: §C.1 · p. 42

• The formulation restricts attention to one agent per round, two actions, Bernoulli realized utilities, and a prior over expected utilities.The principal’s reward is set equal to the agent’s utility, and the prior is independent across actions.Source: §C.2 · p. 42
• A lemma establishes that for any two-by-three instance, some δ0 > 0 exists for the subsequent argument.The proof assumes distinct prior mean rewards and orders the actions so that action a1 has the higher prior mean.Source: §C.2 · p. 42
• The proof builds on a policy that explores both actions at least k times, then recommends the action with the highest posterior mean in a final round.For sufficiently small δ and sufficiently large k, the extension is δ-BIC, and its final-round expected reward approaches the best-action benchmark as k grows.Source: §C.2 · pp. 42–43
• The construction uses a two-by-three instance with expected utilities drawn from three values and positive prior probability on each action-value pair.The two actions have distinct prior mean rewards.Source: §C.2 · pp. 42–43
• The lower-bound proof interprets any iterative recommendation policy for the two-by-three instance as an algorithm for Basic Bandits and invokes a non-standard Lai–Robbins bound.The analysis considers policies that run indefinitely and measures regret against the best-action benchmark.Source: §C.2 · p. 43
• The proof argues by contradiction: a policy violating the target bound would induce a low-regret Basic Bandits algorithm, contradicting the Lai–Robbins lower bound on an instance occurring with constant prior probability.The passage states that the resulting Bayesian lower bound follows for the constructed instance.Source: §C.2 · p. 44