Distributed Learning in Multi-Armed Bandit with Multiple Players

Keqin Liu; Qing Zhao

Source-linked AI summary

Distributed Learning in Multi-Armed Bandit with Multiple Players

Keqin Liu, Qing Zhao

arXiv:0910.2065v3Oct 12, 2009math.OCcs.LGmath.PR

TL;DR

The paper studies decentralized MABs with multiple players that learn independently under collisions and unknown arm rewards. It constructs a TDFS-based policy that fairly shares the M best arms without pre-agreement and proves centralized-order regret under a general reward model. It also shows that TDFS works with any order-optimal single-player policy and establishes a lower bound on the decentralized leading constant.

Problem
The paper asks whether decentralized players that cannot exchange observations can achieve the centralized MAB's logarithmic system-regret order despite collisions.
Method
The paper constructs a Time Division Fair Sharing policy that distributes the M best arms without pre-agreed schedules and supports general reward models.
Results
The decentralized policy achieves the same logarithmic regret order as centralized MAB, and its order optimality persists with different order-optimal single-player policies.
Takeaways & Limitations
TDFS provides a fair decentralized construction whose basic structure can be paired with any order-optimal single-player policy.

Abstract

from arXiv · show

We formulate and study a decentralized multi-armed bandit (MAB) problem. There are M distributed players competing for N independent arms. Each arm, when played, offers i.i.d. reward according to a distribution with an unknown parameter. At each time, each player chooses one arm to play without exchanging observations or any information with other players. Players choosing the same arm collide, and, depending on the collision model, either no one receives reward or the colliding players share the reward in an arbitrary way. We show that the minimum system regret of the decentralized MAB grows with time at the same logarithmic order as in the centralized counterpart where players act collectively as a single entity by exchanging observations and making decisions jointly. A decentralized policy is constructed to achieve this optimal order while ensuring fairness among players and without assuming any pre-agreement or information exchange among players. Based on a Time Division Fair Sharing (TDFS) of the M best arms, the proposed policy is constructed and its order optimality is proven under a general reward model. Furthermore, the basic structure of the TDFS policy can be used with any order-optimal single-player policy to achieve order optimality in the decentralized setting. We also establish a lower bound on the system regret growth rate for a general class of decentralized polices, to which the proposed policy belongs. This problem finds potential applications in cognitive radio networks, multi-channel communication systems, multi-agent systems, web search and advertising, and social networks.

I. INTRODUCTION

The paper studies decentralized MABs in which multiple players independently learn unknown arm rewards while collisions can reduce or redistribute rewards. It shows that decentralized policies can match the centralized logarithmic regret order, while providing fair arm sharing and broad policy and reward-model compatibility.

Problem: In decentralized MABs, M distributed players independently select among N arms with unknown reward parameters and cannot exchange observations or decisions.Collisions occur when players select the same arm, potentially eliminating or sharing rewards depending on the collision model.
Problem: The system regret measures reward loss relative to known-model centralized scheduling, extending the classic single-player regret objective to distributed players.The centralized multiple-play MAB supplies a lower bound on decentralized regret growth.
Main Results: The proposed policy achieves the same logarithmic regret order as centralized MAB despite local learning and unavoidable collisions.This order is achieved under a fairness constraint requiring players to accrue reward at the same rate.
Main Results: Time Division Fair Sharing (TDFS) shares the M best arms without pre-agreed schedules and remains order-optimal under a general reward model.Its basic structure can be combined with any order-optimal single-player policy.
Main Results: The TDFS construction preserves order optimality when players use different order-optimal single-player policies.This makes the decentralized construction less tied to a particular local policy.
Main Results: A tighter-than-centralized lower bound is established for the leading constant of a general class of decentralized policies, including TDFS.The result indicates that decentralization is likely to incur a larger leading constant than centralized learning.

E. Related Work

Prior work developed order-optimal distributed policies, while TDFS extends order optimality to broader reward models and any order-optimal single-player policy, with equal time-average rewards for players.

Earlier distributed policies achieved order optimality by extending index-type single-user policies.
TDFS applies to broader reward models, including Gaussian and Poisson distributions with infinite support.
TDFS can combine with any order-optimal single-player policy to achieve decentralized order optimality.
Unlike policies that assign users to channels with different throughput, TDFS gives each player the same time-average reward at the same rate.
The TDFS logarithmic order remains valid when players observe different reward distributions on an arm, provided the M best arms are common and have equal means across players.
The analysis leaves open whether the same result holds when players have different means for each arm.

B. The Logarithmic Order and the Optimal Policy

The single-player Lai-Robbins policy uses point estimates and confidence upper bounds to select between a leader and a round-robin candidate. Under regularity conditions, it achieves the minimum leading constant of logarithmic regret growth.

Under the stated regularity conditions, the policy achieves the minimum leading constant of the single-player MAB regret growth rate.
The policy maintains a point estimate of each arm’s mean and a confidence upper bound representing its potential.
At each time, it selects the best-estimated sufficiently sampled arm as leader and compares it with a round-robin candidate.
The leader is played only when its point estimate exceeds the candidate’s confidence upper bound.
Although the confidence upper bound lacks a closed form, implementation requires only the point estimate because the comparison is equivalent to two conditions.
The policy initializes by playing each arm once before applying the leader-selection rule.

C. Order-Optimal Index Policies

Index policies simplify single-player MAB decisions by selecting the arm with the greatest sample-mean-based index, but their optimality and decentralized formulation depend on reward-model assumptions.

Index policies assign each arm a value based on its sample mean and play the arm with the greatest index.
Except for Gaussian rewards, the cited index policy achieves the optimal logarithmic order but not the best leading constant.
Several index policies achieve order-optimal regret for reward distributions with known finite support.
TDFS uses collision observations to adjust schedule offsets and reduce future collisions while sharing the M best arms.
Players choose arms using only local observation and decision histories, which include collision history.
The formulation allows collision models where colliding players either share a reward arbitrarily or receive no reward.
The decentralized problem measures total reward loss relative to the same M-best-arm benchmark as the centralized counterpart.
The observation model permits player-specific arm-state distributions when the M best arms are common and have equal means across players.

IV. THE OPTIMAL ORDER OF THE SYSTEM REGRET

The decentralized MAB has logarithmic optimal system-regret growth under both collision models, matching the centralized order. The TDFS construction achieves this order while supporting fair sharing and eliminating pre-agreement.

Logarithmic optimal system-regret growth holds under both collision models.The theorem bounds the growth between constants depending on Θ.
The proof transfers the centralized lower bound and constructs a decentralized policy achieving logarithmic regret growth.
Under nonnegative means for the M best arms, playing exactly M arms centrally is equivalent to playing at most M arms.
The TDFS structure preserves order optimality with any single-player policy having optimal logarithmic order, and using all observations may improve constants.
For M = 2, each player uses one best-arm subsequence and random mini-sequences for learning the second-best arm after excluding the preceding candidate.
TDFS divides time into M subsequences so players target the M best arms in round-robin fashion with different offsets.

B. Order-Optimality under Fairness Constraint

Under fairness, TDFS learns the entire set of M best arms while controlling misidentification and collisions logarithmically. Consequently, its system regret is logarithmic and the policy is order-optimal and fair.

Learning the entire rank of the M best arms is harder because identification errors propagate to later ranks.
Each player targets a rank-specific arm in deterministic subsequences and uses random mini-sequences formed by removing previously targeted arms.
The leader-versus-round-robin rule selects a leader when its estimate exceeds the candidate’s confidence upper bound; otherwise it explores the candidate.
The number of slots in which a player misses its assigned best arm is at most logarithmic with time.
Collisions on each of the M best arms are logarithmic, so reward loss from missed plays or collisions is logarithmic.
TDFS is order-optimal and ensures fairness under a fair collision model, giving each player the same time-average reward.

C. Eliminating the Pre-Agreement

The pre-agreement on time-division offsets can be removed while preserving TDFS order optimality and fairness. Players randomize offsets on joining and revise them after collisions.

Pre-agreement among players on time-division offsets is unnecessary for order-optimal and fair TDFS.
A joining player randomly selects an offset uniformly from {0, 1, · · · , M −1} and cycles through the M best arms.
The player keeps its offset when the initial M plays are collision-free and randomly regenerates it otherwise.

VI. A LOWER BOUND FOR A CLASS OF DECENTRALIZED POLICES

This section defines the TDS policy class and establishes a regret-growth lower bound for uniformly good decentralized policies in that class. The TDFS policy belongs to TDS, and simulations compare its leading constant across settings.

Time Division Selection Policies: TDS policies allocate each player’s selections among the M best arms using parameter-independent time fractions.The fractions satisfy a_i,j ≥ 0 and sum to one for each player, with expected selection counts a_i,jT − o(T^b).
Time Division Selection Policies: The TDFS policy belongs to the TDS class with a_i,j = 1/M for every player-arm pair.Its time-sharing structure allows players to select each of the M best arms according to fixed portions.
Lower Bound: Theorem 5 establishes a lower bound on regret growth for every uniformly good decentralized policy in the TDS class.The proof counts suboptimal-arm plays, first identifying players assigned to the best arms and then lower-bounding exploration of inferior arms.
Lower Bound: The lower-bound argument constructs M distinct players whose expected play counts for the ith best arms are at least T divided by cumulative assignment factors, up to o(T^b).This assignment structure leads to the displayed logarithmic regret lower bound when collisions are excluded in the best case.
Simulation Examples: Simulations evaluate the leading logarithmic regret constant for TDFS under Bernoulli, exponential, and Gaussian reward examples.They compare single-player policies, pre-agreement choices, coupling, and the effects of M and N.
Simulation Examples: Using the Lai–Robbins policy gives the best performance in the Bernoulli example, while coupling parallel procedures improves performance relative to no coupling.Eliminating pre-agreement can impose a performance cost in one setting, and performance degrades as M increases there.

B. Multichannel Communications under Unknown Fading: Exponential Reward Model

This section applies decentralized TDFS to unknown-fading multichannel communication and Gaussian target-collection models. The examples compare leading regret constants and examine pre-agreement and horizon effects.

Exponential Reward Model: In the fading-channel model, each user selects a channel, observes its fading condition, and receives capacity-related reward under exponential unknown-mean SNR.Colliding users receive no reward, and higher expected SNR corresponds to higher expected capacity.
Exponential Reward Model: The exponential model can use SNR itself as the reward because expected channel capacity increases with expected SNR.The reward density is f(s; θ) = 1/θ exp(−x/θ) for s ∈ R+.
Simulation Results: The simulations plot the leading constant of logarithmic regret against N or M for fixed values of the other parameter.The plotted comparisons include centralized and TDS lower bounds and TDFS with or without pre-agreement.
Simulation Results: Eliminating pre-agreement has little impact on TDFS performance in the fading and Gaussian examples.The Gaussian example also reports rapid convergence of the regret growth rate, indicating strong performance within a short finite period.
Gaussian Reward Model: In the Gaussian target-collection model, agents independently select locations whose rewards have unknown means and a common known variance.When multiple agents select one location, they share its reward; log-Gaussian and Gaussian models preserve arm rankings under equal variance.

APPENDIX A.

This appendix states reward-model conditions, centralized multiple-play benchmarks, and proof components used to bound decentralized TDFS regret. It decomposes errors into three slot-count terms and shows logarithmic control.

Conditions: The appendix assumes an unknown-parameter reward family with existing means, positive finite divergence for ordered means, divergence continuity, and a dense parameter space.Additional conditions constrain point estimates and confidence bounds through high-probability and sampling-count properties.
Centralized Benchmark: When the M best arms have nonnegative means, the known-parameter benchmark selects those arms and provides the ideal immediate-reward baseline.The centralized multiple-play problem is equivalent to selecting up to M arms because an optimal policy selects exactly M arms.
Proof Decomposition: The proof partitions suboptimal selections into N1(T), N2(T), and N3(T), based respectively on accurate leaders, inaccurate estimates, and non-best-arm leaders.Each term counts slots in the dominant mini-sequence under a distinct leader-estimation condition.
Proof Bounds: E[N1(T)], E[N2(T)], and E[N3(T)] are each at most logarithmic in T.The appendix separately bounds estimation-error and incorrect-leader events before combining the resulting terms.
Proof Bounds: The proof shows that sufficiently reliable confidence estimates force the ith-best arm to become the leader and be selected on the corresponding event.Geometric time blocks and concentration events yield summable error probabilities used in the logarithmic bounds.

APPENDIX D. PROOF OF LEMMA 3

This appendix proves Lemma 3 by induction over arm rank and player index. The argument combines dominant-mini-sequence counts with Lemma 2 to control deviations from assigned best-arm play.

Induction Base: The proof begins with player index i = 1, applying the Lai–Robbins policy across the player’s dominant mini-sequence.Lemma 2 supplies the needed bound for the first induction case.
Inductive Quantities: For each player, the proof tracks expected slots in the dominant mini-sequence and the expected slots where the assigned ith-best arm is not played.These quantities establish the induction statements for arm-rank assignments.
Inductive Step: The induction assumes the bounds for i = k and then establishes them for i = k + 1.The argument uses the previously proved rank and mini-sequence estimates to extend the result to the next player-arm assignment.
Conclusion: The induction concludes with Lemma 3.The appendix explicitly states that the required statements hold after completing the induction.

APPENDIX E. PROOF OF THE UPPER BOUND C(Θ) IN THEOREM 2

The proof bounds system regret by analyzing reward losses from suboptimal-arm plays and collisions across two collision models. It shows that singular slots and collision-involving normal slots grow at most logarithmically with time.

Slot classification: In normal rounds, players play the M best arms in the correct order according to their local offsets; otherwise, the round is singular.Slots are classified as normal only when every player’s containing round is normal.
Regret decomposition: Reward loss occurs only in singular slots or normal slots involving collisions, so bounding these slot counts suffices for logarithmic regret growth.The proof explicitly reduces the regret analysis to these two types of slots.
Singular slots: Singular rounds and slots have expected counts at most logarithmic in time across all player groups.Each singular round corresponds to M singular slots, preserving the logarithmic order.
Normal-slot collisions: 30? The expected number of collision-involving normal slots between consecutive singular slots is uniformly bounded.Collisions in normal slots arise when players share a global offset, and players randomize a new local offset after observing a collision.
Normal-slot collisions: The expected number of collision-involving normal slots therefore has the same logarithmic order as the expected number of singular slots.Together, these bounds establish the required logarithmic-order control for the relevant loss events.

APPENDIX G. PROOF OF LEMMA 4

The lemma’s proof changes one arm’s mean parameter and uses likelihood-growth arguments to control the probability of insufficient sampling. It also constructs a nonnegative correction term for the sampling-count bound.

Parameter change: Replacing the kth best arm’s mean by λ creates a new parameter set Θ′ under which that arm has a different rank.The proof denotes the replaced arm by l and uses its rank under Θ′ in the subsequent argument.
Sampling-count bound: A random correction c(T) is chosen so that c(T) + v(T) − τ_l,T is almost surely nonnegative and has nonnegative expectation under Θ′.This permits conditioning on the event τ_l,T < (1−δ) log v(T) without reversing the relevant inequality.
Likelihood growth: The strong law gives L_t/t → I(θσ(k), λ) > 0 almost surely, and the same limit holds for max_i≤t L_i/t.These limits support the asymptotic control of likelihood-related events.
Likelihood growth: The probability of simultaneous early likelihood growth and insufficient sampling converges to zero as T tends to infinity.The displayed event uses thresholds involving (1−δ) log v(T) and (1−b) log v(T).