PaperlayerView exact revision on arXiv

Source-linked AI summary

Characterizing Oblivious Common-Reward Multi-Player Bandits: Universal Stationarity, Coordination Traps, and Certified Global Rates

Mingxiao Li, Wenhai Lai, Hongyu Wang

arXiv:2610.29673v1cs.LG

TL;DR

In OC-MPMAB, fully oblivious players choose arms simultaneously and observe only their own choices and a shared reward. The paper proves that their independent gradient-bandit updates estimate a hidden product-policy objective’s gradient, guaranteeing finite-time stationarity; global optimality is not guaranteed in general, but structural reward-table certificates yield global bounds.

  • Problem

    In OC-MPMAB, hidden players affect a common reward while each player observes only its own arm and the shared reward, motivating guarantees for this setting without access to other players’ actions.

    Source: Introduction · p. 1

  • Method

    The paper analyzes independent gradient-bandit updates through the centralized product-policy objective they jointly estimate, then studies stationarity and reward-table certificates.

    Source: Introduction · pp. 1–2

  • Results

    Independent updates yield universal finite-time stationarity, but product-policy traps can prevent global optimality; offline reward-table certificates can recover global bounds.

    Source: Introduction · pp. 1–2

  • Takeaways & Limitations

    Global bounds on product-policy gap and pseudo-regret are available when reward-table certificates rule out product-gradient traps and control stochastic sampling noise.

    Source: Introduction · pp. 1–2

    Finite action spaces, normalized rewards, and oblivious gradient-bandit updates alone do not guarantee global optimality; a local component of an optimal joint action may be unrewarding until others coordinate.

    Source: Why Stationarity Does Not Imply… · p. 4, Finite-Time Stationarity · p. 4

Abstract

from arXiv · show

This paper presents a theoretical analysis of the oblivious common-reward multi-player multi-armed bandit (OC-MPMAB), a minimal multi-player bandit model in which multiple players select arms simultaneously and observe only a shared reward. Crucially, the players are fully oblivious: they do not observe the actions of other players and do not even know whether any other players exist. The contributions of this work are threefold. First, we prove that the independent gradient-bandit updates applied by the players jointly form an unbiased stochastic gradient estimator of a hidden product-policy objective. This property then yields a universal finite-time first-order stationarity guarantee for every instance. Second, we show that stationarity cannot, in general, be strengthened to global optimality. To illustrate this, we identify a product-policy trap obstruction that rules out the guarantee of global optimality. Third, we show that global optimality can be recovered under structural assumptions on the reward table. To make global optimality achievable, we introduce finite-table certificates that separately characterize product-gradient dominance and self-bounding stochastic noise. We then establish certificate-conditioned bounds on the product-policy gap and pseudo-regret. Consequently, the standard $O(1/t)$ product-policy gap and $O(\log T)$ pseudo-regret rates hold when the certificates are uniform.

Introduction

The paper studies bandit learning when hidden adaptive components affect a shared reward, so a controller may not know the other decision-makers exist. It establishes universal finite-time stationarity for independent updates, identifies why this does not guarantee global optimality, and gives conditions for global bounds.

Introduction

  • In modular AI systems, hidden adaptive components can change local-arm values even when a controller appears to face a standard bandit problem.The paper formalizes this setting as OC-MPMAB, where players choose local arms and receive a common reward.Source: Introduction · p. 1
  • Finite-time stationarity does not ensure global optimality: product-policy traps can create suboptimal attractors, while reward-table certificates can recover global bounds.The certificates rule out product-gradient traps and control stochastic sampling noise.Source: Introduction · pp. 1–2
  • Independent local gradient-bandit updates jointly estimate the gradient of a centralized expected-reward objective over product policies, yielding universal finite-time stationarity.No player observes the joint action or the centralized objective.Source: Introduction · pp. 1–2

OC-MPMAB Model

OC-MPMAB models finite sets of players choosing arms simultaneously under a fixed reward table, with each player observing only its own arm and the common reward. Each player independently applies a gradient-bandit update, while centralized analysis treats their softmax policies as a product policy.

System Model

  • Each round, players simultaneously select local arms that form a joint action in the product of their arm sets.The environment assigns each joint action a reward distribution whose conditional mean depends on the current joint action, not prior history.Source: System Model · p. 2
  • Players are unaware of one another and observe only their sampled local arm and the shared scalar reward.The joint action space and common reward function are centralized analytical constructs, not information available to individual players.Source: System Model · p. 2

Gradient Bandit Algorithm for Each Player

  • Each player independently uses a softmax policy over local arms and updates its preferences using the sampled arm and common reward.The update requires no knowledge of the number of players, other players’ actions, messages, or the reward table.Source: Gradient Bandit Algorithm for Each… · p. 2
  • From a centralized perspective, the independent local policies induce a product policy, and the expected reward under it defines the objective over preferences.The relevant optimum is the maximum reward over joint actions, although no player observes this objective or product policy.Source: Gradient Bandit Algorithm for Each… · p. 3

Unbiased Product-Policy Gradient

Despite reward dependence on the full joint action, each player’s local update is an unbiased estimator of the corresponding gradient coordinate of the centralized product-policy objective. Thus, concatenating the local updates yields stochastic gradient ascent, and an action-independent baseline preserves the estimator property.

Unbiased Product-Policy Gradient

  • Each local gradient-bandit update is an unbiased estimator of the corresponding partial derivative of the expected-reward objective.The conditional expectation is over the sampled arms and reward in that round.Source: Unbiased Product-Policy Gradient · p. 3
  • The product-policy gradient identity follows by differentiating the local softmax probability and using the conditional mean reward for the sampled joint action.The concatenated updates therefore implement stochastic gradient ascent on the centralized objective.Source: Unbiased Product-Policy Gradient · p. 3
  • Replacing the reward with the reward minus an action-independent, history-measurable baseline preserves the unbiased-gradient claim.The baseline’s score contribution has zero conditional mean.Source: Unbiased Product-Policy Gradient · p. 3

Finite-Time Stationarity

The paper derives finite-time first-order stationarity from the unbiased product-policy gradient and global smoothness of the objective. The guarantee needs no reward-table structure, but controls gradient norms rather than convergence of iterates or global optimality.

Finite-Time Stationarity

  • The expected-reward objective is globally smooth, with valid smoothness constant L = 2d.Here d is the total number of preference coordinates across players and their arms.Source: Finite-Time Stationarity · p. 3
  • Finite-time stationarity bounds control the average and minimum expected gradient norms under the update.The theorem combines the unbiased-gradient identity with smoothness of the objective.Source: Finite-Time Stationarity · pp. 3–4
  • The guarantee requires finite action spaces, rewards normalized to [0, 1], and the unbiased product-policy gradient identity, but no structural assumptions.It does not assert iterate convergence or global optimality.Source: Finite-Time Stationarity · p. 4

Verifiable Structural Global Convergence

The section separates universal stationarity from global optimality: coordination traps obstruct the latter without additional structure. It introduces offline certificates for gradient progress and stochastic noise, then derives conditional global rates and identifies reward-table classes with analytic certificates.

Why Stationarity Does Not Imply Optimality

  • From uniform initialization, the deterministic product-gradient flow can attract both players to a suboptimal block despite a globally optimal joint action.In the example, the default probabilities q1 = q2 = 1/3 lie in the basin attracted to {0, 1}^2.Source: Why Stationarity Does Not Imply… · p. 4
  • Strict trap minors can create open basins where the stochastic update converges to a suboptimal policy, so finite action spaces and normalized rewards alone do not ensure global optimality.The default-initialization block trap also has a probability of convergence to the suboptimal block bounded below independently of the horizon.Source: Why Stationarity Does Not Imply… · pp. 4–5

Two Structural Certificates

  • Product-gradient dominance makes the gradient control the optimality gap, while self-bounding noise keeps update variance proportional to gradient magnitude.The certificates are reward-table properties evaluated over a region containing the trajectory.Source: Two Structural Certificates · p. 5

Structural Global Rate and Regret

  • Uniform certificates yield a product-policy gap of O(1/t) and expected pseudo-regret of O(log T).The finite-horizon guarantee applies when both certificates hold over a region containing the trajectory.Source: Structural Global Rate and Regret · pp. 5–6

Explicit Verifiable Classes

  • Optimally supported common rewards yield O(1/t) product-policy gap and O(log T) expected pseudo-regret under the stated constant-stepsize condition.The corollary relies on sparsity; local dominance provides a separate certificate for dense reward tables.Source: Explicit Verifiable Classes · p. 6
  • Sparse coordination tables and dense locally dominant tables admit analytic certificates, using complementary mechanisms to avoid the block trap.Sparse tables use joint reinforcement; dense tables retain a local advantage across opponent profiles.Source: Explicit Verifiable Classes · p. 6

Mechanism Diagnostics

The diagnostics illustrate the theoretical mechanisms under fully oblivious feedback, rather than serving as a comprehensive benchmark. They contrast sparse coordination, a block trap, and a dense AI-pipeline case.

Mechanism Diagnostics

  • The sparse coordination diagnostic shows a decreasing product-policy gap and invariant support geometry, but its stepsize exceeds the conservative certified range.It diagnoses the mechanism rather than verifying the certified constants.Source: Mechanism Diagnostics · p. 7
  • In the block-trap panel, uniform initialization leaves optimal-profile probability small while the suboptimal block dominates.This is consistent with Proposition 2.Source: Mechanism Diagnostics · p. 7
  • The dense, nonadditive AI-pipeline case has an analytic local-dominance certificate, while its four modules observe only one terminal score.Supplementary diagnostics associate certificate estimates with terminal gaps and report a larger trap basin as suboptimal-block reward approaches the optimum.Source: Mechanism Diagnostics · p. 7

Related Work

The related work spans decentralized and cooperative bandits, common-interest learning, and policy-gradient methods. This paper distinguishes its setting by studying independent learners with only a shared scalar reward and no awareness of other learners or the game model.

Related Work

  • Multi-player bandit work studies collisions, decentralized allocation, and limited communication, while cooperative bandits use communication, aggregation, centralization, or component feedback [Anantharam, Varaiya, and Walrand 1987; Liu and Zhao 2010; Anandkumar et al. 2011; Kalathil, Nayyar, and Jain 2014; Rosenski, Shamir, and Szlak 2016; Besson and Kaufmann 2018; Boursier and Perchet 2019; Bistritz and Leshem 2018; Bistritz and Bambos 2020; Gai, Krishnamachari, and Jain 2012; Chen, Wang, and Yuan 2013; Kveton et al. 2015].OC-MPMAB has neither coordination signals nor awareness of other learners.Source: Related Work · p. 7
  • Product-policy traps relate to common-payoff and potential games, payoff-based dynamics, and independent multi-agent reinforcement-learning coordination failures; unlike equilibrium-selection analyses assuming known game forms or prescribed dynamics, we characterize stationarity, traps, and finite-table certificates.Learners observe neither joint actions, player identities, nor the game model.Source: Related Work · p. 7
  • Classical likelihood-ratio and policy-gradient work studies gradient identities, baselines, and variance reduction, while softmax policy-gradient theory mostly treats single-agent or centralized policies [Glynn 1990; Williams 1992; Sutton et al. 1999; Baxter and Bartlett 2001; Konda and Tsitsiklis 2003; Greensmith, Bartlett, and Baxter 2004; Mei et al. 2022; Mei et al. 2020b,a; Li et al. 2021; Agarwal et al. 2021; Mei et al. 2023].This paper focuses instead on hidden product coupling, its traps, and conditions for global rates.Source: Related Work · p. 7

Conclusion

Independent gradient-bandit updates yield universal finite-time stationarity in OC-MPMAB, but stationarity need not imply global optimality. Under structural reward-table assumptions, finite-table certificates give product-policy gap and pseudo-regret bounds, with standard rates when certificates are uniform.

  • Independent local gradient-bandit updates jointly estimate the hidden product-policy objective without players observing joint actions or the objective.This yields a universal finite-time first-order stationarity guarantee.Source: Conclusion · p. 7
  • Product-policy traps can create suboptimal attractors, so finite-time stationarity cannot generally be strengthened to global optimality.A deterministic block trap can cause failure with constant probability from default initialization under sufficiently small diminishing stepsizes.Source: Conclusion · p. 7
  • Finite-table certificates for product-gradient dominance and self-bounding stochastic noise yield certificate-dependent gap and pseudo-regret bounds.Uniform certificates recover an O(1/t) product-policy gap and O(log T) pseudo-regret.Source: Conclusion · p. 7

Omitted Proofs

The omitted proofs connect local gradient-bandit updates to the product-policy gradient, derive a finite-time stationarity bound, and analyze a deterministic block trap. The trap’s default initialization lies in a region where both optimal-arm probabilities decrease.

Proof of Main-Text Proposition 1

  • Conditioning on the history, differentiating the local softmax factor shows that each player's update contributes to the product-policy objective's gradient.The proof uses the softmax denominator and quotient rule to identify the derivative.Source: Proof of Main-Text Proposition 1 · p. 10

Proof of Main-Text Theorem 1

  • After rearranging and taking total expectations, summing over t = 1,...,T and using J(H) ≤ J⋆ proves the weighted-average bound; the minimum is no greater than the weighted average.Source: Proof of Main-Text Theorem 1 · p. 10

Proof of Main-Text Proposition 2

  • In the block trap, when both optimal-arm probabilities are below 9/19, they decrease and the region is forward invariant.The default initialization has q1 = q2 = 1/3, so both probabilities converge to zero.Source: Proof of Main-Text Proposition 2 · p. 11

Proof of Main-Text Proposition 3

These proofs connect strict-trap results to stochastic lock-in, give the default-initialization block-trap bound, and derive certificate-based gap and pseudo-regret bounds. A sparse reward structure also supports horizon-independent constants for the rate statement.

Proof of Main-Text Proposition 3

Proof of the Main-Text Default-Initialization Block-Trap Statement

  • The default-initialization block-trap probability bound and asymptotic lower bound on expected gap follow from Supplementary Proposition 1.Source: Proof of the Main-Text… · p. 11

Proof of Main-Text Theorem 2

  • Theorem 2's proof uses conditional unbiasedness and certificate bounds to derive product-policy gap and pseudo-regret bounds.The proof sums the gap bound to obtain the displayed pseudo-regret bound.Source: Proof of Main-Text Theorem 2 · p. 11

Proof of Main-Text Corollary 1

Proof of Main-Text Proposition 4

The proof bounds the baseline-free noise ratio by combining reward separation from the optimal joint action with product-gradient dominance.

Proof of Main-Text Proposition 4

Supplementary Theoretical Results

The supplementary results establish stochastic failure on the block trap, characterize strict suboptimal traps and their stochastic lock-in, and extend local-dominance results to additive rewards with bounded interactions.

Constant-Probability Stochastic Failure for the Block Trap

  • 0.1 is the limiting product-policy gap on the positive-probability block-trap event under diminishing stepsizes and zero-preference initialization.The event has probability bounded below independently of the horizon.Source: Constant-Probability Stochastic… · p. 13

Strict Trap Structure Beyond One Matrix

  • A strict suboptimal coordinate-wise local maximum is necessary and sufficient for a strictly attracting pure-product trap in a deterministic two-player, two-arm table.The four strict corner conditions are enumerated in the passage.Source: Strict Trap Structure Beyond One Matrix · p. 14
  • A strict suboptimal trap minor remains an attracting trap in a larger finite table when the corner is also strict against outside unilateral deviations.Policies near the corner flow toward it, and stochastic updates initialized in compact subsets of its basin converge there with positive probability.Source: Strict Trap Structure Beyond One Matrix · p. 15
  • For strict trap minors, stochastic lock-in from compact subsets of the basin yields an expected product-policy gap bounded below by a positive trap-dependent amount.The trap gap is Δtrap = J⋆−r(x0, y0) > 0.Source: Strict Trap Structure Beyond One Matrix · p. 15
  • With block rewards, uniform initialization lies in an invariant bad basin that drives optimal-arm probabilities toward zero and has horizon-independent positive stochastic trapping probability.The stochastic conclusion holds under the diminishing-stepsize conditions stated for the block-trap result.Source: Strict Trap Structure Beyond One Matrix · p. 15

Dense Additive-Interaction Extension

  • For additive rewards with bounded interactions, the local-dominance condition holds with the stated δ, and the explicit Mall(c) bound from Main-Text Proposition 4 applies.The supplied passages do not state the formula for δ.Source: Dense Additive-Interaction Extension · p. 16

Experiments

The experiments combine finite-table certificate checking with simulations of sparse, dense, and trapped product-policy landscapes. The simulations illustrate mechanisms and stress-test a certificate heuristic, while the stated certified bounds come from the checker rather than diagnostic plots.

Experiments

  • Primary trajectories average 200 independent runs over 5000 steps, using η = 0.20 for sparse coordination and the block trap, and η = 0.15 for additive and AI-pipeline instances.Source: Experiments · p. 16
  • The horizon-dependent certificate constants are used in an offline accept/reject check of a proposed stepsize schedule, not as an adaptive online rule.The check verifies γ_t ≤ 1/(LM) through the chosen horizon, with a sharper invariant region or smaller stepsize available if needed.Source: Experiments · p. 17
  • The fixed-depth checker combines analytic lower bounds for λ⋆(c) with rational interval upper bounds for M_all(c), and reports unknown when interval resolution is insufficient.It does not infer certificate positivity from boxes intersecting the zero-gap set; reported certificate pairs are sound.Source: Table 1 · p. 17, Experiments · p. 17

Results

  • The moving baseline leaves the sparse gap at 0.0011, lowers the dense additive gap from 0.0133 to 0.0054, and changes the block-trap gap from 0.0922 to 0.0963.The block-trap gap remains bounded away from zero despite the baseline ablation.Source: Table 4 · p. 18, Results · p. 18
  • Across all three random-table settings, the highest bλrs(c) quartile has a lower mean terminal gap than the lowest quartile.This is an offline stress test of the certificate heuristic, not a comparison with algorithms using stronger information.Source: Table 5 · p. 19, Results · p. 19
  • The optimally supported coordination plots track product-policy gap and average pseudo-regret, with optimal-action probability exactly one minus the gap.The practical stepsize exceeds the sufficient range, so the plots illustrate predicted geometry rather than certify finite-time constants.Source: Figure 3 · p. 19, Results · p. 19
  • In the dense additive instance, each player has a local reward-improving move; in AI-pipeline routing, the update improves both product-policy gap and best-configuration probability.The AI-pipeline table is dense and nonadditive, with an analytic certificate from local dominance.Source: Figure 4 · p. 20, Results · p. 20
  • As the suboptimal coordinated reward approaches the global optimum, the block-trap basin grows, consistent with a product-policy landscape failure rather than a numerical artifact.The default initialization remains concentrated on the suboptimal block and assigns low probability to the globally optimal action.Source: Results · p. 20, Table 6 · p. 20
Loading 2610.29673v1…