Source-linked AI summary
Multi-agent Q-Learning of Channel Selection in Multi-user Cognitive Radio Systems: A Two by Two Case
Husheng Li
TL;DR
Frequent negotiation can impose substantial overhead in cognitive radio systems where primary-user activity changes rapidly. The paper studies negotiation-free channel selection using multi-agent Q-learning, and reports convergence under stated conditions alongside numerical results showing quick collision avoidance, with possible fluctuation when parameters are improperly chosen.
Problem
Frequent resource updates as primary-user activity changes can make negotiation-based resource allocation inefficient because a substantial portion of time may be spent negotiating.
Source: §I · p. 1Method
The paper studies a two-user, two-channel negotiation-free scheme in which each secondary user learns channel selection through Q-learning, treating the other user as part of its environment.
Source: §I · p. 2, §II · p. 2Results
Under certain conditions the learning converges, and numerical results show that secondary users can learn to avoid collision quickly.
Source: B. ODE and Convergence · p. 4, §VII · p. 6Takeaways & Limitations
The 2 × 2 analysis supports negotiation-free learning as a way for secondary users to learn to avoid collisions, while improperly chosen parameters may produce substantial fluctuation.
Source: §VII · p. 6The analysis considers only two secondary users and two channels.
Source: §I · p. 2, §II · p. 2
Abstract
from arXiv · showhide
Resource allocation is an important issue in cognitive radio systems. It can be done by carrying out negotiation among secondary users. However, significant overhead may be incurred by the negotiation since the negotiation needs to be done frequently due to the rapid change of primary users' activity. In this paper, a channel selection scheme without negotiation is considered for multi-user and multi-channel cognitive radio systems. To avoid collision incurred by non-coordination, each user secondary learns how to select channels according to its experience. Multi-agent reinforcement leaning (MARL) is applied in the framework of Q-learning by considering the opponent secondary users as a part of the environment. The dynamics of the Q-learning are illustrated using Metrick-Polak plot. A rigorous proof of the convergence of Q-learning is provided via the similarity between the Q-learning and Robinson-Monro algorithm, as well as the analysis of convergence of the corresponding ordinary differential equation (via Lyapunov function). Examples are illustrated and the performance of learning is evaluated by numerical simulations.
I. INTRODUCTION
Frequent negotiation can consume substantial time when primary-user activity changes rapidly. The paper studies negotiation-free channel selection, where secondary users learn from experience, and models a two-user, two-channel setting with fixed but unknown rewards and no communication.
I. INTRODUCTION
- Negotiation-based resource allocation may incur substantial overhead because primary-user activity can change rapidly, requiring frequent resource updates and short communication periods.The paper motivates avoiding negotiation as a way to address this inefficiency.Source: §I · p. 1
- The proposed setting has secondary users sense channels and choose idle channels without communicating, learning to avoid collisions and the behavior of other users from experience.The users have no a priori information about channel qualities.Source: §I · p. 2
II. SYSTEM MODEL
- The analysis is restricted to two secondary users and two channels, with rewards fixed throughout the game but unknown to both users.A user's reward is zero if the selected channel is interrupted by a primary user or the other secondary user.Source: §II · p. 2
- Both users can sense both channels but choose only one for transmission; the model assumes both channels are available and excludes communication between users.Sensing only one channel, which would create a partially observable game, is outside the paper's scope.Source: §II · p. 2
III. GAME AND Q-LEARNING
The channel-selection problem is modeled as a two-user, two-channel game. The paper uses a Q-function to represent action values under uncertainty about the other user's action.
A. Game of Channel Selection
- The 2 × 2 channel-selection game assigns zero payoff to both users when they choose the same channel, because that conflict yields no reward.Its two pure Nash equilibria are orthogonal transmissions: A chooses channel 1 while B chooses 2, or vice versa.Source: A. Game of Channel Selection · p. 2
B. Q-function
- Because both channels are assumed available, the system has one state, so each Q-value is the expected reward of an action rather than a state-action pair.Q_ij denotes the value to secondary user i of selecting channel j.Source: B. Q-function · pp. 2–3
III. GAME AND Q-LEARNING
- Each user's expected reward depends on its selected channel and the randomness of the other user's action.The game and Q-learning application are introduced as the channel-selection framework.Source: B. Q-function · p. 2, §III · p. 2
C. Exploration
Q-learning randomizes channel choices so that users test their actions. The Boltzmann distribution uses a temperature parameter to control exploration.
C. Exploration
- Q-learning uses stochastic actions, unlike deterministic fictitious play, to assure that all actions are tested.The paper uses a Boltzmann distribution for random exploration.Source: C. Exploration · p. 3
- The temperature γ controls the frequency of exploration in the Boltzmann distribution.Source: C. Exploration · p. 3
- When a user selects a channel, its expected reward depends on the probability that the other user selects the other channel, which yields reward Rij for orthogonal transmissions.Source: C. Exploration · p. 3
D. Updating Q-Functions
The Q-functions are updated after each spectrum access using a step factor that is zero when a channel is not selected. The paper’s geometric intuition divides the Q-value plane into regions whose dynamics lead toward orthogonal channel choices with large probability.
D. Updating Q-Functions
- The update applies a step factor to the selected channel’s Q-value after each access, with the factor set to zero for an unselected channel.The paper assumes additional step-factor conditions to assure convergence.Source: D. Updating Q-Functions · p. 3
IV. INTUITION ON CONVERGENCE
- In the Metrick-Polak plot, the lines µA = 1 and µB = 1 divide the plane into four regions with different Q-learning dynamics.Region I has A preferring channel 1 and B preferring channel 2, leading with large probability to that Nash equilibrium.Source: §IV · p. 3
- Regions II and IV are unstable and move toward I or III with large probability, while strategies in I and III move close to Nash equilibria.The paper concludes that the update generates a stationary equilibrium point with large probability regardless of the initial point.Source: §IV · p. 3
V. STOCHASTIC APPROXIMATION BASED CONVERGENCE
The convergence analysis connects the Q-learning update to Robbins-Monro iteration and uses stochastic approximation to relate its dynamics to an ordinary differential equation. The stationary expected Q-values are expressed through a q-dependent matrix and reward vector.
V. STOCHASTIC APPROXIMATION BASED CONVERGENCE
- The proof strategy equates the Q-learning update with Robbins-Monro iteration and uses stochastic approximation to relate its dynamics to an ODE whose stability is analyzed.The paper states that convergence follows under certain conditions.Source: §V · p. 3, A. Robbins-Monro Iteration · p. 4
A. Robbins-Monro Iteration
- At a stationary point, the expected Q-values satisfy four equations that can be written using q = (QA1, QA2, QB1, QB2)T and a q-dependent matrix A.The formulation uses reward vector r = (RA1, RA2, RB1, RB2)T.Source: A. Robbins-Monro Iteration · pp. 3–4
- The update is treated as a stochastic approximation with observation noise, where the drift is expressed as g_t(q(t)) = r̄ − q(t).The paper identifies the noise term as δM(t) = r̂(t) − q* in the supplied formulation.Source: A. Robbins-Monro Iteration · p. 4
B. ODE and Convergence
The Q-learning update is treated as a stochastic approximation whose dynamics are represented by an ODE. The proof uses Lyapunov analysis to show convergence to the stationary point determined by equation (7).
B. ODE and Convergence
- The Q-function update is a Robbins-Monro stochastic approximation, and its dynamics are related to an ODE.The martingale-difference noise permits application of stochastic-approximation conditions; the paper omits their verification for length.Source: B. ODE and Convergence · p. 4
- With probability 1, the Q-learning sequence converges to a limit set of the corresponding ODE.The ODE's solution converges to the stationary point determined by equation (7).Source: B. ODE and Convergence · p. 4
- Lyapunov analysis shows the ODE derivative is strictly negative when Rij < 2γ, implying convergence to a stationary point.The proof removes this reward-scale condition because convergence is independent of reward scale, so rewards can be scaled to satisfy it.Source: B. ODE and Convergence · p. 5
VI. NUMERICAL RESULTS
The numerical-results section uses a time-varying learning factor, with its initial value denoted by α0.
VI. NUMERICAL RESULTS
- The simulations use a learning factor αij(t) = α0/t, where α0 is the initial learning factor.Source: §VI · p. 5
A. Dynamics
The dynamics examples show Q-learning trajectories moving toward stable regions and channel-selection probabilities changing over time. The reported examples also compare temperature settings and describe an early channel shift that avoids collision.
A. Dynamics
- The trajectories move from unstable Regions II and IV toward stable Regions I and III; smaller γ produces smoother trajectories with less exploration.The examples use γ = 0.1 in Fig. 4 and γ = 0.01 in Fig. 5.Source: A. Dynamics · p. 5, Figure 5 · p. 5
- Both users initially favor channel 1, after which user A intends to choose channel 2, avoiding collision.Fig. 6 shows the evolution of the probability of choosing channel 1 when γ = 0.1.Source: A. Dynamics · p. 5, Figure 6 · p. 5
B. Learning Speed
The simulations report that learning delay varies with the learning factor and temperature.
B. Learning Speed
- A larger α0 yields smaller learning delay, while a smaller γ yields faster learning.Completion is defined as one user's channel-1 selection probability exceeding 0.95 and the other's falling below 0.05.Source: B. Learning Speed · p. 5
C. Fluctuation
The fluctuation analysis shows that improperly chosen lower bounds can cause substantial learning fluctuation. The conclusion reports quick collision avoidance in the 2 × 2 setting, while retaining parameter choice as a caveat.
C. Fluctuation
- Improper lower bounds of 0.4 for αij(t) and 0.2 for exploration probability may cause substantial fluctuation.Fig. 9 illustrates this parameter-choice issue.Source: C. Fluctuation · p. 5, Figure 9 · p. 6
- Figures 7 and 8 plot CDFs of learning delay across different learning factors α0 and temperatures γ.Source: Figure 7 · p. 6, Figure 8 · p. 6
VII. CONCLUSIONS
- In the 2 × 2 case, numerical results show that users can learn to avoid collision quickly, although improper parameter choices may cause substantial fluctuation.The paper reports convergence under certain conditions.Source: §VII · p. 6