1

Accelerated Reinforcement Learning Algorithms
with Nonparametric Function Approximation for
Opportunistic Spectrum Access

arXiv:1706.04546v1 [] 14 Jun 2017

Theodoros Tsiligkaridis, Member, IEEE, David Romero

Abstract—We study the problem of throughput maximization by predicting spectrum opportunities using reinforcement
learning. Our kernel-based reinforcement learning approach is
coupled with a sparsification technique that efficiently captures
the environment states to control dimensionality and finds the
best possible channel access actions based on the current state.
This approach allows learning and planning over the intrinsic
state-action space and extends well to large state and action
spaces. For stationary Markov environments, we derive the optimal policy for channel access, its associated limiting throughput,
and propose a fast online algorithm for achieving the optimal
throughput. We then show that the maximum-likelihood channel
prediction and access algorithm is suboptimal in general, and
derive conditions under which the two algorithms are equivalent.
For reactive Markov environments, we derive kernel variants of
Q-learning, R-learning and propose an accelerated R-learning
algorithm that achieves faster convergence. We finally test our
algorithms against a generic reactive network. Simulation results
are shown to validate the theory and show the performance gains
over current state-of-the-art techniques.
Index Terms—Reinforcement Learning, Opportunistic Spectrum Access, Channel Access Policy, Kernel, Throughput Maximization.

I. I NTRODUCTION
The FCC has recognized that conventional static spectrum
allocation methods lead to spectrum being under-utilized [1].
RF spectrum is a highly valued commodity; 65MHz of spectrum was auctioned in the US (AWS-3) for $40B. The FCC
realizes the huge demand for spectrum and its inefficient use
today, and is creating the Innovation Band around 100MHz
wide at 3.5GHz to allow cognitive radios to access spectrum
there opportunistically. Currently, there is no established cognitive solution for use of this band, providing an opportunity
for researchers to shape how spectrum is utilized in the future.
The need for intelligent algorithms for autonomous spectrum
and power allocation across different nodes in networks has
been growing in the last decade. Opportunistic spectrum access
(OSA) can be used to efficiently exploit spectrum opportunities
by allowing secondary users (SU) to find and access parts
of the spectrum such that they cause limited interference to
This material is based upon work supported under Air Force Contract
No. FA8721-05-C-0002 and/or FA8702-15-D-0001. Any opinions, findings,
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the U.S. Air Force.
Approved for Public Release, Distribution Unlimited.
T. Tsiligkaridis and D. Romero are with MIT Lincoln Laboratory, Lexington, MA 02421 USA (email: {ttsili,dlr}@ll.mit.edu).

primary users (PU) [2]. OSA has become important recently
as spectrum bands are becoming more congested.
In OSA, nodes within a cognitive radio network (CRN)
collect spectrum data and must find efficient ways to access
spectrum while avoiding collisions with other networks in realtime. Much of the current literature on OSA deals with its
underlying CRN architecture and implementation [3], [4], [5],
[6], [7], performance optimization and MAC protocol design
[8], [9], [10], [11], [12], [13], but little effort has been given to
developing learning-based approaches that are both effective
and practical when dealing with exploiting opportunities in
unknown RF environments that are capable of reacting to
transmission actions being taken.
Many of the proposed learning algorithms based on hidden Markov models, neural networks, and other predictive
models tend to require a prohibitive amount of computational
resources to train, often require periodic retraining, and may
require a very large number of parameters to capture relevant
communication environments [14], [15]. Furthermore, even
state-of-the-art deep learning models are sensitive to noise
[16] and adversarial actions [17]. These problems prohibit the
use of these algorithms in practical environments due to the
amount of data and tight latency requirements. For spectrum
prediction and exploitation, this data must be analyzed in realtime to be valuable for decision making.
In this paper, we develop novel machine learning algorithms to enable autonomous learning and increase spectrum
efficiency in unknown and dynamic RF environments. The
dynamic nature of the RF environment covers cases when
taking actions lead to changes in the RF environment, i.e.,
colliding with a PU may force the PU to move to a different
frequency band or backoff its data rate. Reinforcement learning
(RL) provides a natural framework for model-free optimization
with the goal of learning optimal channel access policies, in
which radios learn by direct interaction with the environment.
RL has been proposed for cognitive radio networks in the
context of cooperative sensing [18], interference control [19],
optimization of queueing systems [20], and spectrum management [21].
To learn a good spectrum access policy, radios must balance
the exploration of the space of states and actions with the
exploitation of an already learned policy [22]. The radios use
acquired knowledge to choose actions (e.g., which channel
to access) that maximize a cumulative reward (e.g., data rate).
Learning a policy directly by interacting with the environment
has the potential of providing adaptation capabilities and

2

significant savings in terms of computational complexity. This
is coupled with a kernel-based framework for dimensionality
reduction to capture the essential features of the communication environment. The advantages of this approach is that it
is adaptive, flexible, and has low complexity. The approach
is illustrated in Fig. 1. The algorithms developed in this
Agent

The blue receiver is observing the states of a communication
environment, st ∈ S, which are power measurements of the
received signals. We assume the available bandwidth is divided
into K channels and the receiver can sense the full band
yielding a state st ∈ RK
+ at each time instant. We assume
that in the noiseless case, the state space S is finite. We also
assume full-duplex operation 1 .

Action

State

࢙࢚

A. State Space

Prediction &
Decision Making

Learning

Reward/Quality Level

࢚࢘

ࢇ࢚

Channel
Access

࢚࢘ା૚

RF Environment

State

Spectrum Sensing

࢙࢚ା૚

Signal
Processing

Fig. 1: Overview of reinforcement learning approach for opportunistic spectrum access.

work may also be useful for prediction in high-dimensional
data, adaptive sensing, robotics and adaptive stochastic control
problems.

B. Action Space
We assume, for simplicity, that the blue link is constrained
to access one of the K channels at each time, and makes
decisions at ∈ A about which channel to access based on the
current state st . The action being taken at affects in general
the evolution of the states. Of course, this assumption can be
relaxed and the methods presented in the paper are still valid
as long as the action space is parameterized appropriately.
In the most general case where the blue link is capable of
accessing up to Ka out of K channels at each time, action can
be represented
 binary vectors in a space A of dimension
PKa Kas
|A| = k=1
k .
C. Transition Model
Under this dynamic model, the probability of being in the
next state depends only on the current state st and the action
taken at , i.e.,

A. Outline
The paper is organized as follows. The problem is formulated in Section II and the nonparametric function approximation modeling approach is described. Section III describes
the dimensionality reduction algorithm and contains analysis
that guides the selection of the kernel and approximation
parameters. Section IV contains the performance analysis for
the case of stationary Markov environments. Several kernel
reinforcement learning algorithms are derived in Section V
including the novel generalization of R-learning. Finally, numerical experiments are included in Section VI.

Pi,j (a) = P (st+1 = j|st = i, at = a)
For stationary environments the transitions do not depend on
the actions, i.e., Pi,j (a) = Pi,j for all a ∈ A. To model
reactive/adaptive environments, the transitions will depend on
the actions being taken in general. We note that if the states
evolve as a higher-order Markov chain, a new state space of
higher dimension may be defined as first-order Markov and
the same techniques may be applied.
D. Reward Model

II. P ROBLEM F ORMULATION
We formulate the problem in the Markov decision process
(MDP) context. We use the MDP (S, A, R, P) to represent
the dynamic communication environment of the green network
(see Fig. 1), where S is the state space, A is the action space,
R is the reward function and P is the state-transition matrix.
The policy of the MDP is a function π : S → A that maps state
to actions. In the sequel we’ll refer to secondary users as the
blue cognitive network and primary users as the green network.
The objective of the blue cognitive network is to find a channel
access policy that maximizes its throughput while operating in
the presence of and avoiding collisions with a green network.
For simplicity, we consider a single blue receiver which may
be used to model a single user link or a centralized controller
that distributes a channel access schedule to user pairs via
a control channel assuming all blue nodes are experiencing
similar path losses.

The reward obtained when transitioning to state st+1 as a
result of taking action at in state st is given by the number
of bits received successfully as a result of a single channel
access and can be measured by an acknowledgment in practice.
If the bit packet fails to be successfully received, a zero or
negative reward is incurred due to the sensing overhead and
the resulting collision with the green network. This can be
written as:
(
R(at ), if channel at is idle at state st+1
rt =
−Cs ,
else
where R(a) is the number of bits successfully received when
using channel a, which is upper bounded by the channel capacity. Note that we make the assumption that all packet losses
for the blue network are due to channel access collisions.
1 The techniques can be extended to half-duplex by splitting each slot into
a sensing and accessing time period.

3

E. Noise Modeling
In practice, there will be noise due to the receiver which
makes the true states unobservable. The observation model in
a AWGN channel over a subband k at time t is:
yt (k) = zt (k) + wt (k)
where wt (k) is complex-valued white Gaussian noise with
variance E|wt (i)|2 = σn2 . The true power level is |zt (k)|2 and
the noiseless state-vector is pt = [|zt (1)|2 , . . . , |zt (K)|2 ]T .
Taking the power measurement of yt (k) and assuming independence between the transmitted signal and noise, we obtain:
st = pt + nt
where nt = [|wt (1)|2 , . . . , |wt (K)|2 ]T . The noise distribution
is exponential for each subband k, and due to independence
across subbands, the multivariate distribution factors as
f (n) =

K
Y
1 −n(k)/σn2
e
I{n(k)≥0}
σn2

φ is unknown, all the computations can be performed in terms
of inner products. We use the exponential kernel in this paper,
0 2
k
i.e., k(x, x0 ) = exp( −kx−x
), although other kernels may
2σ 2
also be used in our approach.
The RL algorithms in this paper all have the same general
form (see Fig. 1):
(a) Choose action at based on -greedy policy, i.e.,
(
arg maxa∈A Qt (st , a) + Ht (st , a), w.p. 1 − 
at =
∼ unif(A),
w.p. 
P
where Qt (st , a)
=
=
l αl k((st , a), (sl , al ))
αTt kt ((st , at )),
kt ((s, a))
=
[k((s, a), (s1 , a1 )), . . . , k((s, a), (sL , aL ))]T is a kernelbased vector, and Ht (st , a) is a penalty function whose
effect asymptotically vanishes, i.e., limt→∞ Ht (s, a) = 0.
(b) Take action at , observe reward rt and next state st+1
(c) Update state-action value function coefficients in expansion (2):

k=1

The noise in our power measurements st is highly nonGaussian and concentrated on the positive orthant of the Kdimensional channel space.

αt+1 = αt + ηt (rt + ft − Qt (st , at )) kt ((st , at ))
where ft is a term that may depend on αt and st+1 , and
ηt > 0 is a step size parameter.

F. Reinforcement Learning with Nonparametric Function Approximation

III. D IMENSIONALITY R EDUCTION

The objective is to find the optimal policy π ∗ that maximizes
the long-term reward. The state-action value function may be
defined to maximize the discounted cumulative reward:
"∞
#
X
π
π
t
Q (s, a) = E
γ rt s0 = s, a0 = a

A major issue that needs to be addressed when using the
nonparametric model (2) is how to control its complexity
without losing important information. The number of terms
in the expansion (2) grow as the time horizon increases,
making computational complexity intractable and reducing
generalization performance.
We describe an online sparsification technique for deciding
which terms to ignore and which terms to keep in the series expansion using approximate linear dependence (ALD) analysis
[24], [23]. ALD analysis is a method for sequentially building
a dictionary D of representative feature vectors φ(xi ) =
φ((si , ai )). When a state-action pair x = (s, a) is observed the
ALD criterion is used to determine whether the corresponding
feature vector φ((s, a)) can be well approximated as a linear
combination of feature vectors already included in D. To
understand more concretely how ALD is used in our approach,
let the dictionary after testing t − 1 samples be given by
Dt−1 = {xj = (sj , aj ) : j = 1, . . . , Lt−1 }. Given the new
datum xt = (st , at ), the test for whether to include xt in the
dictionary becomes:

t=0

or to maximize the long term average reward:
#
"
T
1X
π
π
rt s0 = s, a0 = a
Q (s, a) = lim E
T →∞
T t=0
The optimal state-action value function is
Q∗ (s, a) = max Qπ (s, a)
π

(1)

and the optimal policy is obtained as:
π ∗ (s) = arg max Q∗ (s, a)
a∈A

We adopt the framework of reinforcement learning with
function approximation. Consider a data set generated from
the MDP {(st , at , st+1 , rt )}Tt=1 using the -greedy exploration
method. Using the kernel-based approach of [22], [23], we
model the state-action value functions of the MDP using a
nonparametric nonlinear approximation:
Q(s, a) =

L
X

αl k((s, a), (sl , al ))

(2)

l=1

where k(·, ·) is the kernel function and αl is the coefficient
associated with each state action pair (sl , al ). We remark
that the kernel can be thought of as an inner product in a
Hilbert space H, i.e., k(x, x0 ) = hφ(x), φ(x0 )i, and although
the dimension of H may be infinite and the nonlinear mapping

Lt−1

δt = min k
c

X

cj φ(xj ) − φ(xt ) k2 > µ

(3)

j=1

where µ > 0 is a parameter controlling the approximation
Lt−1
error. Defining the kernel matrix as Kt−1 = {k(xi , xj )}i,j=1
T
and the vector kt−1 (xt ) = [k(x1 , xt ), . . . , k(xLt−1 , xt )] , we
can express the optimal solution to (3) and its corresponding
optimal value as:
ct = K−1
t−1 kt−1 (xt )

(4)
T

δt = ktt − kt−1 (xt ) ct

4

def

where ktt = k(xt , xt ). If δt ≤ µ, then the dictionary remains
the same, i.e., Dt = Dt−1 , otherwise, the new state-action pair
is added and Dt = Dt−1 ∪ {(st , at )}.
If we associate each term in the dictionary with a function
φ(·), where k(x, x0 ) = hφ(x), φ(x0 )i, the set of functions
tends to be approximately linearly independent. This approach
essentially sparsifies the kernel expansion in (2) by keeping
relevant terms while ignoring terms that have been observed
previously in the data stream and, more generally, can be well
approximated by a linear combination of other terms in the
dictionary.

= 1 − 1 − e

A. Dictionary Size & Parameter Selection
It is known that if k(·, ·) is a continuous kernel function
and the state and action spaces are compact, then for any
training sequence {xt = (st , at )}Tt=1 and for any positive µ,
the dictionary is finite [24]. In our setting, the action space
is finite but the state space is infinite due to the presence of
noise. However, the exponentially decaying tails of the noise
distribution imply that the observed state space is compact
with high probability.
Next, we provide a few criteria for choosing the parameters
µ and σ. Assume that the states in the kernel domain, i.e.,
{φ(si )}N
i=1 , are linearly independent (and thus distinct).
In the noiseless case, the ALD test should create a new
element if two state-action pairs differ. This occurs iff for all
x1 6= x2 :
2

kφ(x1 ) − φ(x2 )k2 > µ ⇔ 2(1 − k(x1 , x2 )) > µ
2
2
µ
⇔ e−kx1 −x2 k2 /(2σ ) < 1 −
2

1
2
2
⇔ kx1 − x2 k2 > 2σ log
1 − µ2


1
2
2
2
⇔ ks1 − s2 k2 + ka1 − a2 k2 > 2σ log
1 − µ2
This inequality holds if:

min dmin (S)2 , dmin (A)2 > 2σ 2 log



1
1−

def


µ
2

(5)
def

where dmin (S) = mins1 6=s2 ks1 − s2 k2 and dmin (A) =
mina1 6=a2 ka1 − a2 k2 are the minimum distances between two
elements in the state and action spaces, respectively. Given
bounds on the minimum distances in states and actions, we
can choose σ and µ jointly so that the inequality (5) holds.
Next, we consider a benchmark probability for creating a
new element using ALD:


2
pnew = P kφ((p + n, a)) − φ((p, a))k2 > µ
= P (2(1 − k(p + n, p)) > µ)

2
2
µ
= P e−knk /2σ < 1 −
2

K
X
1
=P
n2k > 2σ 2 log
1−
k=1

We would like this probability to be relatively small so that
not too many superfluous dictionary items are created as this
increases computational complexity.
Exact computation of pnew is intractable, but we may upper
bound it as:



1
2
2
pnew ≤ P K max{nk } > 2σ log
k
1 − µ2
s
!

2σ 2
1
= P max nk >
log
k
K
1 − µ2
s

 K


!
µ
2

where n ∈ RK
+ is a random noise vector with independent
exponential random variables nk ∼ Exp( σ12 ) (see Sec. II-E).
n

− σ12

n

2σ 2
K

log

1
µ
1−
2



In order to keep pnew ≤ δ for some small δ > 0 when
operating with receiver noise level σn2 , we can choose σ and
µ to satisfy the condition:




2
1
1
2
2
2σ log
> K σn log
(6)
1 − µ2
1 − (1 − δ)1/K
Equation (6) along with (5) provides
 an acceptable range of
values for the function θ = 2σ 2 log 1−1 µ , and therefore can
2
be used to help choose the parameters σ and µ for a given
scenario.
B. Efficient Recursive Implementation
The ALD test may be recursively implemented by avoiding
a direct inversion of the kernel matrix Kt−1 in (4), which
takes O(L3t−1 ) computational complexity in general.
If δt > µ, then the new state-action pair xt = (st , at ) is
added to the dictionary and the kernel matrix is updated by
adding a new row and column:


Kt−1
kt−1 (xt )
Kt =
kt−1 (xt )T
ktt
The matrix inverse is then recursively updated as:


T
1 δt K−1
−ct
t−1 + ct ct
K−1
=
t
−cTt
1
δt
with initial value K−1
= [ k111 ]. When implemented using
1
the recursive update, computational complexity to perform the
ALD test is reduced to O(L2t−1 ).
IV. P ERFORMANCE A NALYSIS FOR S TATIONARY M ARKOV
ENVIRONMENTS

In this section we derive the optimal channel access policy
for maximizing throughput in unknown environments that can
be modeled as a stationary Markov chain. We also derive
conditions under which the optimal policy coincides with
the maximum-likelihood prediction-and-access policy which
is suboptimal in general. For concreteness we consider the
noiseless case in this section.
The Markov environments under consideration in this section can be fully characterized by two parameters; the transition probability matrix P = {Ps,j } ∈ [0, 1]N ×N and the
connectivity matrix that associates idle channels to states,

5

A = {Aj,a } ∈ {0, 1}N ×K . To aide in our exposition define
Tj for j ∈ {1, · · · , N } as sets of indices corresponding to
channels that are idle when the system is in state j. Thus,
Aj,a = I{a∈Tj } where I{·} is the indicator function. This is
graphically illustrated in Figure 2.

Theorem 2. Assume all channels have the same capacity, i.e.,
Ca = C.The optimal decision rule makes the same channel
access decisions as the ML prediction-and-access algorithm,
and thus achieves the same limiting throughput iff:

j1
j2
a1
s

j3

a2

aK

jN

P






X


X
Ps,j Aj,a ,
Ps,j Aj,a > max
max Ps,ms +
a∈Tms 

 a∈T
/ ms 

.
.
.

.
.
.

According to Theorem 1, this ML policy achieves a suboptimal throughput. Theorem 2 shows that under some
stochastic dominance assumptions, the ML policy coincides
with the decisions made by the optimal policy π ∗ (s) =
maxa {Ca hPs,· , A·,a i}.

j6=ms

j6=ms

∀s ∈ S

A

NxN

NxK

Fig. 2: Graphical model for state transition s → j determined
by transition matrix P and connectivity matrix A associating idle
channels (corresp. actions) to states.

def

(8)

def

where Tms = {a : Ams ,a = 1} and ms = arg maxj∈S Ps,j .
Proof: See Appendix B

Presentation Name - 1
Author Initials MM/DD/YY

The following theorem derives the structure of the optimal
policy for average throughput maximization.
Theorem 1. Assume the underlying Markov chain has a finite
state space and is irreducible. Let the expected reward after
accessing an idle channel a be given by Ca . Consider a
randomized policy π q (s) given by:
P(π q (s) = a) = qa (s)
Consider
the
deterministic
policy
π ∗ (s)
=
maxa {Ca hPs,· , A·,a i}. Then, the policy π ∗ is optimal
and achieves the limiting throughput:
#
"
T
1X
q
πq
Thr(π ) = lim E
rt
T →∞
T t=1
X X
=
πs
qa (s)Ca hPs,· , A·,a i
s∈S

≤

X
s∈S

Next, we derive expressions for the limiting throughput for
the ML prediction-and-access algorithm.
Theorem 3. Assume the underlying Markov chain has a finite
state space and is irreducible. Consider the ML predictionand-access algorithm which chooses a channel a ∈ Tms with
probability qms (a) when the system is in state s. Let the
expected reward after accessing an idle channel a be given
by Ca . The limiting throughput is:
T
1X
rt
T →∞ T
t=1
X 
X
a.s.
qms (a)Ca
=
πs Ps,ms

Thr = lim

s∈S

+

a

πs max {Ca hPs,· , A·,a i} = Thr(π ∗ )
a

a∈Tms

X
j6=ms

Ps,j

X

qms (a)Ca



(9)

a∈Tj ∩Tms

(7)

where π is the stationary distribution of the Markov chain,
i.e., π = πP.
Proof: See Appendix A
We note that Theorem 1 can be generalized to arbitrary
action spaces (see Sec.II.B). Theorem 1 provides an
upper bound on the average throughput for stationary
ergodic Markov environments and characterizes the average
throughput optimal policy in terms of an inner product
between the rows of P and the columns of A.
Another method for choosing an idle channel is the twostage maximum likelihood (ML) prediction-and-access approach:
1) Choose most likely channel to transition to, i.e., ms =
arg maxj Ps,j
2) Choose an idle channel a associated with state ms , i.e.,
a ∈ Tms

where π is the stationary distribution of the Markov chain,
i.e., π = πP.
The proof of Theorem 3 is similar to the proof of Theorem 1.
The following corollary shows special cases of the ML
prediction-and-access decision rule in terms of the statetransition matrix P and the state-connectivity matrix A. This
result will be used in Section VI to match the empirical results
to the theoretical prediction of the throughput.
Corollary 1. The following special cases hold for the ML
prediction-and-access decision rule:
•

def

For the case qs (a) = I{a=a∗ (s)} , where a∗ (s) =
arg maxa∈Tms Ca , the expression (9) simplifies to:




Thr =

X
s∈S


πs max {Ca }·Ps,ms +
a∈Tms

X
j6=ms


Ps,j I{a∗ (s)∈Tj } 
| {z }
=Aj,a∗ (s)

6

•

For the case when all rewards are equal, i.e., Ca = C,
1
and qs (a) = |Tm
I{a∈Tms } , the expression (9) becomes:
s|


X
X
|T
∩
T
|
j
ms 
Ps,j
Thr = C
πs Ps,ms +
|Tms |
s∈S
j6=ms
PK
XX
a=1 Aj,a Ams ,a
=C
πs Ps,j · P
K
a=1 Ams ,a
s∈S j∈S
V. A LGORITHMS

A. Count-based Learning Algorithm
Motivated by the inner-product based optimal decision rule
derived in Theorem 1, we propose a recursive count-based
learning (CBL) algorithm. CBL attempts to construct the
optimal state-action value function (1) using the form given in
(2). We show in Theorem 4 that the algorithm asymptotically
achieves the optimal throughput given in Theorem 1. The
performance of CBL is illustrated using simulation in Section
VI-A.
During an initial training period the dictionary of stateaction pairs is built using ALD analysis. The αl corresponding
to each state-action pair in the dictionary can be computed as:

where I{a∈Tj } can be computed by observing state st = j, and
rt is the reward obtained as a result of taking action at−1 in
state st−1 . The storage complexity of this update is O(L) and
the computational complexity is O(|A|), which means that the
overall complexity of the algorithm is still dominated by the
ALD test.
The recursion (13) can alternatively be written in terms of
a stochastic approximation update:


αt+1 = αt + diag(Nt )−1 rt − αTt kt ((st , at )) kt ((st , at ))
(14)
When there is noise present in the channel, a small step size
η > 0 may be used:


αt+1 = αt + η rt − αTt kt ((st , at )) kt ((st , at ))
(15)
The following theorem shows that the CBL decision rule
asymptotically achieves the optimal throughput.

def

αl = α(s,a)
X
= Ca
Ps,j

Ni (t) = Ni (t − 1) + 1
(12)
α(i,a) (t − 1)Ni (t − 1) + rt I{a∈Tj }
,a ∈ A
α(i,a) (t) =
Ni (t)


rt
1
=
I{a∈Tj } + 1 −
α(i,a) (t − 1)
Ni (t)
Ni (t)
(13)

(10)

j:a∈Tj

where Tj = {a : Aj,a = 1} is the set of channels that are
idle when the system is in state j, and Ps,j is the probability
corresponding to the state transition s → j. Because the radio
doesn’t have access to the transition statistics of the Markov
Chain, Ps,j in (10) is replaced by its maximum likelihood
estimate:
X Ns,j
α(s,a) = Ca
Ns
j:a∈T
P j
j:a∈Tj Ns,j
= Ca
(11)
Ns
where Ns,j is the number of observed transitions s → j,
and Ns is the number of observed occurrences of state s.
Neglecting the ALD test, a straightforward implementation of
this algorithm has per-step computational complexity O(L)
and storage complexity O(N 2 ) where N is the number of
unique states in the dictionary, L ≤ |A|N is the total number
of entries in the dictionary and |A| is the cardinality of the
action space. Overall computational and storage complexity
are dominated by the ALD test described in Section III-B,
pushing both to O(L2 ).
Because we are interested only in choosing actions and not
directly learning P, we recursively compute (11) and avoid
the intermediate step of estimating and storing the transition
matrix as follows. Assume the states (st−1 , st ) = (i, j) are
observed. Updating the αl ’s at time t requires updating Nj ,
Ni,j and their dependent αl ’s. Assuming a 1-step latency is
acceptable, these updates can be efficiently implemented using
the following pair of recursive equations:

Theorem 4. Let the minimum distance between states in the
dictionary be given as dmin (S) = mins0 6=s ks−s0 k. Fix δ > 0
to be arbitrarily small, and assume:
σ2 ≤

dmin (S)2

2 ln N δ−1

(16)

The count-based learning decision rule chooses channel access actions based on the following rule asymptotically:
π(s) = arg max {hPs,· , A·,a i + a }
a∈A

(17)

where a ∈ [0, δ]. Here, Ps,· is the s-th row of the transition
probability matrix P and A·,a is the a-th column of the stateaction connectivity matrix A.
Proof: See Appendix C
We note that while not pursued in this paper, Theorem 4 can
be generalized to arbitrary action spaces.
B. Kernel Q-Learning
The Q-learning algorithm [22] seeks to find the policy π(·)
that maximizes the discounted cumulative reward:
"∞
#
X
π
t
E
γ rt
t=0

where γ ∈ [0, 1) is the discount parameter. This criterion
models rewards received sooner as being more important than
rewards received later. The Q-learning algorithm estimates the
optimal state-action value function Q∗ using the stochastic
approximation:


0
Qt+1 (st , a) = Qt (st , a)+η rt +γ max
Q
(s
,
a
)−Q
(s
,
a
)
t
t+1
t
t
t
0
a

7

Algorithm 1 Kernel R-Learning Algorithm (KRL)
Input: step sizes η, β
Initialize ρ0 = 0
for t = 1, . . . , T : do
(a) Choose action at based on -greedy policy, i.e.,
(
arg maxa∈A αTt kt ((st , a)), w.p. 1 − 
at =
∼ unif(A),
w.p. 
(b) Take action at , observe reward rt and next state st+1
(c) Update policy

 T
αt+1 = αt−1 + η rt − ρt + max
αt kt ((st+1 , a0 ))
0
a

− αTt kt ((st , at )) kt ((st , at ))
(d) Update average expected reward per time step:
if αTt kt ((st , at )) = maxa αTt kt ((st , a)) then

ρt+1 = ρt + β rt − ρt + max
αTt kt ((st+1 , a0 ))
a0

− max αTt kt ((st , a))
a

else
ρt+1 = ρt
end if
end for

D. Generalized Kernel R-Learning
The CBL method computes a set of coefficients αt using (15) to maximize the single-stage expected reward. To
speed up learning, we may choose actions by maximizing the
difference between the R-learning and CBL value functions.
Of course, in order for the modified algorithm to approach
the solution obtained with R-learning, the effect of the CBL
single-stage value function in the decision making is damped
down by the number of times that action has been chosen when
the system is in that state, Nt (st , a). This idea of guided action
selection to maximize the future reward when in the transient
regime has the potential of speeding up convergence.
In our proposed Generalized Kernel-based R-Learning
(GKRL) approach actions are chosen as:
o
n
(
e T k ((s ,a))
α
arg maxa αTt kt ((st , a)) − Ntt (stt ,a)t1+ζ It+ , w.p. 1 − 
at =
∼ unif(A),
w.p. 
where ζ ≥ 0,
(
def

It+ =

def

Nt (st , a) =

e Tt kt ((st , a))} ≥ 0
1, maxa {αTt kt ((st , a)) − α
,
0, else
X
cntst (s0 , a0 )

(s0 ,a0 )∈Dt :ks0 −st k<δ,a0 =a

In the kernel setting, the Q-learning iteration becomes:

 T
αt+1 = αt + η rt + γ max
αt kt ((st+1 , a0 ))
a0

− αTt kt ((st , at )) kt ((st , at ))
C. Kernel R-Learning
To maximize throughput, we want to maximize the following undiscounted average reward:
n

1X π
E [rt ]
n→∞ n
t=1

ρπ = lim

instead of the discounted cumulative reward. For γ approaching 1, this maximization approaches the average cost criterion.
The R-learning algorithm of Schwartz [25] maximizes the
average adjusted sum of rewards:
Qπ (s, a) =

∞
X

Eπ [rt+k − ρπ |st = s, at = a]

k=1

It is based on iteratively solving for a fixed point of the
Bellman equation [26]
X
Q∗ (s, a) + ρ∗ = r(s, a) +
Ps,s0 (a) max
Q∗ (s0 , a0 )
0
s0

a

where ρ∗ is the average reward for the optimal policy. The
stochastic approximation algorithm is shown in Alg. 1 for
the kernel setting. A numerical study comparing Q-learning
with R-learning was conducted in [27] and it is shown that
R-learning can outperform Q-learning.

e t is the vector of coefficients computed using (14). Here,
and α
cntst (st , a) estimates the number of times action a has been
chosen when the system is in state st and is computed as:
cntst (s, a) =

t
X

k((si , ai ), (s, a))

i=1

for all (s, a) pairs in the dictionary. The threshold δ is based
on the noise variance and attempts to cluster similar states.
We remark that in the large sample regime, we expect
Nt (st , a) → ∞ and the GKRL method behaves identically as
KRL. However, in the transient regime where most learning
occurs on startup, the algorithm seeks to choose actions that
maximize the gap between the expected long-term average
reward and the expected myopic reward.
VI. N UMERICAL E XPERIMENTS
A. Simulated Data
1) Setup: To compare the performance of the proposed
algorithms we simulate a scenario in which a pair of fullduplex blue cognitive network radios attempt to operate in
the presence of K green network radio links. We assume
that the green network is non-cooperative with the blue
network. Each of the K green links consists of a pair of
transceivers communicating over a channel with line-of-sight
(LOS) propagation loss. The K channels are assumed to be
non-overlapping in frequency and each has of bandwidth of
W Hz. We make the simplifying assumption that the channels
can be decomposed into time slots of duration Tslot . Each of
the blue network radios is constrained to access the one of the
same K W Hz channels being used by the green network and
must attempt to minimize collisions. Blue and green network

8

Description
number of available channels
bandwidth of each channel
maximum data rate of each link
channel access duration
green network transmit power

TABLE I: Parameters used in numerical experiments

Possible States
-35

1
-40

2

-45

-50

3

radios are assumed to operate at a rate of R bits/sec2 when no
collisions occur. The values of each of the parameters chosen
for our numerical experiments are summarized in Table (I).
Throughout our experiments the radio links are configured in
a particular randomly generated physical layout as shown in
Figure (3).

-55

Rx Power (dBm)

Value (units)
5 (links or channels)
1.2 (MHz)
600 (kbits/sec)
1.5 (ms)
20 (dBm)

Frequency (channel ID)

Parameter
K
W
R
Tslot
Pgtx

-60

4

-65

5
-70

1

2

3

4

5

6

7

8

9

10

State ID

Fig. 4: The channel is modeled as a 1st-order Markov Chain with
300

10 possible channel states. The columns of the above image illustrate
each of these states as observed at the blue network receiver.

Tx of interest
Rx of interest
Interfering radio

200

Link 1
Link 2
Link 3

100

Link 4

meters

Link 5

0

-100

-200

-300
-300

-200

-100

0

100

200

300

meters

Fig. 3: Physical layout of the blue and green networks. Each link
is denoted by a line connecting a transceiver pair. The states are
generated assuming line-of-sight pathloss between each of the green
network radios and the blue network receiver of interest.

For our simulations the composite channel evolves in time
according to a ergodic first-order Markov Chain over 10
randomly generated states. The state space is shown in Figure
(4).
Prior to being processed by any of the learning algorithms,
the observed power measurements are normalized by mapping
them to the unit interval. This helps with numerical stability.
We characterize performance of each algorithm in both
stationary and reactive settings. In the stationary case, the
green network is not affected by the actions being taken
by the blue network, while for the reactive case, the green
network adapts to the blue network’s actions. We compare
our algorithms with collision avoidance (CA) which consists
of sensing, finding an idle channel and accessing it in the next
time slot.
2) Performance: The metric we use is the average throughput as a function of training time, which characterizes the
learning performance of each algorithm. In our simulation,
each sample corresponds to 1.5ms. Monte Carlo simulations
are performed where the training set was generated randomly
over many trials, and for each trial the optimal policy was
learned using the nonparametric learning techniques developed
2 Specifically, each radio operates at the Nyquist rate of its respective
channel using a 1/2 rate code and antipodal signaling.

and performance was averaged over many trials on heldout sets
to obtain the average throughput.
a) Stationary Case: We compare the CBL method with
maximum-likelihood (ML) prediction and access. We consider
the transition probability matrix P shown in Fig. 5. Each
row if this matrix consists of a singel dominant probability
of jumping to some randomly chosen next state while the
remaining probabilities are uniformly chosen to sum to unity.
Fig. 6 shows the achievable throughput as a function of
training time for both noiseless and noisy channels. Both
CBL and ML methods outperform CA and CBL achieves the
optimal throughput 366Kbps as expected from Theorem 1,
while ML achieves a suboptimal throughput of 347Kbps. Fig.
0.4

1
0.35

2
3

0.3

4

0.25

5
0.2

6
0.15

7
8

0.1

9

0.05

10
2

4

6

8

10

Fig. 5: Probability transition matrix used for stationary example.
7 shows the histogram of the normalized powers over a block
of noisy data. We note the noise is exponentially distributed
as discussed in Section II-E.
b) Reactive Case: We compare the modified CBL algorithm, Kernel Q-learning (KQL), Kernel R-learning (KRL)
and Generalized Kernel R-learning (GKRL) for the probability
matrices P(a) shown in Fig. 8. These matrices were designed
so that the optimal single-stage reward over two stages is
suboptimal with respect to the optimal two-stage reward. The
optimal
policy here is a two-stage policy given by π ∗ (s) =
P10
5, 5] and the subopk=1 ak I{s=k} , a = [3, 3, 4, 5, 5, 3, 3, 4,P
10
timal single-stage policy is π G (s) =
k=1 bk I{s=k} , b =
[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]. Actions that lead to channel 5 or 10
being chosen are desirable since these two channels have triple

9

the bandwidth of the rest of the channels and thus yield a
higher reward when accessed in an idle state.
Online performance refers to the throughput obtained while
learning which involves taking random actions to explore
with probability , while offline performance refers to the
throughput obtained when actions are chosen based on maximizing the Q function and thus no exploration is performed.
Figures 9 and 10 show the mean and standard deviation of
the throughput when 100 Monte Carlo trials are performed
for the noiseless case. The online performance is lower than
the offline performance because a random action is taken for
exploration with probability  = 0.1 in the former. We observe
that KRL and GKRL both achieve the optimal throughput
1000Kbps, while KQL with γ = 0.99 and CBL only achieve
a throughput of approximately 750Kbps. It is interesting how
even with a γ close to unity, KQL does not achieve the optimal
throughput. Finally, GKRL approaches maximum performance
faster than KRL in both the online and offline settings.
Figures 11 and 12 show the mean and standard deviation
of the average throughput for the case with channel noise. In
this case the receiver of interest observes the green network

Noiseless

B. Reactive MAC Layer Results
In this section, a reactive green network competes with
the blue cognitive network running a reinforcement learning
algorithm and average throughput performance is evaluated.
The green network MAC layer is intuitive and is based on
reacting to the blue network’s actions while at the same time
trying to increase its throughput. The goal of the blue cognitive
radio network is to create and exploit white space opportunities
by learning the behavior of the green network and reacting to
it appropriately to increase its throughput.
The green network’s behavior is outlined in Fig. 13, which
describes the probabilistic evolution of each subchannel. The
green network does not attempt to learn the behavior of the

Noisy

380

Online

360

360

340

340

1000

1000

320

900

900

300

800

800

300
280

CBL
ML
CA
ML (Theory)
Oracle (Theory)

260
240

280

CBL
ML
CA
ML (Theory)
Oracle (Theory)

260
240

220

220

200
2000

4000

6000

600
500
GKRL: 0=0.1
KRL: 0=0.1
CBL: 0=0.1
KQL: .=0.99, 0=0.1
Collision Avoidance

300

200
0

700

400

0

2000

Time (ms)

4000

200

6000

for noiseless and noisy cases. CBL achieves the optimal throughput
as predicted by theory, and ML achieves a suboptimal throughput.
CBL achieves a throughput ×1.7 larger than CA.

600
500
GKRL: 0=0.1
KRL: 0=0.1
CBL: 0=0.1
KQL: .=0.99, 0=0.1
Collision Avoidance

400

200
100

0

0
0

Fig. 6: Stationary case. Throughput as a function of training time

700

300

100

Time (ms)

Offline

1100

Throughput (Kbits/s)

320

1100

Throughput (Kbits/s)

Throughput (Kbits/s)

Throughput (Kbits/s)

380

radios at various signal-to-noise ratios ranging from 11 to
20dB depending on relative pathloss. Both GKRL and KRL
methods achieve the optimal throughput 1000Kbps, while
KQL achieves a throughput of 750Kbps and CBL achieves
a throughput of 800Kbps. We note that even when there is
noise present, GKRL continues to learn faster than KRL.
Furthermore, GKRL has smaller fluctuations around its mean
as it has a lower standard deviation.

10

20

30

40

0

10

Time (s)

20

30

40

Time (s)

Fig. 9: Reactive noiseless case. Mean throughput averaged over
100 trials as a function of time in online (left panel) and offline
(right panel) setting. GKRL outperforms all algorithms in terms of
achievable throughput and learning rate.

12000

Counts

10000
8000

Online

150

6000

GKRL: 0=0.1
KRL: 0=0.1
CBL: 0=0.1
KQL: .=0.99, 0=0.1

4000

0

0.2

0.4

0.6

0.8

1

1.2

Normalized Power

Fig. 7: Histogram of normalized power levels in the presence of
noise.
a=2

a=1

a=3

a=4

2

2

2

2

4

4

4

4

4

6

6

6

6

6

8

8

8

8

8

10

10

10

10

2

4

6

8 10

2

4

6

8 10

2
0

4

6
0.5

8 10

2

4

6

100

50

100

80

60

40

a=5

2

10

GKRL: 0=0.1
KRL: 0=0.1
CBL: 0=0.1
KQL: .=0.99, 0=0.1

120

Standard Dev. (Kbits/s)

0

Standard Dev. (Kbits/s)

2000

Offline

140

8 10

20

0

0
0

10

20

Time (s)
2

4

6

30

40

0

10

20

30

40

Time (s)

8 10

1

Fig. 8: Probability transition matrices used for the reactive example.

Fig. 10: Reactive noiseless case. Standard deviation of throughput
averaged over 100 trials as a function of time. GKRL has the lowest
asymptotic variance.

10

blue network. Instead, the probabilities p and q determine
how the network reacts to interference in each subchannel,
while the probability z determines the likelihood of the green
network beginning to access an idle subchannel when no
interference is present. Note that as (p, q) → (1, 0) the green
network can be characterized as highly competitive, as it
attempts to minimize channel access by blue network radios.
For (p, q) → (0, 1) the network becomes less competitive, as
it is less likely to attempt to block access and more likely to
yield use of a subchannel to a blue network radio.
We consider the case when the blue cognitive network may
access at most two of the K = 5 channels
at a time, yielding

a total number of actions K + K
=
15.
This allows for
2
higher throughput and also allows for the possibility of one
action to be exploratory in nature while the other action is
exploitative. Figure 14 shows the throughput as a function
of training time in the presence of noise. In this simulation,
we used p = 0.2, q = 0.9, z = 0.5 to model the reactive
green network. The GKRL method outperforms all in terms
of throughput when exploring and when not exploring. The
GKRL method asymptotically achieves the highest throughput
of 1020Kbps while the KQL method with γ = 0.99 and

CBL lag significantly behind at 900Kbps. Furthermore, GKRL
achieves a throughput at least ×2 larger when compared to
collision avoidance. Figure 15 also shows that GKRL and
KRL methods achieve the lowest variance asymptotically. It
is interesting that GKRL has a lower variance than KRL
throughout the learning process.
VII. C ONCLUSION
Reactive MAC
Layer
We propose low-complexity
nonparametric
learning algorithms for reinforcement learning over large and continuous
• Model as a set of K independent channels evolving
probabilistically based on the actions being taken
Channel State ࢙࢚

Channel State ࢙࢚ା૚

Action ࢇ࢚

0 (Idle)
Access
1 (Busy)
0 (Idle)
0 (Idle)
Don’t Access
1 (Busy)
0 (Idle)
Access
1 (Busy)
1 (Busy)

૙

0 (Idle)

૚

1 (Busy)

Don’t Access

Machine Learning for Spectrum Operations - 37
Theo Tsiligkaridis 05/25/2017

1000

900

900

800

800

600
500
400
GKRL: 0=0.1
KRL: 0=0.1
CBL: 0=0.1
KQL: .=0.99, 0=0.1
Collision Avoidance

300
200

500
400

200
100
0

20

30

GKRL: 0=0.1
KRL: 0=0.1
CBL: 0=0.1
KQL: .=0.99, 0=0.1
Collision Avoidance

300

0
10

40

1000

900
800
GKRL: 0=0.2
KRL: 0=0.2
CBL: 0=0.2
KQL: .=0.99, 0=0.2

700
600

0

10

20

30

400

Reactive noisy case. Mean throughput averaged over
100 trials as a function of time in online (left panel) and offline
(right panel) setting. GKRL outperforms all algorithm in terms of
achievable throughput and learning rate.

20

40

50

Online

Time (s)

30

40

30

40

50

Standard Dev. (Kbits/s)

100

50

150

100

50

10

20

30

150

GKRL: 0=0.2
KRL: 0=0.2
CBL: 0=0.2
KQL: .=0.99, 0=0.2

100

50

0
10

20

30

Time (s)
0

Offline

200

GKRL: 0=0.2
KRL: 0=0.2
CBL: 0=0.2
KQL: .=0.99, 0=0.2

0

20

20

Time (s)

0

10

10

of reactive green network with MAC layer (see Fig. 13) averaged
over 100 trials as a function of training time. GKRL outperforms all
methods asymptotically.

200

0
0

0

Fig. 14: Mean throughput of blue cognitive network in presence

GKRL: 0=0.1
KRL: 0=0.1
CBL: 0=0.1
KQL: .=0.99, 0=0.1

Standard Dev. (Kbits/s)

Standard Dev. (Kbits/s)

30

Time (s)

Offline

150

GKRL: 0=0.1
KRL: 0=0.1
CBL: 0=0.1
KQL: .=0.99, 0=0.1

0

600

400
10

Fig. 11:

50

GKRL: 0=0.2
KRL: 0=0.2
CBL: 0=0.2
KQL: .=0.99, 0=0.2
Collision Avoidance

700

500

0

100

800

40

Time (s)

Online

900

Collision Avoidance

500

Time (s)

150

Offline

1100

1000

600

100
0

Online

1100

700

Throughput (Kbits/s)

700

st+1 depends on the previous channel state st and the action taken
at .

Standard Dev. (Kbits/s)

Throughput (Kbits/s)

Throughput (Kbits/s)

1000

Fig. 13: Probabilistic MAC layer diagram. The next channel state

Offline

1100

Throughput (Kbits/s)

Online

1100

40

50

0

10

20

30

40

50

Time (s)

40

Time (s)

Fig. 12: Reactive noisy case. Standard deviation of throughput
averaged over 100 trials as a function of time. GKRL and KRL have
the lowest asymptotic variance.

Fig. 15: Standard deviation of throughput of blue cognitive network
in presence of reactive green network with MAC layer (see Fig.
13) averaged over 100 trials. GKRL achieves the lowest asymptotic
variance.

11

state spaces. For stationary environments, we also derive
bounds on the achievable throughput and derive conditions
under which the maximum-likelihood prediction achieves
the optimal performance. Kernel variants of Q-learning, Rlearning were derived, in addition to a novel accelerated Rlearning algorithm for learning optimal channel access policies
in reactive environments. Simulation results show the benefits
of our approach over Q-learning and collision avoidance
schemes.
A PPENDIX A
P ROOF OF T HEOREM 1
Proof. Since the Markov chain is irreducible with finite state
space, it is also positive recurrent and a stationary distribution
π exists and is the unique solution to π = πP. The average
reward under policy π q after T steps is given by:
#
"
T
T
X
q
q
1 XX
1
rt =
I{st =s} Eπ [rt |st = s]
Eπ
T t=1
T t=1
s∈S

=

=

T
X
1 XX
Ps,j E[rt |st = s, st+1 = j]
I{st =s}
T t=1 s
j
T
X
1 XX
I{st =s}
Ps,j
T t=1 s
j
X
×
qa (s)E[rt |st = s, at = a, st+1 = j]
a

T
X
X
1 XX
I{st =s}
Ps,j
qa (s)Aj,a Ca
=
T t=1 s
a
j
!
T
X
X
X 1X
I{st =s}
Ps,j
=
qa (s)Aj,a Ca
T t=1
s
a
j

s. From Theorem 4, the optimal decision rule chooses an
action that maximizes the inner product hPs,· , A·,a i. Notice
the following:
X
Ps,j Aj,a , for a ∈ Tms
hPs,· , A·,a i = Ps,ms +
j6=ms

X

hPs,· , A·,a i =

Ps,j Aj,a ,

for a ∈
/ Tms

j6=ms

Under the conditions (8), the maximum inner product decision
rule (17) always chooses an action a ∈ Tms , which coincides
with the ML decision rule.
Next suppose that (8) isnviolated for a particular ostate
P
s ∈ S. Then, maxa∈Tms Ps,ms + j6=ms Ps,j Aj,a
≤
nP
o
maxa∈T
/ ms
j6=ms Ps,j Aj,a , and the inner product decision rule (17) may yield an a ∈
/ Tms . Thus, the converse also
holds. The proof is complete.
A PPENDIX C
P ROOF OF T HEOREM 4
Proof. The coefficients converge to:
X
X Ns,j
→
Ps,j = hPs,· , A·,a i
α(s,a) =
Ns
j:Aj,a 6=0

j:Aj,a 6=0

where the dictionary D = {(sl , al )}L
l=1 has size L = |D|. The
decision rule asymptotically becomes:
(
)
L
X
π(s) = arg max Q(s, a) =
α(sl ,al ) k ((s, a), (sl , al ))
a∈A

l=1

(18)
Consider a particular state s that exists in the dictionary D.
Then, the Q-function may be decomposed as:
X
X
−ks−sl k2
−(a−al )2
−(a−al )2
α(sl ,al ) e 2σ2 e 2σ2
Q(s, a) =
α(sl ,al ) e 2σ2 +
sl =s

Using the following asymptotic results for Markov chains:
=

T
1X
a.s.
I{s =s} −→ πs
T t=1 t

X

sl 6=s

hPs,· , A·,al i e

−(a−al )2
2σ 2

sl =s

+

we obtain:

X

hPsl ,· , A·,al i e

−ks−sl k2
2σ 2

e

−(a−al )2
2σ 2

sl 6=s

!
Thr(π q ) =

X

πs

s

X
j

Ps,j

X

qa (s)Aj,a Ca

a

=
≤

X
s
X
s

πs

c(s, k)e

−(a−k)2
2σ 2

k=1



X X
X
=
πs
qa (s) 
Ps,j Aj,a  Ca
s

=

K
X

a

j

X

qa (s) hPs,· , A·,a i Ca

a

where the coefficients are
c(s, k) = hPs,· , A·,k i +

hPs,· , A·,k i ≤ c(s, k) ≤ hPs,· , A·,k i + δ
since
X

hPsl ,· , A·,k i e

−ks−sl k2
2σ 2

sl 6=s

Proof. The ML algorithm chooses an action a ∈ Tms , where
ms is the most likely state transition starting from state

−ks−sl k2
2σ 2

The inequality (16) guarantees that:

a

A PPENDIX B
P ROOF OF T HEOREM 2

hPsl ,· , A·,k i e

sl 6=s

πs max {hPs,· , A·,a i Ca }

The policy π ∗ achieves the upper bound. The proof is complete.

X

≤

X

kPsl ,· k1 kA·,k k∞ e

sl 6=s

=

X

e

−ks−sl k2
2σ 2

≤ (N − 1) max
e
0
s 6=s

sl 6=s

= (N − 1)e

−dmin (S)2
2σ 2

≤δ

−ks−s0 k2
2σ 2

−ks−sl k2
2σ 2

12

For small enough δ, c(s, k) ≈ hPs,· , A·,k i, and the decision
rule (18) coincides with (17).
R EFERENCES
[1] FCC Spectrum Policy Task Force, “Report of the spectrum efficiency
working group,” November 2002.
[2] Q. Zhao and B. M. Sadler, “A survey of dynamic spectrum access:
processing, networking, and regulatory policy,” IEEE Signal Processing
Magazine, vol. 24, no. 3, pp. 79–89, May 2007.
[3] P. D. Sutton, J. Lotze, H. Lahlou, B. Ozgul, S. A. Fahmy, K. E. Nolan,
J. Noguera, and L. E. Doyle, “Multi-platform demonstrations using the
Iris architecture for cognitive radio network testbeds,” in International
Conf. Cognitive Radio Oriented Wireless Networks and Commun., 2010.
[4] D. Xu, Q. Zhang, Y. Liu, Y. Xu, and P. Zhang, “An Architecture
for Cognitive Radio Networks with Cognition, Self-Oorganization and
Reconfiguration Capabilities,” in IEEE Vehicular Technology Conference
(VTC), 2012.
[5] S. Soltani, Y. Sagduyu, Y. Shi, J. Li, J. Feldman, and J. Matyjas, “Distributed Cognitive Radio Network Architecture, SDR implementation
and Emulation Testbed,” in IEEE Military Communications Conference
(MILCOM), 2015.
[6] H. Wang, H. Zhao, J. Li, S. Wang, and J. Wei, “Network architecture
self-adaptation technology in cognitive radio networks,” in IEEE International Symp. Personal, Indoor, and Mobile Radio Commun. (PIMRC),
2016.
[7] D. B. Rawat, “Roar: An architecture for real-time opportunistic spectrum
access in cloud-assisted cognitive radio networks,” in IEEE Consumer
Commun. & Networking Conf. (CCNC), 2016.
[8] Q. Zhao, L. Tong, A. Swami, and Y. Chen, “Decentralized cognitive
MAC for opportunistic spectrum access in ad hoc networks: a POMDP
framework,” IEEE J. Sel. Areas Commun., vol. 17, no. 4, pp. 589–600,
April 2007.
[9] Y. Chen, Q. Zhao, and A. Swami, “Joint design and separation principle
for opportunistic spectrum access in the presence of sensing errors,”
IEEE Trans. Inf. Theory, vol. 54, no. 5, pp. 2053–2071, May 2008.
[10] Q. Zhao, B. Krishnamachari, and Y. Chen, “On myopic sensing for
multichannel opportunistic access: structure, optimality, and performance,” IEEE Trans. Wireless Commun., vol. 7, no. 12, pp. 5431–5440,
December 2008.
[11] Q. Zhao, S. G. adn L. Tong, and B. M. Sadler, “Opportunistic spectrum
access via periodic channel sensing,” IEEE Trans. Signal Processing,
vol. 56, no. 2, pp. 785–796, February 2008.
[12] M. Derakhshani and T. Le-Ngoc, “Learning-based opportunistic spectrum access with adaptive hopping transmission strategy,” IEEE Trans.
Wireless Commun., vol. 11, no. 11, pp. 3957–3967, Nov. 2012.
[13] S. K. Jayaweera, Signal Processing for Cognitive Radios. John Wiley
& Sons, Inc., 2015.
[14] D. W. Browne, “Predicting communications activity in the radio spectrum,” in Asilomar Conf. Signals, Systems and Computers, 2012.
[15] V. Tumuluru, P. Wang, and D. Niyato, “Channel status prediction
for cognitive radio networks,” Wireless Communications and Mobile
Computing, vol. 12, pp. 862–874, 2012.
[16] A. Nguyen, J. Yosinski, and J. Clune, “Deep Neural Networks are Easily
Fooled: High Confidence Predictions for Unrecognizable Images,” in
IEEE Conf. Computer Vision and Pattern Recognition (CVPR), 2015,
pp. 427–436.
[17] N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and
A. Swami, “The Limitations of Deep Learning in Adversarial Settings,”
in IEEE European Symposium on Security and Privacy, 2016, pp. 372–
387.
[18] B. F. Lo and I. F. Akyildiz, “Reinforcement learning for cooperative
sensing gain in cognitive radio ad hoc networks,” Wireless Networks,
vol. 19, pp. 1237–1250, 2013.
[19] A. Galindo-Serrano and L. Giupponi, “Distributed Q-Learning for
aggregated interference control in cognitive radio networks,” IEEE
Transactions on Vehicular Technology, vol. 59, no. 4, pp. 1823–1834,
May 2010.
[20] L. Wang and V. Fodor, “Dynamic Cooperative Secondary Access in Hierarchical Spectrum Sharing Networks,” IEEE Transactions on Wireless
Communications, vol. 13, no. 114, pp. 6068–6080, November 2014.
[21] N. Morozs, T. Clarke, and D. Grace, “Distributed Heuristically Accelerated Q-Learning for robust cognitive spectrum management in LTE
cellular systems,” IEEE Transactions on Mobile Computing, vol. 15,
no. 4, pp. 817–825, April 2016.

[22] R. S. Sutton and A. G. Barto, Reinforcement Learning : An Introduction.
MIT Press, 1998.
[23] X. Xu, D. Hu, and X. Lu, “Kernel-Based Least Squares Policy Iiteration
for Reinforcement Learning,” IEEE Transactions on Neural Networks,
vol. 18, no. 4, pp. 973–992, July 2007.
[24] Y. Engel, S. Mannor, and R. Meir, “The Kernel Recursive Least-Squares
Algorithm,” IEEE Transactions on Signal Processing, vol. 52, no. 8, pp.
2275–2285, August 2004.
[25] A. Schwartz, “A Reinforcement Learning method for maximizing undiscounted rewards,” in International Conference on Machine Learning,
1993.
[26] S. P. Singh, “Reinforcement Learning Algorithms for Average-Payoff
Markovian Decision Processes,” in AAAI National Conference on Artificial Intelligence, 1994.
[27] S. Mahadevan, “Average Reward Reinforcement Learning: Foundations,
Algorithms, and Empirical Results,” Machine Learning, vol. 22, pp.
159–195, 1996.

