PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret

Animashree Anandkumar, Nithin Michael, Ao Kevin Tang, Ananthram Swami

arXiv:1006.1673v1cs.NIstat.ML

TL;DR

The paper addresses distributed learning and channel access with unknown channel availabilities and no communication among secondary users. It develops policies that learn from sensing and feedback, achieving logarithmic regret when the user count is known and nearly logarithmic regret when it is unknown.

  • Problem

    Secondary users must learn unknown channel availability statistics and coordinate access without information exchange or prior agreement.

  • Method

    The paper proposes distributed learning and access policies that use sensing decisions and collision feedback, including estimation of the user count when it is unknown.

  • Results

    The known-user policy achieves logarithmic and order-optimal regret, while the unknown-user policy achieves regret growing slightly faster than logarithmically.

  • Takeaways & Limitations

    The policies provide performance guarantees for distributed cognitive medium access under self play without information exchange.

  • Takeaways & Limitations

    The approach uses an idealistic i.i.d. model for primary transmissions, whereas a Markovian model may be more appropriate in practice.

Abstract

from arXiv · show

The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement among the secondary users. We propose policies for distributed learning and access which achieve order-optimal cognitive system throughput (number of successful secondary transmissions) under self play, i.e., when implemented at all the secondary users. Equivalently, our policies minimize the regret in distributed learning and access. We first consider the scenario when the number of secondary users is known to the policy, and prove that the total regret is logarithmic in the number of transmission slots. Our distributed learning and access policy achieves order-optimal regret by comparing to an asymptotic lower bound for regret under any uniformly-good learning and access policy. We then consider the case when the number of secondary users is fixed but unknown, and is estimated through feedback. We propose a policy in this scenario whose asymptotic sum regret which grows slightly faster than logarithmic in the number of transmission slots.

I. INTRODUCTION

The paper studies distributed learning and channel access when channel availability is unknown and users have no information exchange or prior agreement. It proposes policies with logarithmic or nearly logarithmic regret, including order-optimal regret when the number of users is known.

  • Motivation: Unknown channel availability must be learned from sensing decisions while secondary users opportunistically access idle spectrum.The system seeks higher-availability channels, but their statistics are initially unknown.
  • Motivation: Distributed access without communication creates both collision losses and competition for channels with higher availabilities.Policies must address regret from learning and from coordinating access among users.
  • Contributions: The paper proposes two distributed learning and access policies with regret guarantees under self play.One policy assumes the number of secondary users is known; the other estimates it while learning channel availabilities and access rules.
  • Contributions: O(log n) regret is proved for the policy with known user count, while the unknown-user policy achieves O(f(n) log n) regret for any f(n) tending to infinity.Here n is the number of transmission slots.
  • Contributions: The known-user policy achieves order-optimal regret because a lower bound for uniformly-good distributed learning policies is also logarithmic in transmission slots.The effects of user and channel counts are also characterized and verified through simulations.
  • Significance: The analysis targets the combined exploration-exploitation and cooperation-competition tradeoffs in distributed cognitive medium access.The authors position the results as engineering insights for practical cognitive systems.

II. SYSTEM MODEL & FORMULATION

The paper models slotted cognitive access with unknown, distinct channel availabilities and collision-based feedback. It defines regret against an ideal centralized allocation and seeks policies that maximize successful secondary transmissions.

  • Notation:: The U highest entries of the availability vector μ are the U-best channels, and the remaining channels are the U-worst channels.The notation also defines σ(T; μ), the index of the Tth-highest entry, and Bernoulli Kullback–Leibler distance.
  • A. Sensing & Channel Models: There are U secondary users and C orthogonal channels, with C ≥ U; channel i is free independently across slots with probability μ_i.Primary transmissions occur independently with probability 1−μ_i, and μ_i values are distinct and lie in (0,1).
  • A. Sensing & Channel Models: Each user senses exactly one channel per slot and learns its free or occupied state from that sensing decision.Users maintain sensing histories for the channels, with perfect sensing of primary transmissions.
  • A. Sensing & Channel Models: Under the collision model, simultaneous transmissions by two or more users on one channel all fail, and users receive transmission acknowledgements.Future policies can depend on previous sensing and feedback results.
  • B. Regret of a Policy: The objective is to maximize expected successful secondary transmissions over n slots while respecting primary-user noninterference.S(n; μ, U, ρ) denotes expected total successful transmissions under policy ρ.
  • B. Regret of a Policy: The ideal benchmark assumes known channel statistics and a central agent that orthogonally assigns users to the U-best channels.The benchmark assigns user j to the jth-highest availability channel.
  • B. Regret of a Policy: Regret is the positive gap between ideal benchmark throughput and the expected throughput achieved by a distributed policy.The formulation incorporates collisions and counts sole occupancy through V_i,j(n).

III. SPECIAL CASES FROM KNOWN RESULTS

Known single-user and centralized results reduce channel learning to multi-armed bandits, with logarithmic regret under suitable statistics. The gMEAN statistic is simpler but does not attain the optimal scaling constant.

  • A. Single Secondary User (U = 1): For one secondary user, channel selection is a multi-armed bandit problem with unknown channel availabilities.The best channel is the arm with highest availability.
  • A. Single Secondary User (U = 1): The sample-mean policy has logarithmic regret but does not achieve the optimal scaling constant.The paper therefore uses gMEAN because it is simpler to analyze than gOPT.
  • A. Single Secondary User (U = 1): Uniformly good policies require subpolynomial regret, formalized as R(n; µ, U, ρ) = o(n^α) for every α > 0.This condition supports logarithmic lower-bound analysis.
  • A. Single Secondary User (U = 1): The gOPT statistic achieves the asymptotic logarithmic regret bound for the single-user problem.The bound concerns time spent in suboptimal channels and the resulting regret.
  • B. Centralized Learning & Access for Multiple Users: The centralized multi-user policy generalizes single-user learning while allocating users to orthogonal channels to avoid collisions.Its implementation uses the U highest-ranked channel statistics.

B. Centralized Learning & Access for Multiple Users

With centralized learning and access, a central agent jointly learns channel availabilities and assigns users to the U best channels without collisions. Classical bandit bounds characterize the resulting regret, while the distributed setting must additionally address competition and collisions.

  • Centralized learning and access: A centralized policy allocates the U users to orthogonal channels, avoiding collisions while minimizing sum regret.The central agent uses sensing variables from all users.
  • Centralized regret: The U-worst channels determine the centralized policy’s regret through the time users spend selecting channels below the U best availabilities.The threshold channel is the Uth-best channel.
  • Centralized regret: The centralized gOPT scheme achieves the stated regret bound.The gMEAN scheme also has a stated bound for any n > 0.
  • Distributed motivation: Distributed learning and allocation policies are developed by extending classical multi-armed bandit results.
  • Distributed motivation: Distributed access must balance avoiding U-worst channels against collisions caused by users targeting the same high-availability channels.The regret upper bound separates losses from suboptimal channel selection and collisions.
  • Distributed motivation: The ρRAND policy uses adaptive randomization: a user redraws its rank after a collision and otherwise retains the previous rank.Channel selection follows the rank ordering of each user’s g-statistic.

C. Regret Bounds under ρRAND

Under ρRAND, users learn channel rankings and randomize access to reach an orthogonal configuration on the U best channels. The resulting expected collisions and time in U-worst channels are logarithmic, yielding Θ(log n) regret and fair settling probabilities.

  • Policy behavior: ρRAND asymptotically allocates users orthogonally to the U-best channels.This establishes the target configuration before deriving its regret guarantees.
  • Learning error: The expected time each user spends in any U-worst channel is logarithmically bounded.This controls the regret term caused by selecting lower-availability channels.
  • Collision analysis: With perfect channel knowledge, randomization over the U-best channels forms a finite-state Markov chain whose orthogonal configuration is absorbing.The resulting absorption time bounds collision costs.
  • Collision analysis: Under ρRAND, the expected number of collisions in the U-best channels is O(log n).Only a finite expected number of additional collisions is needed under perfect knowledge, while learning errors add logarithmic cost.
  • Overall regret: The distributed ρRAND(U, C, gMEAN) policy achieves Θ(log n) regret without explicit communication among users.The lost successful-transmission opportunities are logarithmic in the number of transmissions.
  • Fairness: ρRAND does not distinguish users, giving each equal probability of settling in one of the U-best channels while incurring logarithmic regret.The paper reports this fairness phenomenon in simulations.

V. DISTRIBUTED LEARNING AND ACCESS UNDER UNKNOWN NUMBER OF USERS

When the number of secondary users is unknown, ρEST jointly estimates user count, learns channel availability, and adapts decentralized access using collision feedback. Its regret is slightly more than logarithmic, with performance critically dependent on avoiding over-estimation.

  • Policy ρEST: ρEST estimates the number of users while executing ρRAND and updates that estimate from observed collisions.Each user maintains a current estimate and increments it when collision evidence exceeds a threshold.
  • Policy ρEST: Under-estimation causes collisions to accumulate because users target the same top-ranked channels, enabling collision counts to trigger estimate increases.After learning channel ranks, too few targeted channels for the actual user population necessarily creates collisions.
  • Regret guarantees: O(ξ∗(n; U)) regret is achieved when ξ∗(n; U) = ω(log n), where n is the number of transmission slots.The bound depends on the maximum threshold function over candidate user-count estimates.
  • Limitation: Over-estimating U can make regret linear in transmissions because users may select U-worst channels with finite probability even after learning true channel ranks.Avoiding over-estimation is therefore essential for sublinear regret.
  • Regret guarantees: E[T′(n)] = O(log n) for slots in which any user has an incorrect estimate among the top-U channel ranks.This bounds the time spent with wrong channel rankings under ρEST.
  • Regret guarantees: For threshold functions satisfying ξ(n; k) = ω(log n) for k > 1, the probability of over-estimating U vanishes asymptotically.The analysis combines conditional regret bounds with a no-over-estimation result.
  • Regret guarantees: Unknown user count yields O(f(n) log n) regret for any f(n) →∞, compared with O(log n) for ρRAND when the user count is known.Thus, estimating the population size causes a quantified degradation from logarithmic to slightly super-logarithmic regret.

A. Lower Bound For Distributed Learning & access

The paper compares distributed and centralized learning-and-access policies against regret lower bounds and evaluates how regret changes with users, channels, collisions, and fairness. The distributed policy is order-optimal in logarithmic order, but its scaling constant is affected by collisions.

  • Lower bound comparison: ρRAND matches the distributed regret lower bound in order O(log n), although its scaling factors differ.The distributed lower bound is worse than the centralized bound because users learn channel availabilities independently.
  • Varying users: As U increases with fixed C, centralized regret decreases whereas distributed regret increases, primarily because collisions increase under ρRAND.The theoretical result concerns the upper bound under ρRAND; simulations also show increasing actual regret.
  • Comparison of schemes: Centralized allocation has the least regret, while distributed schemes remain O(log n) but are not optimal in the scaling constant.The distributed case has an additional gap because collisions are not accounted for in the comparison.
  • Varying channels: As C increases with fixed U, regret increases for all policies because the number of U-worst channels and the quality gap both increase.When both users and channels increase with their quality, regret also increases as U grows.
  • Collisions and learning: The cumulative number of collisions under ρRAND is logarithmic in n, though simulations with unknown parameters appear linear because n is small.Known channel parameters produce fewer collisions, consistent with the theoretical analysis.
  • Fairness: Under ρRAND, each user has approximately equal frequency of receiving the best channel across 1000 runs, indicating fair allocation.The simulation uses U = 4 users and C = 9 channels.

VIII. CONCLUSION

The paper proposes distributed policies for learning channel availability and accessing channels with multiple secondary users. With provable sum-regret guarantees, the known-user policy is order-optimal and the unknown-user policy is nearly order-optimal.

  • Contributions: The paper proposes two distributed policies for learning channel availability statistics and accessing channels among multiple secondary users.The policies operate in a cognitive network and provide guarantees in terms of sum regret.
  • Policy settings: The first policy assumes the number of secondary users is known, while the second removes that requirement.The second policy estimates the number of users in addition to learning channel availabilities and designing access rules.
  • Guarantees: The known-user policy achieves order-optimal regret, while the unknown-user policy is nearly order-optimal.These guarantees are combined with a lower bound for uniformly good learning-and-access policies.
  • Implications: The analysis provides insights into incorporating learning and distributed medium access control in a practical cognitive network.The conclusion identifies dynamic users, dynamic traffic, and relaxed modeling assumptions as future directions.

APPENDIX

The appendix develops probability and regret bounds by tracking sensing counts, channel-selection events, collisions, and transitions between good and bad learning states. It also bounds the time for random allocation to reach an orthogonal configuration.

  • Sensing counts: T_i(n) counts how often channel i is sensed across all users during n rounds.The appendix sums the per-user sensing counts T_i,j(n) over users.
  • Selection probabilities: The probability of transmitting on channel i is decomposed into the event that its g-statistic is competitive and the event that a U-best channel has a lower statistic.A union bound is then used to control the latter event.
  • Regret decomposition: The regret analysis separates losses associated with sensing U-worst channels from losses associated with collisions.The identity sum_i T_i(n) = nU follows because each of U users senses one channel per slot.
  • Orthogonality time: A genie-aided random-allocation process bounds the expected time to reach orthogonality using the reciprocal probability of an orthogonal configuration.The orthogonality probability is related to the number of compositions of U and the placements of U identical balls in U bins.
  • Random allocation bound: Without the genie, users that avoid collisions retain their choices, so the number of configurations is lower and the time to reach orthogonality is no larger.The argument uses the fact that only one configuration satisfies orthogonality in this analysis.

D. Proof of Lemma 3

The proof analyzes incorrect channel rankings through bad events and correct top-U rankings through good events. It then bounds collisions by combining the durations of bad periods with expected collisions during good runs.

  • Case 1: For U = C = 2, the proof bounds ranking errors by decomposing the relevant event into simpler events and applying a union bound.A Chernoff-Hoeffding bound controls one of the resulting probability terms.
  • Assumption: The proof treats users as identical for the orthogonality analysis.This assumption appears explicitly in the two-user case discussion.
  • Case 2: For min(U, C) > 2, a good event is defined as all users having the correct top-U ordering of g-statistics.The proof separately counts slots under bad events and collisions during runs of good events.
  • Collision bound: Each transition from a bad state to a good state contributes at most U E[Υ(U, U)] expected collisions in the U-best channels.Collisions during bad events are bounded by U E[T′(n)].

F. Proof of Lemma 4

The proof bounds sensing of U-worst channels and collisions in U-best channels, then shows the collision-related bad event probability vanishes asymptotically.

  • Sensing bound: E[Ti,j(n)|C(n; U)] = O(log n) for every U-worst channel i and j = 1, . . . , U.Under C(n; U), a U-worst channel is sensed only when mistaken for a U-best channel.
  • Collision bound: At most U Pa ξ(n; k) collisions occur in the U-best channels, with a defined as the maximum estimated number of users.Conditioned on C(n; U, ), the estimate satisfies a ≤ U.
  • Good and bad events: The good event is that all users’ top-U entries in gj(n) match those in µ.The proof partitions slots into good and bad events and analyzes collisions during runs of good events.
  • Good and bad events: The number of collisions under the bad event is at most T ′(n).This establishes the collision bound used later in the proof.
  • Asymptotic conclusion: P[Cc(n); U] → 0 as n →∞ when k = U, because E[T ′(n)] = O(log n) and ξ∗(n; U) = ω(log n).The proof chooses αn = ω(1) and αn = o(ξ∗(n; k)/ log n) so both terms in the probability bound decay to zero.
Loading 1006.1673v1…