Reinforcement Learning for Call Admission Control and Routing under Quality of Service Constraints in Multimedia Networks.
In this paper, we solve the call admission control and routing problem in multimedia networks via reinforcement learning (RL). The problem requires that network revenue be maximized while simultaneously meeting quality of service constraints that forbid entry into certain states and use of certain actions. The problem can be formulated as a constrained semi-Markov decision process. We show that RL provides a solution to this problem and is able to earn significantly higher revenues than alternative heuristics.
Introduction
A number of researchers have recently explored the application of reinforcement
learning (RL) to resource allocation and admission control problems in telecommu-
nications, e.g., channel allocation in wireless systems, network routing, and admission
control in telecommunication networks (Nie and Haykin, 1998, Singh, 1997,
Boyan and Littman, 1994, Marbach, et al, 1998). This paper focuses on applications
of the RL method to call admission control (CAC) and routing in broadband
multimedia communication networks, such as ATM networks. Broadband networks
carry heterogeneous traffic types simultaneously on the same channels. The channels
are packet-based so that customers can send at varying rates over time. Calls
arrive and depart over time and the network can choose to accept or reject connection
requests. If the new call is accepted, the network will choose an appropriate
route to deliver the call from it source node to its destination node. The network
provides Quality of Service (QoS) guarantees at the packet level, e.g., maximum
probability of congestion, and at the call level, e.g. limits on call blocking probabil-
ities. In return, the network collects revenue (payoff) from customers for calls that
it accepts into the network. The network wants to find a CAC and routing policy
that maximizes the long term revenue/utility and meets QoS constraints.
Maximizing revenue while meeting QoS constraints suggests a constrained semi-Markov
decision process (SMDP), as in Mitra, et al (1998). The rapid growth in the
number of states with problem complexity has led to RL approaches to the prob-
lem, as in Marbach and Tsitsiklis (1997), Marbach, et al (1998). However, these RL
applications have ignored QoS criteria. This work draws on a closely related and
more fundamental problem of constrained optimization of (semi-)Markov decision
processes, which has been studied by researchers from control theory, operation re-
search and artificial intelligence communities, see e.g. Altman and Shwartz (1991),
Feinberg (1994), Gabor, et al (1998).
Unlike model-based algorithms (e.g. linear programming in Mitra, et al, 1998),
the RL algorithm used in this paper is a stochastic iterative algorithm, it does not
require a priori knowledge of the state transition probabilities associated with the
underlying Markov chain, and thus can be used to solve real network problems
with large state spaces that cannot be handled by model-based algorithms, and can
automatically adapt to real traffic conditions.
This work builds on earlier work of the authors (Brown, et al, 1999), in that it
provides a more general framework for studying the CAC and routing problem,
under QoS constraints. It also provides more detailed information and proofs for
the RL algorithm used in the study, and contains results for combined CAC and
routing in a multimedia network, which were not reported in Tong and Brown
(1999).
Section 2 describes the problem model used in this study. Section 3 formulates
the CAC problem as a SMDP, and gives a RL algorithm that solves the SMDP.
Section 4 considers QoS constraints in more details. Simulations for CAC on a
single link system is presented in Section 5. Combined CAC and network routing is
studied in Section 6, with simulation results for a 4-node, 12-link network. Section
7 concludes the paper.
2. Problem description
This section describes the CAC problem for a single-link communication system.
There is a substantial literature on CAC in one link multiservice networks, e.g.
Marbach and Tsitsiklis (1997), Mitra, et al (1998), and references in Dziong and
Mason (1994). The single link case is significant since it is the basic building
block for larger networks and, as shown in Section 6 of this paper, combined CAC
and routing for a multi-link network system can be decomposed into single link
processes. We thus first focus on a single-link system.
Users attempt to access the link over time and the network immediately chooses to
accept or reject the call. If accepted, the call generates traffic in terms of bandwidth
as a function of time. At some later time, the call terminates and departs from
the network. For each call accepted, the network receives an immediate revenue
payment. The network measures QoS metrics such as transmission delays, packet
loss ratios, or call rejection probabilities for each service class, and compares them
against the guarantees given to the calls.
The problem is described by the call arrival, traffic, and departure processes;
the revenue payments; QoS metrics; QoS constraints; and network model. To be
concrete, we describe the choices used in the later examples. Calls are divided into
discrete classes indexed by I . The calls are generated via independent
Poisson arrival processes (arrival rate - i ) and have exponential holding times (mean
holding time 1=- i ). Within a call the bandwidth is an on/off process where the
traffic is either on, generating packets at rate r i , or off at rate zero with mean
holding times 1=- on
i and 1=- off
. When a class i call is admitted, the system collects
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 3
a fixed amount of revenue which can be interpreted as the average
reward for carrying the i\Gammath class call (Dziong and Mason, 1994). The network
element connects to the network with a fixed bandwidth B. The total bandwidth
used by accepted calls varies over time.
One important packet-level QoS metric is the fraction of time that the total band-width
exceeds the network bandwidth and causes packet losses, i.e., the congestion
probability, I . We choose the packet-level QoS guarantee to be the
upper limit of congestion probability, p
i , which we denote the Capacity constraint.
In previous works (e.g. Carlstrom and Nordstrom, 1997, Marbach, et al, 1998) each
call had a constant bandwidth over time so that the effect on QoS was predictable.
Variable rate traffic is safely approximated by assuming that it always transmits at
its maximum or peak rate. This peak rate allocation under-utilizes the network; in
some cases by orders of magnitude less than what is possible. Network efficiency
can be improved by statistical multiplexing: Statistically, bursty sources are unlikely
to all simultaneously communicate at their peak rates. Thus it is possible to carry
more bursty or variable rate traffic than would be possible by allocating capacity
according to peak rate requirements, while maintaining service quality. Stochastic
traffic rates in real traffic, the desire for high network utilization/revenue, and the
resulting potential for QoS violations characterize the problem in this study.
Another important QoS metric is the call-level blocking probability. When offered
traffic from each class must be cut back to meet the capacity constraint, it is
important to do so fairly, which we denote the Fairness constraint. Fairness can
be defined in a number of different ways, but one intuitive notion is that calls
from every class are entitled to the same admission probability, or equivalently, the
same rejection probability, (Dziong and Mason, 1994). This will be more precisely
defined in Section 4.
Ultimately our goal is to find a policy, -, that for every system state, s, chooses
the correct control action, a, so that we maximize revenue subject to the QoS
constraints. Formally, we consider the following problem of finding the CAC policy,
-, that
maximizes J 0 (-) (1)
subject to J j (- l
fset of all policiesg (3)
where K is the number of QoS constraints, l are real numbers that
characterize the QoS constraints, J 0 (-) characterizes the average network revenue
under policy -, and J j characterize the QoS under policy -. We
consider objectives of the form
an )
an )
K. Action an is chosen at state s n according to the policy -,
an ) are the reward functions associated with revenue (for
are assumed to be bounded. The -(s n ; an ) are the
average sojourn times at state s n under action an , while n indexes the n\Gammath decision
epoch (Decisions are made at points of time referred to as decision epochs).
3. Semi-Markov decision processes and reinforcement learning
The following sections develop the components to the problem and finish by justifying
a particular method suitable for the CAC problem.
3.1. States and actions
This section develops the state action model and a reduced state space representation
suitable for the CAC problem.
The CAC problem can be formulated as a semi-Markov decision process (SMDP)
in which state transitions and control selections take place at discrete times, but
the time from one transition to the next is a continuous random variable. At
any given point of time, the system is in a particular configuration, x, defined by
the number of each type of ongoing calls, and y, the number of calls in the on
state of each type. At random times an event e can occur (only one event can
occur at any time instant), where e is an I \Gammavector indicating either a class i call
arrival, a call termination, a call being turned on, or a call being turned off event,
I . The configuration and event together determine the state of the system,
e). For an I-class system, s is a 3I dimensional vector. Since the number
of possible choices for e is in general small compared to those for x; y, the size the
state space is dominated by the configuration part of the state. It can be shown
that using the nearly complete decomposability approximation we can reduce the
state descriptor into the form of stands for a call arrival or
departure event of class i. Let I ) be the configuration, e i denote
the I \Gammavector whose elements are equal to zero except the ith element, whose value
is unity. Then the states associated with a class i call arrival are
the states associated with a class i call departure are I . This
reduction, by ignoring the number of calls in the on state and the events of a call
being turned on or off, gives us enough accuracy for the CAC problem, as shown
experimentally by Mitra, et al (1998).
Here we give two reasons for this simplification. First, the moment a call turns on
or off is not a decision point for the admission controller, and therefore no action
needs to be taken. Theorem 2 in the Appendix shows that ignoring the events of a
call being turned on or off is valid. Section 3.4 also provides further discussions
on the similar simplifications. Second, it is intuitively clear that this simplification
is a good approximation when the process describing the number of calls in the on
state reaches equilibrium between any change in the number of calls in progress due
to the call arrival/departure. Hence, when making a call admission decision, the
number of calls of each class in progress is important, but the number of calls of
each class in the on state is not, because these quantities oscillate rapidly relative
to call arrivals and departures. If we view the ignorance of y as state aggregation,
and assume that for a fixed x, the Q-values do not change much for different y,
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 5
then the discussions in Section 3.6 further justify this reduction of dropping y. We
note that y does affect the congestion probability. Assuming the y process reaches
equilibrium and corresponds to fixed x, and assuming source independence, the
probability for the configuration (x; y) is given by the binomial distribution
I
Y
where b i is the fraction of time a class i call spends in the on state,
The average congestion probability for class i with fixed x is thus
x I
y I =0
where 1f\Deltag is the indicator function. So the average congestion probability depends
only on x.
Capacity constraints associated with (6) are conservative in that the set
is the set of x such that the long run average packet-level QoS constraints are
always satisfied, and we will never go into any state for any period of time where
the capacity constraint will be violated if we stay there forever. The set C c uniquely
determines a state space S: for any i, (x; e i
. Mitra, et al (1998) considers a
more aggressive approach to the packet-level QoS constraints, that averages across
all the allowable configurations x. Let
x2Ca
T (x) be the total system time,
T (x) be the portion of T the system spends at x, C a is the set of the allowable
configurations x such that
x2Ca
are less than or equal to target p
I . Obviously, C a is not unique,
and C c is a possible C a , although in general it is too conservative. In some occasions,
to emphasis the dependence of C c and C a on p
I ), we also write C c (p   )
and C a (p   ).
In summary, we choose the state descriptor to be is the
number of class i calls in progress, and e i stands for a new class i call arrival, \Gammae i
for a class i call departure, 1 - i - I .
When an event occurs, the learner has to choose an action feasible for that event.
The action set is A(s)=f0=reject, 1=acceptg upon a new call arrival. Call terminations
are not decision points, so no action needs to be taken. Symbolically, at
6 H. TONG AND T.X BROWN
such states A(s)=f\Gamma1=no action due to call departuresg. Note that the actions
available at state s, A(s), in general depend on s. For example, if adding a new call
at a state s will violate the capacity constraint, then the action set at that state
should be constrained to f0g. At some subsequent random time another
event occurs, and this cycle repeats. The revenue structure for CAC is:
The task of the learner is to determine a policy for accepting calls given s, that
maximizes the long-run average revenue, over an infinite horizon while meeting
the QoS requirements. For CAC, the system constitutes a finite state space
e)g, (due to the capacity constraint), finite action space A=f\Gamma1,0,1g, semi-Markov
decision process.
3.2. Transition probabilities
This section considers the probability model and concludes that for large state
spaces, classical approaches based on the transition probability model are not fea-
sible. Theoretically, a state transition probability p(s; a; s 0 ) - the probability of
going from state s under action a to next state s 0 - can be derived (Mitra, et
al, 1998), which depends on the configuration x and call arrival rates. But exact
system models are often infeasible for several important reasons. First, call arrival
rates may depend not only on each call class, but also on the configuration
x (Dziong and Mason, 1994). Therefore, the call arrival rate for each class may
not be a constant in general. Second, for any network of reasonable size, the state
space is extremely large. As an example, a 4-node, 12-link network with 3 service
types has more than 10 states (Marbach, et al, 1998). It is not even possible to
explicitly list all the states. Finally, fixing a model before computing the optimal
policy means that it will not be robust if the actual traffic condition departs from
the assumed model.
For the above reasons, it is clear that for any practical system with large state
space, it will be very difficult, if not impossible, to determine the exact transition
model for the Markov chain before performing any model-based algorithm to
compute the optimal policy. This is the main motivation for this study to apply
model-free RL algorithms to solve CAC problems.
Although we will not explicitly compute the transition probabilities, we make the
following assumptions in this study: let - ss 0 (a) be the continuous random inter-
transition time from state s to state s 0 under action a, with probability distribution
F ss 0 (-ja),
Assumption A1.
Assumption A2. a) is the expectation of - ss 0 (a), for
any s 2
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 7
Z 1-dF ss 0 (-ja) (10)
In particular, there exists
Assumption A3. Unichain Condition: For every stationary policy -, transition
matrix (p(s; -(s); s 0 determines a Markov chain on S with one ergodic
class and a (possibly empty) set of transient states.
Assumption A1 guarantees the transition probabilities are well defined. Assumption
A2 guarantees that the number of transitions in a finite time interval is, almost
surely, finite. A3 guarantees that except for some initial transient states, any state
can reach any other state with non-zero probability.
3.3. Q-learning
This section develops the RL methodology used in this paper for the unconstrained
maximization of revenue. The QoS constraints will be considered in Section 4.
We learn an optimal policy using Watkins' Q-learning algorithm (Watkins and
Dayan, 1992). Given optimal Q-values, Q   (s; a), the policy -   defined by
is optimal. In particular, (12) implies the following procedures. When a call arrives,
the Q-value of accepting the call and the Q-value of rejecting the call is determined.
If rejection has the higher value, we drop the call. Else, if acceptance has the higher
value, we accept the call. Only one action (and Q-value) exists at a call departure.
To learn Q   (s; a), we update our value function as follows: on a transition from
state s to s 0 under action a in time - ss 0 (a),
where is the stepsize or learning rate, k is an integer variable to
index successive updates, and ff ? 0 is chosen to be sufficiently close to 0 so that
the discounted problem is equivalent to the average reward problem (the Tauberian
approximation, Gabor, et al, 1998). It is well known that Q-learning (13) is the
Robbins-Monro stochastic approximation method that solves the so-called Bellman
optimality equation associated with the decision process. Let
Z 1e \Gammaff- dF ss 0 (-ja)
for all s, and a 2 A(s). Assumption A2 guarantees that H is a contraction mapping
with contraction factor
Z 1e \Gammaff- dF ss 0 (-ja)
with respect to the maximum norm.
Theorem 1. Suppose thatX
for all s 2 and each state-action pair is updated an infinite number of
times. Then, Q k (s; a) converges with probability 1 to Q   (s; a), for every s and a.
Proof: See Bertsekas and Tsitsiklis (1996).
3.4. A simplified learning process
There is a practical issue concerning the implementation of Q-learning (13). From
the above discussions, Q-learning needs to be executed at every state transition,
including the transition caused by a call departure, at which the feasible action set
is there is only one action at states
associated with call departures, it is not necessary to learn the optimal Q-values at
these states to induce the optimal policy at these states.
Is it possible to avoid the updates of Q-values at departure states, and still get
the same optimal policy? This will reduce the amount of computation and storage
of Q-values significantly, since the state space is almost halved by dropping the call
departure states. We note that the only interesting states at which decisions need
to be made are those associated with call arrivals, )g. So the decision
point jumps from one arrival to the next arrival, where an interarrival period may
contain zero, one, or more departures. Given
where e j is the first arrival after e i , for the cases where there are n ? 0 departures
between two adjacent arrivals, by Chapman-Kolmogorov equations (Bertsekas and
Gallager, 1992), the transition probability for the actual decision process is
s is the intermediate state corresponds to a call departure.
It is shown in the Appendix that the same optimal policy can be obtained by
only doing Q-learning at the states associated with call arrivals. This result is
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 9
intuitive since the call departures are random disturbances that only affect the
state transitions. Even though (18) further complicates the already intractable
transition model for the SMDP, since Q-learning does not depend on the explicit
model, the asymptotic convergence to the optimal policy follows.
3.5. Exploration
In order for Q-learning to perform well, all potentially important state-action pairs
(s; a) must be explored. Specifically, the convergence theorem of Q-learning requires
that all state-action pairs (s; a) are tried infinitely often. This section develops an
exploration strategy suitable for the CAC problem.
A common way to try all state-action pairs in RL is, with a small probability
ffl, a random action rather than the action recommended by RL is chosen at each
decision point during training, the so-called ffl\Gammarandom exploration. For the CAC
problem considered in this paper, without exploration some states will be visited
with probabilities several orders higher than some other states, and experiments
have shown that ffl\Gammarandom exploration is very unlikely to help in this situation.
Therefore, after training some states will be visited many times while some other
states will only be visited for a few times, and the resulting Q-value functions are
far from converging, and an optimal policy cannot be expected in reasonable time.
To see this, the call arrival process can be modeled as truncation of I independent
M/M/1 queues system. The truncated system is the same as for the untruncated
system, except that all configurations I ) for which capacity constraint
is violated have been eliminated. The stationary distribution of this system,
assuming the greedy policy (the policy that always accepts a new call if the capacity
constraint will not be violated by adding the new call), is given by Bertsekas and
Gallager (1992)
G is a normalization constant,
is the allowed set of configurations of the truncated system.
Since the state s and action a deterministically define the next configuration x 0 of
the next state s 0 , and the event part of s 0 , e 0 (arrival only, at which an action
needs to be taken), occurs independent of x 0 with probability determined by - i due
to the memoryless assumption, so the stationary distribution of states s 0 depends
on (19). As an example, consider the same experimental parameters shown in

Table

1 of Section 5 below, except that to simplify the calculation of the allowable
configuration set C of the truncated system, we use the peak-rate allocation, so
1g. Using (19) and (20) we have, for the most
visited state, 0:2297, and for the least visited state, P
i.e., more than five orders of difference in the stationary distribution of state-action
pairs for this small system. It is shown in Szepesvari (1998) that the convergence
rate of Q-learning is approximated by
for some suitable constant B ? 0, where k is the same index as in (13), and i as
defined in (15).
To overcome the slow convergence caused by the small value of P min =Pmax in
the stationary distribution, a controlled exploration scheme is derived based on the
facts that Q-learning is an off-policy learning method (Sutton and Barto, 1998,
Section 7.6), and that in SMDP the state transitions, and thus the state distri-
bution, can be controlled by choosing appropriate actions. At each state during
training where there are more than one feasible actions, with probability ffl the control
action is chosen that leads to the least visited configuration. This ffl\Gammadirected
heuristic effectively reduces the difference in the number of visits between states,
and significantly speeds up the convergence of the value functions. In terms of the
Q-learning formula (13), action a is chosen according to the exploration scheme,
and action b is chosen according to the current Q-value.
3.6. Function approximation vs. lookup tables
Q-learning deals effectively with the curse of modeling (an explicit state transition
model is not needed, and a simulator can be used instead). Another major difficulty
with SMDP problems is the curse of dimensionality (the exponential state space
explosion with the problem dimension). In the above treatment, we have assumed
that the problem state space is kept small enough so that a lookup table can be
used. Clearly, when the number of state-action pairs becomes large, lookup table
representation will be infeasible, and a compact representation where Q is represented
as a function of a smaller set of parameters using a function approximator
is necessary.
In this paper, we choose the approximation architecture to correspond to state
aggregation. We consider the partition of the state space S into disjoint subsets
\Gammadimensional parameter vector OE whose mth component
is meant to approximate the Q-value function for all states s 2 Sm under
action a. In other words, we are dealing with piecewise constant approximation
~
Q(s;
When the value of M is small, a lookup table can be used for the aggregated
problem. In this case, it can be shown (Bertsekas and Tsitsiklis, 1996) that Q-learning
converges to the optimal policy for the aggregated problem. Other function
approximators can be used, they may perform well in practice, however, there is
no convergence result as for the state aggregation case, and we wish to avoid them
here. By Proposition 6.8 in Bertsekas and Tsitsiklis (1996), and the Tauberian
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 11
approximation, it is easy to show that the performance loss due to state aggregation
is bounded by
where J
0 and ~
0 are the optimal average revenue per unit time for the original and
the aggregated problem, respectively, i as defined in (15); and
In CAC, state aggregation can be interpreted as a feature-based architecture
whereby we assign a common value OE(m; a) to all states s, given a, that share a
common feature vector. For example, a feature vector may involve for each call class
a three value indicator, that specifies whether the load of each call class is "high",
"medium", or "low" in the system, instead of specifying precisely the number of
ongoing calls of each class, x. Since states with similar numbers of calls would be
expected to have similar Q-values, " is expected to be small. Therefore, the state
space can be greatly reduced, and lookup table can be used.
3.7.

Summary

This section formulates the CAC problem as a SMDP, and justify the Q-learning
approach to solving the CAC problem. It shows that we can simplify the problem
by ignoring the details of the within call processes and not computing Q-values
for states that have no decision. Standard ffl\Gammarandom exploration policies will significantly
slow down learning in this problem, so a simple ffl\Gammadirected exploration
strategy is introduced. Aggregation of states is shown to be a simplifying heuristic
that follows readily from the problem structure. The next section develops a
method for incorporating the constraints into this framework.
4. Constraints
We restrict the maximization to policies that never violate QoS guarantees, (1)
- (3). For general SMDP problems, the constrained optimal policy is a randomized
stationary policy, which randomizes in at most K states for a problem with
K \Gammaconstraints (Feinberg, 1994). However, model-based linear programming algorithms
have to be employed to derive such a policy, which is impractical for CAC
where the number of states can be very large. Since randomizations are needed at
only K states, which is usually much smaller than the total number of states, the
non-randomized stationary policy learned by RL is often a good approximation to
the constrained optimal policy (Gabor, et al, 1998).
In general SMDP, due to stochastic state transitions, meeting such constraints
may not be possible (e.g. from any state no matter what actions are taken there
is a possibility of entering restricted states). In admission control, service quality
depends on the number of calls admitted into the system and adding calls is strictly
controlled by the admission controller, so that meeting such QoS constraints is
possible.
We consider two important classes of QoS constraints in CAC in an integrated
service network. One is the State-dependent constraints, the other is the Past-
dependent constraints. The (conservative) capacity constraint is an example of
state-dependent constraints. State-dependent constraints are QoS intrinsic to a
state. The congestion probability is a function solely of the number of calls in
progress of the current state, [cf. (6)]. Past-dependent constraints depend on
statistics over the past history. An example is the fairness criterion. Fairness
depends on the statistics of the rejection ratios over the past history. We address
these two constraints separately.
4.1. Capacity constraint
For simplicity, we consider a total packet congestion probability upper bound, p   .
For the conservative approach, this means the set C c (p
[cf (6) and (7)]
x I
y I =0
As stated, the conservative capacity constraint is an intrinsic property of a state
and it only depends on the current state. This allows us to collect QoS statistics
about each state and treat them in a principled way (e.g. computing confidence intervals
on the estimates). The current state and action (s n ; an ) uniquely determine
the next configuration, xn+1 , and the projected congestion probability for the next
state s n+1 is determined only by xn+1 . Therefore, to forecast the impact of an at
we need to evaluate if p(xn+1 ), the expected congestion probability, is greater
or less than the constraint p   . If an action will cause p(xn+1 action
should be eliminated from the feasible action set A(sn ). In CAC, if adding a new
call will violate the capacity constraint, then the only feasible action is to reject
the new call request.
When considering the aggressive capacity constraint, we need to determine the
set C a = C a (p   ) of allowable configurations, defined implicitly (but not uniquely)
from
lim
x2Ca
where T (x) is the total time the system spends at x, and
x2Ca
T (x). We note
that the distribution T (x)=T depends on the control policy. Again, generalization to
the case where different service types have different packet-level QoS requirements
can be easily made.
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 13
As stated, C c (p   ) serves as a possible C a but it is usually too conservative. To
construct a more aggressive set C a (p   ), we gradually decrease p
c from 1, and find
a series of sets C c (p
c ) corresponding to the changing p
c . Clearly, the size of C c (p
is non-increasing with the decrease of p
c , however, it must always contain C c (p   ).
In practice, at some value p
c0 under the learned policy, if the aggressive congestion
probability will be sufficiently close to, and still less than the constraint p   ,
then the search for C a (p   ) can stop, and we choose the C a (p
c0 ) for the
aggressive capacity constraint. In essence, we try to find a corresponding value of
conservative threshold p
c to the aggressive threshold p   , and construct C a from the
conservative approach. This way, the aggressive capacity constraint remains to be a
state-dependent constraint, and as for the conservative capacity constraint, we can
implement this constraint by constraining the action set at each state. Although
C a determined in the above way may not be the most aggressive one in term of the
revenue maximization (1) - (3), the loss of optimality is expected to be small.
4.2. Fairness constraint
be the measured rejection ratio for class i upon the nth call arrival
(before the nth decision is made). For arbitrarily constraints on R i (s n ), we may
not be able to find a feasible policy. The fairness constraint involves comparisons
of rejection ratios for all types of calls. We formulate the fairness constraints as
1-i-I
1-i-I
where l d is the maximum allowed rejection ratio discrepancy. A feasible policy
exists by always rejecting all call types. The aggressive fairness constraint can be
formulated as
lim
- l d (28)
where - sn sn+1 (a) is the inter-transition duration from state s n to s n+1 under action
a. This formulation is a constrained SMDP problem (1) - (3) with
the capacity constraint is implemented by constraining the feasible action set at
each state as described in the preceding subsection.
To deal with the fairness constraint, we use the Lagrange multiplier framework
studied in Beutler and Ross (1986). Since the fairness constraint is a past-dependent
constraint (the vector R(sn+1 ) depends on the rejection ratios over the past his-
tory), to fit into this framework, we need to include this history information into
our state descriptor. The new state descriptor, - s, has the form
where the I \Gammavector req (resp. rej) denotes the total number of call requests (resp.
rejections) from each class before the current call arrival, - is the time interval
between the last and the current call request, and is the original state
14 H. TONG AND T.X BROWN
descriptor. We obtain a Markov chain by doing this expansion, however, the state
space has been enlarged significantly. Specifically, due to the inclusion of req; rej,
and -, the state space is now infinite, and we must resort to some form of function
approximation to solve the SMDP problem. In this paper, we use state aggregation
as our approximation architecture, by quantizing the rejection ratios R
and -.
In terms of a Lagrange multiplier !, we consider the unconstrained optimization
for the parametrized reward
a) is the original reward function associated with the
is the cost function associated with the constraint
the numerator of (28).
If there exists a non-randomized policy - !
that solves the Bellman optimality
equation associated with reward function (30), and in the mean time, achieves the
equality in (28), then Beutler and Ross (1986) shows that - !
is the constrained
optimal policy. In case such optimal policy does not exist, it is shown that the
constrained optimality is achieved by randomization at only one state - s 0 , between
two non-randomized policies, - !
2 , that only differ from each other in -
slightly undershooting (resp. overshooting) l d . Clearly, in case
that the non-randomized constrained optimal policy does not exist, - !
1 is the next
best non-randomized policy, and the loss of optimality is minimal. For the above
reasons, and to avoid the complications of randomized policies, we concentrate on
non-randomized policies in this study.
4.3.

Summary

This section shows how the constraints can be introduced to the problem, either by
modulating the action space or modifying the reward function. While optimality
requires a randomized policy, since the policy only needs to be randomized in two
states out of many states, we greatly simplify the search by restricting
ourselves to deterministic policies.
5. Simulation results
The experiments use the following model. The total bandwidth is normalized to
1.0 unit of traffic per unit time. The target congestion probability is p
Two source types are considered with the properties shown in Table 1. The fairness
constraint is that the average rejection ratio discrepancy for two service types should
not differ more than l As noted before, all holding times are exponential.
We first concentrate on the conservative approach to the capacity constraint.
Since exploration is employed to ensure that all potentially important state-action
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 15

Table

1. Experimental parameters
Source Type
Parameter I II
on rate, r 0.08 0.2
Mean on period, 1=- on 5 5
Mean off period, 1=- off 15 45
Call arrival rate, - 0.067 0.2
Call holding time, 1=-
Immediate payoff,
pairs are tried, it naturally enables us to collect statistics that can be used to
estimate QoS at these state-action pairs. It should be emphasized that a single visit
to a state is not sufficient to determine the long run QoS metrics due to variability
in the within call process. As the number of times that each state-action pair is
visited increases, the estimated service quality becomes more and more accurate
and, with confidence, we can gradually eliminate those state-action pairs that will
violate QoS requirements. As a consequence, the value function is updated in a
gradually correct subset of state-action space in the sense that QoS requirements
are met for any action within this subspace. As stated in Section 4, the capacity
constraint eliminates those state-action pairs that violate the congestion probability
upper limit.
In the experiments, we use a simple way to eliminate state-action pairs with
confidence. Since our target congestion probability is be the
total number of visits to the configuration x, (counted as the number of time steps
in the simulation), and w(x) be the number of congestions at x, then if w(x)
and T (x) ? 200, or if w(x)
20000, we conclude that (s; a) is not acceptable. These thresholds provide close
approximations to the confidence intervals in Brown (1997). A more sophisticated
way to estimate p(x) is proposed in Tong and Brown (1998), where artificial neural
networks (NNs) are trained based on the maximum likelihood principle so that the
NN estimates of p(x) extrapolate well down to p  In simulations, the
discount factor ff is chosen to be 10 \Gamma4 , learning rate exploration
Initial Q-values for RL are artificially set such that Q-learning
started with the greedy policy.
After training is completed, we apply a test data set to compare the policy obtained
through RL with alternative heuristic policies. The final QoS measurements
obtained at the end of the RL training while learning QoS are used for testing
different policies. To test the RL policies, when there is a new call arrival, the
algorithm first determines if accepting this call will violate QoS. If it will, the call
is rejected, else the action is chosen according to a = arg max a2A(s) Q(s; a), where
0=rejectg. For the QoS constraint we use three cases: Peak rate
allocation; statistical multiplexing function learned on-line, denoted QoS learned;
and statistical multiplexing function given a priori, denoted QoS given. We examine
six different cases: (1) RL: QoS given; (2) RL: QoS learned; (3) RL: peak rate;
A heuristic that only accepts calls from the most valuable class, i.e., type I,
with QoS given; (5) Greedy: QoS given; (6) Greedy: peak rate.
From the results shown in Fig. 1, it is clear that simultaneous Q-learning and
QoS learning converges correctly to the RL policy obtained by giving the QoS a
priori and doing standard Q-learning only. We see significant gains (about 15%)
due to statistical multiplexing in (6) vs (5), and (3) vs (1). The gains due to RL
are about 25% in (6) vs (3), and (5) vs (2). Together they yield about 45% increase
in revenue over conservative peak rate allocation in this example. It is also clear
from the figure that the RL policies perform better than the heuristic policies. Fig.
(2) shows the rejection ratios for different policies.
Now we consider the aggressive approach to the capacity constraint. From the
simulation, it is found that the value of p
corresponds to the aggressive
capacity constraint p  . The acceptance regions (i.e., C a and C c ) for both
the aggressive and conservative approaches are shown in Fig. 3. The aggressive
acceptance region is much larger than the conservative one. In the figure, the
number of type II users starts at two due to insufficient measurement data (for the
confidence level) in the region below that. Comparing Figs. 4 and 5 with Figs.
1 and 2, we can see that the aggressive approach earns significantly more revenue
than the conservative approach, for both greedy policy and RL policy, note that
the peak rate allocation earns the same total amount of rewards (un-normalized)
with both approaches. In Fig. 4, the Q-values are initialize so that the RL policy
starts with the greedy policy.
In the above examples, the performance improvement due to RL is more significant
than the improvement due to statistical multiplexing. Because no fairness
constraint is imposed for this case, rejection ratios for the two types of calls differ
significantly.
Our fairness constraint requires that the two rejection ratios cannot differ more
than 5% on average. To test RL under the fairness constraint, we set the reward
parameters for a type I call to be 1, and for a type II call to be 10, and keep other
parameters in Table 1 unchanged. As stated before, we use feature-based state
aggregation to cope with the difficulty of the large state space caused by fairness
constraint. Specifically, we learn Q(h(-s); a) instead of Q(-s; a), where the feature
quantization. In the following experiment, the
experienced rejection ratio discrepancy f(R(-s)) is quantized into 100 levels, and -
is quantized into only 2 levels, with corresponding to - 4 (the approximate
average inter-arrival time), and Although s is not aggregated in this
experiment, for cases where s is more complicated, it is also possible to aggregate
s into a simpler feature. !   is found to be 80.0 in the simulation. The learned RL
policy is compared with a greedy policy under the fairness constraint, which accepts
all calls as long as the fairness constraint is met, otherwise, if the fairness constraint
is violated, it only accepts calls from the class experiencing highest rejection ratio.
The results are shown in Figs. 6 and 7. With fairness as a strong constraint on
possible policies, the gain due to RL reduces as expected.
From Figs. 1, 4, and 6, we see that Q-learning converges quickly. The fact that
the RL curves in these figures show oscillations is connected with the learning rates,
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 17
total
reward
Comparison of different policies, exponential ON/OFF246
1.RL: QoS given
2.RL: QoS learned
3.RL: peak rate
4.Greedy, type only
5.Greedy: QoS given
6.Greedy: peak rate

Figure

1. Comparison of total rewards of
RL while learning QoS (capacity constraint
RL with given QoS measurements, RL
with peak rate, greedy policies and peak rate
allocation, normalized by the greedy total reward

rates
1-Greedy: peak rate, 2-RL: peak rate, 3-Greedy: QoS given, 4-RL: QoS learned, exponential ON/OFF

Figure

2. Comparison of rejection ratios for
the policies learned in Fig. 1.
a) in (13). Specifically, in order for Q-learning to converge, fl k (s; a) have to
satisfy (16) and (17) for all (s; a). But in the simulations, we used a small constant
learning rate, condition (17) is not met. The reason that (17) is
not adhered to is because typically, there is no prior knowledge as to how and
when a) should be decreased - once the learning rate becomes very small,
the algorithm may stop making any noticeable progress, and the training process
could become too long.
6. Combining CAC with network routing
In general, the issues of CAC and routing are closely related in a communication
network. Combined CAC and routing can also be formulated as a SMDP. However,
the exact characterization of network state would require the specification of the
number of calls in progress from each class on each possible route in the network.
Such a detailed specification of state is intractable for computation. By assuming
statistical independence of the links in the network (Dziong, 1997, Krishnan, 1990),
some form of decompositions of network routing process into single link processes
is usually employed (Dziong and Mason, 1994, Marbach, et al, 1998). Based on the
preceding results for single link admission control and the link state independence
approximation, we propose a decomposition rule that allows decentralized training
and decision making for combined CAC and routing in a network, which also tries
to maximize the network revenue.
123579number of users of class
number
of
users
of
class
II
comparison of accept regions
Aggressive
Conservative

Figure

3. Comparison of acceptance regions.
total
reward
Comparison of different policies, exponential ON/OFF
RL: QoS learned
Greedy: QoS given
Greedy: peak rate

Figure

4. Comparison of total rewards of
RL while learning QoS (capacity constraint
Greedy policy and peak rate alloca-
tion, normalized by the greedy total reward,
Aggressive.
30.10.30.50.70.9rejection
rates
1-Greedy: peak rate, 2-Greedy: QoS given, 3-RL: QoS learned, exponentialON/OFF

Figure

5. Comparison of rejection ratios for
the policies learned in Fig. 4.
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 19
total
reward
Comparison of different policies, exponential ON/OFF
RL: QoS learned
Greedy: QoS given

Figure

6. Comparison of total rewards obtained
from RL policy and Greedy policy,
when both capacity constraint and fairness
constraint are imposed, normalized by the
greedy total reward.
rejection
rates

Figure

7. Comparison of rejection ratios with
both capacity constraint and fairness constraint
for the policies learned in Fig. 6.
Let R denote all the predefined routes in the network, the action space for the
system is action due to call departures, route the
new call over route r 2Rg. Each link (i; j), from node i to node j, keeps a separate
is the link state variable. Whenever a new call
of type k is routed over a route r which contains link (i; j), the immediate reward
associated with the link (i; j) is equal to c ij satisfying
(i;j)2r
For example, is the number of links along the route r. Q-learning
can be performed for each link similarly as in the single link case. At each
arrival, we update the Q-value of link (i; j), only if this arrival is associated with the
link. For a new type k call originated at node o, destined for node d, the decision
is made at node o in the following way:
od ) be the set of routes that can carry the call without
violating QoS constraints;
ii) Define the net gain g r of accepting the new call under routing decision r by
ae P
(i;j)2r
\Theta


Figure

8. Network model.
The admission and routing decision is
r
r2A(s od )[f0g
r (34)
Decision Making: If r  reject the call. Otherwise, route the call over
route r   .
In the above approach, although the network state s is simplified into the link state
each link, the action space for each link is not simplified into
acceptg, as in Dziong and Mason (1994), Marbach, et al (1998). This is important
since by doing so the link Q-functions can distinguish single-link calls from multi-link
calls, and avoid accepting too many multi-link calls, and block single-link calls
that may bring the same amount of revenue while using less network resources.

Table

2. Experimental parameters
Source Type
Parameter I II III
On rate, r
Call arrival rate, - 0.1 0.1 0.067
Call holding time, 1=- 200 180 120
Immediate payoff,
We present simulation results obtained for the case of a network consisting of 4
nodes and 12 unidirectional links. There are two different classes of links with a
total bandwidth of 1.5 and 2 units, respectively (indicated by thick and thin arrows
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 21
in Fig. 8). We assume three different source types, whose parameters are given in

Table

2. Call arrivals at each node are independent Poisson processes with mean -,
the destination node is randomly selected among the other three nodes. For each
source and destination node pair, the list of possible routes consists of three entries:
the direct path and two alternative 2-hop routes. To emphasize the effect of RL,
we only consider the capacity constraint and assume peak rate allocation on each
link in the simulations.
We use feature-based state aggregation to approximate the Q-values for each link,
where we learn Q(h(s); r) instead of Q(s; r), and i.e., the numbers
of ongoing calls from each type are aggregated into eight levels.
The policy obtained through RL is compared with a commonly used heuristic
policy that gives the direct path priority. When the direct path reaches its capacity,
the heuristic will try the 2-hop routes, and find one that does not violate the
capacity constraint. If no such route exists, the call is rejected.
The results are given in Fig. 9 (Total Fig. 10 (Call rejection ratios),
and Fig. 11 (Routing behavior). The results show that the RL policy increases
the total revenue by almost 30% compare to the commonly used heuristic routing
policy.
7. Conclusion
This paper formulates the CAC and routing problem as a constrained SMDP, and
provides a RL algorithm for computing the optimal control policy. We incorporate
two important classes of QoS constraints, state-dependent and past-dependent con-
straints, into a RL solution to maximize a network's revenue. The formulation is
quite general and has been applied to the capacity and fairness constraints. The
approach was experimented with on a single link as well as a network problem, and
we showed significant improvement even for simple examples.
Future work includes: further study on combined CAC and routing; and studying
other function approximators, such as neural networks, to approximate Q-value
functions.

Acknowledgments

This work was funded by NSF CAREER Award NCR-9624791.


Appendix


Proof for the simplified learning process
The following Theorem shows that we can avoid learning Q-values at state transitions
corresponding to calls being turned on or off (Section 3.1), and call departures
(Section 3.4). Let J ff
and c(s; A(s)g be the set of the intermediate states,
g.
22 H. TONG AND T.X BROWN
total
reward
Comparison of different routing policies, exponential ON/OFF
RL
Heuristic

Figure

9. Comparison of the total rewards
for the 4-node network, normalized by the
Heuristic total reward.
20.10.30.50.70.9Rejection ratios: 1-Heuristic, 2-RL, exponential ON/OFF
rejection
rates

Figure

10. Comparison of the rejection ratios
for the policies in Fig. 9.
Routing-Heuristic
portion
of
calls
routed
on
direct
and
paths
direct
1st 2-hop
2nd 2-hop
Routing-RL
portion
of
calls
routed
on
direct
and
paths
direct
1st 2-hop
2nd 2-hop

Figure

11. Comparison of the routing behavior for the policies in Fig. 9.
REINFORCEMENT LEARNING FOR CALL ADMISSION CONTROL 23
Theorem 2. Assume that from each s 2 S 2 , a 2 A(s), it takes at most m sa steps
to go to a state - s 0
all the states between s
and -
s 0 are in S 1 , and 1. Then the optimal stationary policy for the
modified decision process by only considering states in S 2 is also optimal for the
original decision process.
Proof: The optimal policy for the original problem is
Z 1e \Gammaff- dF ss 0 (-ja)
for all s 2 S. The optimal policy - ff for the modified decision process is,
since there is only one feasible action in A(s) for s 2 S 1 . For each s 2 S 2 , n in (18)
can be at most m sa due to the assumption.
hi
Z 1e \Gammaff- dF ss 0 (-ja)
oe
where s 0 is the first state after s that is in S 2 . Define
Z 1e \Gammaff- dF ss 0 (-ja)
Since m sa is finite, without loss of generality, assume m other values of
sa , the procedure is similar). The summation term in (A.3) becomes
hi
"/
\DeltaD(s;
The second summation in the second term of the above formula is
due to the condition that p(-s
Combining (A.5) and (A.6)
From (A.3), (A.4), and (A.7), we have for all s
Z 1e \Gammaff- dF ss 0 (-ja)
By the uniqueness of the optimal value function, it is easy to verify that J ff
Therefore, by (A.1), (A.2), and (A.8)
In the above proof, e.g. (A.4), we used the memoryless property of the transition
processes.
In CAC, states such as s serve as - s 0 . Since from s 0 , it is not
possible to have any more call departures. And due to the capacity constraint, from
any state s, under any action a, it will take at most finite number of consecutive
call departures to reach a state like s 0 .



--R

Adaptive control of constrained Markov chains.

Data Networks



Adaptive statistical multiplexing for broadband communications.
Optimizing admission control while ensuring quality of service in multimedia networks via reinforcement learning.
Control of self-similar ATM call traffic by reinforcement learning
Call admission and routing in multi-service loss networks
IEEE Trans.
ATM Network Resource Management
Constrained semi-Markov decision processes with average reward

International Conference on Machine Learning
Markov decision algorithms for dynamic routing.
A Neuro-Dynamic Approach to Admission Control in ATM Networks: The Single Single Link Case
Reinforcement learning for call admission control and routing in integrated service networks.
Robust dynamic admission control for unified cell and call QoS in statistical multiplexers.

Reinforcement learning for dynamic channel allocation in cellular telephone systems.
Reinforcement Learning
The asymptotic convergence-rate of Q-learning
Advances in NIPS 10
Estimating loss rates in an integrated services network by neural networks.
Adaptive call admission control under quality of service con- straints: a reinforcement learning solution

--TR
routing;reinforcement learning;call admission control;quality of service;multimedia networks