Multiagent -Learning for Aloha-Like Spectrum Access in Cognitive Radio Systems

The Aloha-like spectrum access problem is essentially an game. When secondary user transmits over an idle channel , it receives reward (e.g., channel capacity or successful transmission probability), if no other secondary user transmits over this channel, and reward 0, if one or more other secondary users are transmitting over this channel, since collision will happen. We assume that the reward does not change with time. When channels change slowly, the learning algorithm proposed in this paper can also be applied to track the change of channels. When channels change very fast, it is impossible for secondary users to learn. Since there is no explicit information exchange among secondary users, the collision avoidance is completely based on the received reward. The payoff matrices for the case of are given in Figure 3. Note that the actions, denoted by for user at time , in the game are the selections of channels. Obviously, the diagonal elements in the payoff matrices are all zero since collision yields zero reward.

It is well known that Nash equilibrium means the strategies such that unilaterally changing strategy incurs the degradation of its own performance. Mathematically, a Nash equilibrium means a set of strategies , where is the strategy of player , which satisfy

where means the reward of player and means the strategies of all players except player .

It is easy to verify that there are multiple Nash equilibrium points in the game. Obviously, orthogonal transmission strategies, that is, , , are pure equilibria. The reason is the following. If a secondary user changes its strategy and transmits over other channels with nonzero probability, those transmission will collide with other secondary users (recall that, for the Nash equilibrium, all other secondary users do not change their strategies) and incurs performance degradation. The orthogonal channel assignment can be achieved in the following approach: let all secondary users sense the channel randomly at the very beginning; once a secondary user finds an idle channel, it will access this channel forever; after a random number of rounds, all secondary users will find different channels, thus achieving the orthogonal transmission. We call this scheme the simple orthogonal channel assignment since it is simple and fast. However, in this scheme, the different rewards of different channels are ignored. As will be seen in the numerical simulation results, the proposed learning procedure can significant outperform the simple orthogonal channel assignment.

We define the -function as the expected reward in one time slot (since the channel states are completely known to the secondary users and are not controlled by the secondary users, each secondary user needs to consider only the expected reward in one time slot, that is, a myopic strategy) of each action under different states; that is, for secondary user and system state , the -value of choosing channel is given by

where is the reward obtained by secondary user , which is dependent on the action, as well as the system state, and the expectation is over the randomness of other users' actions, as well as the primary users' occupancies.

In contrast to fictitious play [11], which is deterministic, the action in -learning is random. We assign nonzero probabilities for all channels such that all channels will be explored. Such an exploration guarantees that good channels will not be missed during the learning procedure. We consider Boltzmann distribution [23] for random exploration, that is,

where is called temperature, which controls the randomness of exploration. Obviously, the smaller is (the colder), the more focused the actions are. When , each user chooses only the channel having the largest -value.

When secondary user selects channel and the system state is , the expected reward is given by

since secondary user ( ) chooses channel with probability (collision happens and secondary user receives no reward) and channel is idle with probability ; then the product in (4) is the probability that no other secondary user accesses channel .

In the procedure of -learning, the -functions are updated after each spectrum access using the following rule:

where is a step factor (when channel is not selected by user , we set ), is the reward of secondary user and is the characteristic function of the event that channel is selected by secondary user at the th spectrum access. Note that this is the standard -learning without considering the future states. An intuitive explanation for (5) is that, once channel is accessed, the corresponding -value is updated by combining the old value and the new reward; if channel is not chosen, we keep the old value by setting . Our study is focused on the dynamics of (5). To assure convergence, we assume that

as well as

Note that, in a typical stochastic game setting and -learning, the updating rule in (5) should consider the reward of the future and add a discounted term of the future reward to the right hand side of (5). However, in this paper, the optimal strategy is myopic since we assume that the system state is known, and thus the secondary users' actions do not affect the system state. For the case of partial observation (i.e., each secondary user knows only the state of a single channel), the action does change each secondary user's state (typically the belief of system state), and the future reward should be included in the right hand side of (5), which will be discussed in Section 5.

The -values for different users are mutually coupled and all -values change if one -value is changed since the strategy of the corresponding user is changed, thus changing the expected rewards of other users. We define -values satisfying the following equations as a stationary point

Note that the stationarity is only in the statistical sense since the -values can fluctuate around the stationary point due to the randomness of exploration. Obviously, as , the stationary point converges to a Nash equilibrium point. However, we are still not sure about the existence of such a stationary point. The following lemma assures the existence of stationary point. The proof is given in Appendix .

Lemma 1.

For sufficiently small , there exists at least one stationary point satisfying (8).

As will be shown in Proposition 1, the updating rule of -values in (5) will converge to a stationary equilibrium point close to Nash equilibrium. Before the rigorous proof, we provide an intuitive explanation for the convergence using the geometric argument proposed in [24].

The intuitive explanation is provided in Figure 4 for the case of (we call it Metrick-Polak plot since it was originally proposed by A. Metrick and B. Polak in [24]). For simplicity, we ignore the indices of state and assume that both channels are idle. The axes are and , respectively. As labeled in the figure, the plane is divided into four regions separated by two lines and , in which the dynamics of -learning are different. We discuss these four regions separately.

Then, we observe that the points in Regions II and IV are unstable and will move into Region I or III with large probability. In Regions I and III, the strategy will move close to the stationary point with large probability. Therefore, regardless where the initial point is, the updating rule in (5) will converge to a stationary point with large probability.

In this section, we prove the convergence of the -learning of the proposed Aloha-like spectrum access with Boltzman distributed exploration. First, we find the equivalence between the updating rule (5) and Robbins-Monro iteration [25] for solving an equation with unknown expression (a brief introduction is provided in Appendix ). Then, we apply a conclusion in stochastic approximation [14] to relate the dynamics of the updating rule to an ODE and prove the convergence of the ODE.

It is well known that, in partially observable Markov decision process (POMDP) problems, the belief on the system state, that is, ( is the observation history before period ), can play the role of system state. Due to the special structure of the game, we can define the state of secondary user at period as

where , , means the number of consecutive periods during which channel has not been sensed before period (e.g., if the last time that channel was sensed by secondary user is time slot , .) and is the state of channel in the last time when it is sensed before period .

For the purpose of learning, we define the objective function for user as the discounted sum of rewards in each spectrum access period with discount factor , that is,

Then, to maximize the objectively function, the corresponding -learning strategy is given by [23]

where is uniquely determined by and , and is the step factor dependent on the time, channel, user, and belief state. Note that is the system state in the next time slot, which is random. Intuitively, the new -value is updated by combining the old value and the new estimation, which is the sum of the new reward and discounted old -value.

Similarly to the complete information situation, we have the following proposition which states the convergence of the learning procedure with partial information and large . The proof is given in Appendix . Note that numerical simulation shows that small also results in convergence. However, we are still unable to prove it rigorously.

Proposition 2.

When is sufficiently large, the learning procedure in (19) converges.

Figures 5 and 6 show the dynamics of versus (recall that and ) of several typical trajectories for the state of both channels being idle when . We assume that for all and . Note that in Figure 5 and in Figure 6. We observe that the trajectories move from unstable regions (II and IV in Figure 4) to stable regions (I and III in Figure 4). We also observe that the trajectories for smaller temperature is smoother since less explorations are carried out.

Figure 7 shows the evolution of the probability of choosing channel 1 when , and both channels are idle. We observe that both secondary users prefer channel 1 at the beginning and soon secondary user 1 intends to choose channel 2, thus avoiding collisions.

In this subsection, we consider the performance of reward averaged over all system states. When , we set and for the three channels, respectively. When , we use the first two channels in the case of . The rewards of different channels for different secondary users are randomly generated with a uniform distribution between . The CDF curves of performance gain, defined as the difference of average rewards after and before the learning procedure, are plotted in Figure 8 for both and . Note that the CDF curves are obtained from 100 realizations of learning procedure. From a CDF curve, we can read the distribution of the performance gains. For example, for the curve , performance gain 0.4 in the horizontal axis corresponds to 0.6 in the vertical axis; this means that around 60% of the secondary users obtain performance gain less than 0.4. We observe that when , most performance gains are positive. However, when , a small portion of the performance gains are negative, that is, the performance is decreased after the learning procedure. Such a performance reduction is reasonable since Nash equilibrium may not be Pareto optimal. We also plotted the average performance gains versus different and in Figure 9. We observe that larger results in worse performance gain. When is small, smaller yields better performance, but decreases faster than larger when increases. The performance gain over the simple orthogonal channel assignment scheme is given in Figure 10. We observe that the learning procedure generates a much better performance than the simple orthogonal channel assignment.

We define the stopping time of learning as the time that the relative fluctuation of average reward, which is obtained from 2000 spectrum access periods using the current -values, has been below 5 percent for successive 5 time slots. That is, compute the relative fluctuation at time slot using

where is the vector containing all -values and the norm is 2-norm. Then, when is smaller than 0.05 for 5 consecutive times, we claim that the learning is completed. Then, the learning delay is the time spent before the stopping time. Obviously, the smaller the learning delay is, the faster the learning is. Figures 11 and 12 show the delays of learning, which characterizes the learning speed, for different learning factor and different temperature , respectively, when . The original values are randomly selected. When the probabilities of choosing channel 1 are larger than 0.95 for one secondary user and smaller than 0.05 for the other secondary user, we claim that the learning procedure is completed. We observe that larger learning factor results in smaller delay while smaller yields faster learning procedure.

The speed of learning is compared for , and in Figure 13 (both and are fixed). We observe that, for more than 90% of the realizations, the learning can be completed within 20 spectrum access periods. However, the learning procedure may last for a long period of time for some situations. We can notice that the learning speeds are similar for cases and . We also observe that, when is much larger ( ), the increase of delay is not significant.

In previous simulations, the rewards of successfully accessing channels, are assumed to be constant. In practical systems, they may change with time since wireless channels are usually dynamic. In Figure 14, we show the CDF of performance gains (the configuration is the same as that in Figure 8) when channel changes slowly. We used a simple model for channel reward, which is given by

where is a random variable uniformly distributed between 0 and 1. From Figure 14, we observe that the learning algorithm still improves the performance significantly.

Figure 15 shows the performance gain of learning in the case of partial observations. We adopt the -learning mechanism introduced in Section 5. Note that there are infinitely many belief states since a channel could be unsensed for an infinite period of time. For computational simplicity, we set all to (recall that is the period of time that channel has not been sensed by user before time ). From Figure 15, we observe that the performance is actually degraded for around 40% ( ) or 50% ( ) cases. However, the amplitude of performance degradation is averagely less than the amplitude of performance gain. We also observe that the performance gain is decreased when is increased from 2 to 3.

The learning delay for the partial observation case is shown in Figure 16, where the simulation setup is similar to that of Figure 13. Again, we observe that the learning speeds of and are similar to each other.