Nof S.Y. Springer Handbook of Automation

Подождите немного. Документ загружается.

Cybernetics and Learning Automata 12.4 Classiﬁcation of Learning Automata 225

In (12.6), each element f

of the matrix F

represents

the probability of the automaton moving from state q

to the state q

on receiving an input signal β from the

RE. F

is a Markov matrix, and hence



j=1

=1 , where β ∈ B;i =1, 2,...,s .

(12.7)

Similarly, in a stochastic automaton, if G(·) is stochas-

tic, we have

=Pr{α(t) =α

|q(t) =q

}, i, j =1, 2,...,s ,

(12.8)

where g

represents the elements of the conditional

probability matrix of dimension s×r. Intuitively, g

de-

notes the probability that, when the automaton is in

state q

, it chooses the action α

.Asin(12.7), we

have



j=1

=1 , for each row i = 1, 2,...,s . (12.9)

Fixed Structure Learning Automata

In a stochastic LA, if the conditional probabilities f

and g

are constant, i. e., they do not vary with the

time step t and the input sequence, the automaton is

termed a ﬁxed structure stochastic automaton (FSSA).

The popular examples of these types of automata were

proposed by Tsetlin [12.1, 2], Krylov [12.26], and

Krinsky [12.27] – all of which are -optimal. Their de-

tails can be found in [12.3].

Variable Structure Learning Automata

Unlike the FSSA, variable structure stochastic au-

tomata (VSSA) are those in which the state transition

probabilities are not ﬁxed. In such automata, the state

transitions or the action probabilities themselves are up-

dated at every time instant using a suitable scheme.

The transition probabilities f

and the output func-

tion g

vary with time, and the action probabilities

are updated on the basis of the input. These au-

tomata are discussed here in the context of linear

schemes, but the concepts discussed below can be ex-

tended to nonlinear updating schemes as well. The

types of automata that update transition probabilities

with time were introduced in 1963 by Varshavskii and

Vorontsova [12.6]. A VSSA depends on a random-

number generator for its implementation. The action

chosen is dependent on the action probability distri-

bution vector, which is, in turn, updated based on the

reward/penalty input that the automaton receives from

the RE.

Deﬁnition 12.6

A VSSA is a quintuple Q, A, B, T, where Q rep-

resents the different states of the automaton, A is

the set of actions, B is the set of responses from

the environment to the LA, G is the output func-

tion, and T is the action probability updating scheme

T :[0, 1]

× A× B →[0, 1]

, such that

P(t +1) = T[P(t),α(t),β(t)],

(12.10)

where P(t) is the action probability vector.

Normally, VSSA involve the updating of both the

state and action probabilities. For the sake of simplic-

ity, in practice, it is assumed that in such automata, each

state corresponds to a distinct action, in which case the

action transition mapping G becomes the identity map-

ping, and the number of states, s, is equal to the number

of actions, r (s =r < ∞).

VSSA can be analyzed using a discrete-time

Markov process, deﬁned on a suitable set of states.

If a probability updating scheme T is time invariant,

{P(t)}

t≥0

is a discrete-homogenous Markov process,

and the probability vector at the current time instant

P(t) (along with α(t)andβ(t)) completely determines

P(t +1). Hence, each distinct updating scheme, T,

identiﬁes a different type of learning algorithm, as fol-

lows:

•

Absorbing algorithms are those in which the updat-

ing scheme, T, is chosen in such a manner that the

Markov process has absorbing states;

•

Nonabsorbing algorithms are those in which the

Markov process has no absorbing states;

•

Linear algorithms are those in which P(t +1) is

a linear function of P(t);

•

Nonlinear algorithms are those in which P(t +1) is

a nonlinear function of P(t).

In a VSSA, if a chosen action α

is rewarded, the

probability for the current action is increased, and the

probabilities for all other actions are decreased. On the

other hand, if the chosen action α

is penalized, the

probability of the current action is decreased, whereas

the probabilities for the rest of the actions could, typi-

cally, be increased. This leads to the following different

types of learning schemes for VSSA:

Part B 12.4

226 Part B Automation Theory and Scientiﬁc Foundations

•

Reward–penalty (RP): In both cases, i.e., when

the automaton is rewarded as well as penalized, the

action probabilities are updated;

•

Inaction–penalty (IP): When the automaton is pe-

nalized the action probability vector is updated,

whereas when the automaton is rewarded the action

probabilities are neither increased nor decreased;

•

Reward–inaction (RI): The action probability vec-

tor is updated whenever the automaton is rewarded,

and is unchanged whenever the automaton is penal-

ized.

A LA is considered to be a continuous automaton if

the probability updating scheme T is continuous, i.e.,

the probability of choosing an action can be any real

number in the closed interval [0, 1].

In a VSSA, if there are r actions operating in a sta-

tionary environment with β ={0, 1}, a general action

probability updating scheme for a continuous automa-

ton is described below. We assume that the action α

chosen, and thus, α(t) =α

. The updated action proba-

bilities can be speciﬁed as

for β(t) =0 , ∀j =i , p

(t +1) = p

(t)−g

[P(t)],

for β(t) =1 , ∀j = i , p

(t +1) = p

(t)+h

[P(t)].

(12.11)

Since P(t) is a probability vector,

(

j=1

(t) =1.

Therefore,

when β(t) =0 ,

(t +1) = p

(t)+



j=1, j=i

[P(t)],

and when β(t) =1 ,

(t +1) = p

(t)−



j=1, j=i

[P(t)]. (12.12)

Table 12.1 Properties of the continuous learning schemes

Learning Learning Usefulness Optimality Ergodic/absorbing

scheme parameters (good/bad) (when useful)

a > 0, Good -optimal Absorbing

b =0 as a →0 (stationary E)

a =0, Ver y b ad Not even Ergodic

b > 0 expedient (nonstationary E)

a =b, Bad Never Ergodic

(symmetric) a, b > 0 -optimal (nonstationary E)

R− P

a > 0, Good -optimal Ergodic

b a as a →0 (nonstationary E)

The functions h

and g

are nonnegative andcontinuous

in [0, 1], and obey

∀i = 1, 2,...,r , ∀P ∈ (0, 1)

0 < g

(P) < p

, and

0 <



j=1, j=i

(P)]< 1 . (12.13)

For continuous linear VSSA, the following four learn-

ing schemes are extensively studied in the literature.

They are explained for the two-action case; their exten-

siontother-action case, wherer > 2, is straightforward

and can be found in [12.3]. The four learning schemes

are:

•

The linear reward–inaction scheme (L

)

•

The linear inaction–penalty scheme (L

)

•

The symmetric linear reward–penalty scheme

)

•

The linear reward– -penalty scheme (L

R− P

For a two-action LA,let

[P(t)]=ap

(t)and

[P(t)]=b(1− p

(t)) . (12.14)

In (12.14), a and b are called the reward and penalty

parameters, and they obey the following inequalities:

0 < a < 1, 0 ≤b < 1. Equation (12.14) will be used

further to develop the action probability updating equa-

tions. The above-mentioned linear schemes are quite

popular in LA because of their analytical tractability.

They exhibit signiﬁcantly different characteristics, as

can be seen in Table 12.1.

The L

scheme was ﬁrst introduced by Nor-

man [12.28], and then studied by Shapiro and Naren-

dra [12.29]. It is based on the principle that, whenever

the automaton receives a favorable response (i.e., re-

ward) from the environment, the action probabilities are

Part B 12.4

Cybernetics and Learning Automata 12.4 Classiﬁcation of Learning Automata 227

updated in alinear manner,whereas ifthe automatonre-

ceives an unfavorable response (i.e., penalty) from the

environment, they are unaltered.

The probability updating equations for this scheme

can be simpliﬁed to

(t +1) = p

(t)+a[1− p

(t)],

if α(t) =α

, and β(t) =0 ,

(t +1) =(1−a)p

(t) ,

if α(t) =α

, and β(t) =0 ,

(t +1) = p

(t) ,

if α(t) =α

or α

, and β(t) =1 . (12.15)

We see that, if action α

is chosen, and a reward is re-

ceived, the probability p

(t) is increased, and the other

probability p

(t)(i.e.,j =i) is decreased. Ifeither α

is chosen,and a penaltyis received, P(t) is unaltered.

Equation (12.15) shows that the L

scheme has the

vectors [1, 0]



and [0, 1]



as two absorbing states. In-

deed, with probability 1, it gets absorbed into one of

these absorbing states. Therefore, the convergence of

the L

scheme is dependent on the nature of the initial

conditions and probabilities. The scheme is not suitable

for nonstationary environments. On the other hand, for

stationary random environments, the L

scheme is both

absolutely expedient, and -optimal [12.3].

The L

and L

schemes are devised similarly, and

are omitted from further discussions. They, and their

respective analysis, can be found in [12.3].

The so-calledsymmetry conditions for the functions

g(·)andh(·) to lead to absolutely expedient LA are also

derived in [12.3,8].

Table 12.2 Properties of the discretized learning schemes

Learning Learning Usefulness Optimality Ergodic/absorbing

scheme parameters (good/bad) (as N →∞) (when useful)

N > 0 Good -optimal Absorbing

(stationary E)

N > 0 Ve ry b ad Expedient Ergodic

(nonstationary E)

ADL

N > 0 Good, sluggish -optimal Artiﬁcially absorbing

(stationary environments)

N > 0 Reasonable -optimal Ergodic

if c

min

< 0.5 (nonstationary E)

ADL

N > 0 Good -optimal Artiﬁcially absorbing

(stationary E)

MDL

N > 0 Good -optimal Ergodic

(nonstationary E)

Discretized Learning Automata

The VSSA algorithms presented in Sect. 12.4.2 are con-

tinuous, i.e., the action probabilities can assume any

real value in the interval [0, 1].InLA, the choice of

an action is determined by a random-number generator

(RNG). In order to increase the speed of convergence

of these automata, Thathachar and Oommen [12.30]

introduced the discretized algorithms for VSSA,in

which they suggested the discretization of the prob-

ability space. The different properties (absorbing and

ergodic) of these learning automata, and the updating

schemes of action probabilities for these discretized au-

tomata (like their continuous counterparts), were later

studied in detail by Oommen et al. [12.31–34].

Discretized automata can be perceived to be some-

what like a hybrid combination of FSSA and VSSA.

Discretization is conceptualized by restricting the prob-

ability of choosing the actions to only a ﬁxed number

of values in the closed interval [0, 1]. Thus, the updat-

ing of the action probabilities is achieved in steps rather

than in a continuous manner as in the case of contin-

uous VSSA. Evidently, like FSSA, they possess ﬁnite

sets, but because they have action probability vectors

which are random vectors, they behave like VSSA.

Discretized LA can also be of two types:

(i) Linear – in which case the action probability values

are uniformly spaced in the closed interval [0, 1]

(ii) Nonlinear – in which case the probability values are

unequally spaced in the interval [0, 1] [12.30, 32–

34].

Perhaps the greatest motivation behind discretiza-

tion is overcoming the persistent limitation of con-

Part B 12.4

228 Part B Automation Theory and Scientiﬁc Foundations

tinuous learning automata, i. e., the slow rate of

convergence. This is achieved by narrowing the un-

derlying assumptions of the automata. Originally, the

assumption was that the RNGs could generate real val-

ues with arbitrary precision. In the case of discretized

LA, if an action probability is reasonably close to unity,

the probability of choosing that action increases to unity

(when the conditions are appropriate) directly, rather

than asymptotically [12.30–34].

The second important advantage of discretization is

that it is more practical in the sense that the RNGsused

by continuous VSSA can only theoretically be assumed

to adopt any value in the interval [0, 1], whereas almost

all machine implementations of RNGs use pseudo-

RNGs. Inother words,the setof possible random values

is not inﬁnite in [0, 1], but ﬁnite.

Last, but not the least, discretization is also im-

portant in terms of implementation and representation.

Discretized implementations of automata use integers

for tracking the number of multiples of 1/N of the ac-

tion probabilities, where N is the so-called resolution

parameter. This not only increases the rate of conver-

gence of the algorithm, but also reduces the time, in

terms of the clock cycles it takes for the processor to do

each iteration of the task, and the memory needed. Dis-

cretized algorithms have been proven to be both more

time and space efﬁcient than the continuous algorithms.

Similar to the continuous LA paradigm, the dis-

cretized versions, the DL

, DL

,andDL

automata,

have also been reported. Their design, analysis, and

properties are given in [12.30,32–34], and are summa-

rized in Table 12.2.

12.5 Estimator Algorithms

12.5.1 Rationale and Motivation

As we have seen so far, the rate of convergence of

learning algorithms is one of the most important con-

siderations, which was the primary reason for designing

the family of discretized algorithms. With the same

goal Thathachar and Sastry designed a new-class of al-

gorithms, called the estimator algorithms [12.35–38],

which have faster rate of convergence than all the previ-

ous families. These algorithms, like the previous ones,

maintain and update an action probability vector. How-

ever, unlike the previous ones, these algorithms also

keep running estimates for each action that is rewarded,

using a reward–estimate vector, and then use those esti-

mates in the probability updating equations. The reward

estimates vector is, typically, denoted in the literature

D(t) =[

(t),...,

(t)]



. The corresponding state

vector is denoted by Q(t) =P(t),

D(t).

In a random environment, these algorithms help

in choosing an action by increasing the conﬁdence in

the reward capabilities of the different actions; for ex-

ample, these algorithms initially process each action

a number of times, and then (in one version) could

increase the probability of the action with the high-

est reward estimate [12.39]. This leads to a scheme

with better accuracy in choosing the correct action.

The previous nonestimatorVSSA algorithms updatethe

probability vector directly on the basis of the response

of the environment to the automaton, where, depend-

ing on the type of vector updating scheme being used,

the probability of choosing a rewarded action in the

subsequent time instant is increased, and the probabili-

ties of choosing the other actions could be decreased.

However, estimator algorithms update the probability

vector based on both the estimate vector and the current

feedback provided by the environment to the automa-

ton. The environment inﬂuences the probability vector

both directly and indirectly, the latter being as a re-

sult of the estimation of the reward estimates of the

different actions. This may, thus, lead to increases in ac-

tion probabilities different from the currently rewarded

action.

Even though there is an added computational cost

involved in maintaining the reward estimates, these es-

timator algorithms have an order of magnitude superior

performance than the nonestimator algorithms previ-

ously introduced. Lanctôt and Oommen [12.31]further

introduced the discretizedversionsof theseestimator al-

gorithms, which were proven to have an even faster rate

of convergence.

12.5.2 Continuous Estimator Algorithms

Thathachar and Sastry introduced the class of con-

tinuous estimator algorithms [12.35–38]inwhichthe

probability updating scheme T is continuous, i.e., the

probability of choosing an action can be any real

number in the closed interval [0, 1]. As mentioned sub-

sequently, the discretized versions of these algorithms

were introduced by Oommen and his co-authors, Lanc-

Part B 12.5

Cybernetics and Learning Automata 12.5 Estimator Algorithms 229

tôt and Agache [12.31,40]. These algorithms are brieﬂy

explained in Sect.12.5.3.

Pursuit Algorithm

The family of pursuit algorithms is a class of estima-

tor algorithms that pursue an action that the automaton

currently perceives to be the optimal one. The ﬁrst pur-

suit algorithm, called the CP

algorithm, introduced

by Thathachar and Sastry [12.36, 41], pursues the op-

timal action by changing the probability of the current

optimal action whether it receives a reward or a penalty

by the environment. In this case, the currently perceived

best action is rewarded, and its action probability value

is increased with a value directly proportional to its

distance to unity, namely 1− p

(t), whereas the less

optimal actions are penalized, and their probabilities

decreased proportionally.

To start with, based on the probability distribution

P(t), the algorithm chooses an action α(t). Whether

the response was a reward or a penalty, it increases

that component of P(t) which has the maximal current

reward estimate, and it decreases the probability corre-

sponding to the rest of the actions. Finally, the algorithm

updates the running estimates of the reward probabil-

ity of the action chosen, this being the principal idea

behind keeping, and using, the running estimates. The

estimate vector

D(t) can be computed using the fol-

lowing formula which yields the maximum-likelihood

estimate

(t) =

(t)

, ∀i = 1, 2,...,r ,

(12.16)

where W

(t) is the number of times the action α

has

been rewarded until the current time t,andZ

(t)isthe

number of times α

has been chosen until the current

time t. Based on the above concepts, the CP

algo-

rithm is formally given in [12.31,39,40].

The algorithm is similar in principle to the L

al-

gorithm, because both the CP

and the L

algorithms

increase/decrease the action probabilities of the vector,

independent of whether the environment responds to

the automaton with a reward or a penalty. The major

differencelies in the way the reward estimates are main-

tained, used, and are updated on both reward/penalty. It

should be emphasized that, whereas the nonpursuit al-

gorithm moves the probability vector in the direction

of the most recently rewarded action, the pursuit algo-

rithm moves the probability vector in the direction of

the action with the highest reward estimate. Thathachar

and Sastry [12.41] have theoretically proven their -

optimality, and experimentally proven that these pursuit

algorithms are more accurate, and several orders of

magnitude faster than the nonpursuit algorithms.

The reward–inaction version of this pursuit al-

gorithm is also similar in design, and is described

in [12.31, 40]. Other pursuit-like estimator schemes

have also been devised and can be found in [12.40].

TSE Algorithm

A more advanced estimator algorithm, which we refer

to as the TSE algorithm to maintain consistency with

the existing literature [12.31, 39,40], was designed by

Thathachar and Sastry [12.37,38].

Like the other estimator algorithms, the TSE al-

gorithm maintains the running reward estimates vector

D(t) and uses it to calculate the action probability vec-

tor P(t). When an action α

(t) is rewarded, according

to the TSE algorithm, the probability components with

a reward estimate greater than

(t) are treated differ-

ently from those components with a value lower than

(t). The algorithm does so by increasing the proba-

bilities for all the actions that have a higher estimate

than the estimate of the chosen action, and decreasing

the probabilities of all the actions with a lower esti-

mate. This is done with the help of an indicator function

(t) which assumes the value 1 if

(t) >

(t)and

the value 0 if

(t) ≤

(t). Thus, the TSE algorithm

uses both the probability vector P(t) and the reward

estimates vector

D(t) to update the action probabili-

ties. The algorithm is formally described in [12.39]. On

careful inspection of the algorithm, it can be observed

that P(t +1) depends indirectly on the response of the

environment to the automaton. The feedback from the

environment changes the values of the components of

D(t), which, in turn, affects the values of the functions

f(·)andS

(t) [12.31,37–39].

Analyzing the algorithm carefully, we obtain three

cases. If the i-th action is rewarded, the probability val-

ues of the actions with reward estimates higher than

the reward estimate of the currently selected action are

updated using [12.37]

(t +1)

= p

(t)−λ





(t)−

(t)



(t)− p

(t)p

(t)]

r −1



;

(12.17)

when

(t) <

(t), since the function f



(t)−

(t)



is monotonic and increasing, f



(t)−

(t)



is seen to

be negative. This leads to a higher value of p

(t +1)

than that of p

(t), which indicates that the probabil-

ity of choosing actions that have estimates greater than

Part B 12.5

230 Part B Automation Theory and Scientiﬁc Foundations

that of the estimates of the currently chosen action will

increase.

For all the actions with reward estimates smaller

than the estimate of the currently selected action, the

probabilities are updated based on

(t +1) = p

(t)−λ f



(t)−

(t)



(t) . (12.18)

The sign of the function f



(t)−

(t)



is negative,

which indicates that the probability of choosing actions

that have estimates less than that of the estimate of the

currently chosen action will decrease.

Thathachar and Sastry have proven that the TSE

algorithm is -optimal [12.37]. They have also experi-

mentally shown that the TSE algorithm often converges

several orders of magnitude faster than the L

scheme.

Generalized Pursuit Algorithm

Agache and Oommen [12.40] proposed a generalized

version of the pursuit algorithm (CP

) proposed by

Thathachar and Sastry [12.36, 41]. Their algorithm,

called the generalized pursuit algorithm (GPA), gen-

eralizes Thathachar and Sastry’s pursuit algorithm by

pursuing all those actions that possess higher reward

estimates than the chosen action. In this way the proba-

bility of choosing a wrong action is minimized. Agache

and Oommen experimentally compared their pursuit al-

gorithm with the existing algorithms, and found that

their algorithm is the best in terms of the rate of

convergence [12.40].

In the CP

algorithm, the probability of the

best estimated action is maximized by ﬁrst decreas-

ing the probability of all the actions in the following

manner [12.40]

(t +1) =(1−λ)p

(t) , j = 1, 2,...,r .

(12.19)

The sum of the action probabilities is made unity

by the help of the probability mass Δ, which is given

by [12.40]

Δ =1−



j=1

(t +1) =1−



j=1

(1−λ)p

(t)

=1−



j=1

(t)+λ



j=1

(t) =λ. (12.20)

Thereafter, the probability mass Δ is added to the prob-

ability of the best estimated action. The GPA algorithm,

thus, equidistributes the probability mass Δ to the ac-

tion estimated to be superior to the chosen action. This

gives us [12.40]

(t +1) =(1−λ)p

(t)+Δ = (1−λ)p

(t)+λ,

(12.21)

where

= max

j=1,2,...,r



(t)



. Thus, the updating

scheme is given by [12.40]

(t +1) =(1−λ)p

(t)+

K(t)

(t) >

(t) , j =i ,

(t +1) =(1−λ)p

(t) ,

(t) ≤

(t) , j =i ,

(t +1) =1−



j=i

(t +1) , (12.22)

where K(t) denotesthe number of actions that have esti-

mates greaterthan theestimate ofthe reward probability

of the action currently chosen. The formal algorithm is

omitted, but can be found in [12.40].

12.5.3 Discrete Estimator Algorithms

As we have seen so far, discretized LA are superior to

their continuous counterparts, and the estimator algo-

rithms are superior to the nonestimator algorithms in

terms of the rate of convergence of the learning algo-

rithms. Utilizing the previously proven capabilities of

discretization in improving the speed of convergence of

the learning algorithms, Lanctôt and Oommen [12.31]

enhanced the pursuit and the TSE algorithms. This

led to the designing of classes of learning algorithms,

referred to in the literature as the discrete estimator al-

gorithms (DEA) [12.31]. To this end, as done in the

previous discrete algorithms, the components of the ac-

tion probability vector are allowed to assume a ﬁnite set

of discrete values in the closed interval [0, 1], which is,

in turn, divided into a number of subintervals propor-

tional to the resolution parameter N. Along with this,

a reward estimate vector is maintained to keep an esti-

mate of the reward probability of each action [12.31].

Lanctôt and Oommen showed that, for each mem-

ber algorithm belonging to the class of DEAstobe

-optimal, it must possess a pair of properties known as

the property of moderation and the monotone property.

Together these properties help prove the -optimality of

any DEA algorithm [12.31].

Moderation Property

A DEA with r actions and a resolution parameter N is

said to possess the property of moderation if the max-

Part B 12.5

Cybernetics and Learning Automata 12.5 Estimator Algorithms 231

imum magnitude by which an action probability can

decrease per iteration is bounded by 1/(rN).

Monotone Property

Suppose there exists an index m and a time instant

< ∞, such that

(t) >

(t), ∀j s.t. j =m and ∀t s.t.

t ≥ t

, where

(t) is the maximal component of

D(t).

A DEA is said to possess the monotone property if there

exists an integer N

such that, for all resolution param-

eters N > N

, p

(t) →1 with probability 1 as t →∞,

where p

(t) is the maximal component of P(t).

The discretized versions of the pursuit algorithm,

and the TSE algorithm possessing the moderation and

monotone properties, are presented in the next section.

Discrete Pursuit Algorithm

The discrete pursuit algorithm (formally described

in [12.31]), is referred to as the DPA in the literature,

and is similar to a great extent to its continuous pursuit

counterpart, i.e., the CP

algorithm, except that the up-

dates to the action probabilities for the DPA algorithm

are made in discrete steps. Therefore, the equations in

the CP

algorithm that involve multiplication by the

learning parameter λ are substituted by the addition or

subtraction of quantities proportional to the smallest

step size.

As in the CP

algorithm, the DPA algorithm op-

erates in three steps. If Δ =1/(rN) (where N denotes

the resolution, and r the number of actions) denotes

the smallest step size, the integral multiples of Δ de-

note the step sizes in which the action probabilities

are updated. Like the continuous reward–inaction algo-

rithm, when the chosen action α(t) =α

is penalized,

the action probabilities remain unchanged. However,

when the chosen action α(t) =α

is rewarded, and the

algorithm has not converged, the algorithm decreases,

by the integral multiples of Δ, the action probabil-

ities which do not correspond to the highest reward

estimate.

Lanctôt and Oommen have shown that the DPA

algorithm possesses the properties of moderation and

monotonicity, and that it is thus -optimal [12.31].

They have also experimentally proved that, in differ-

ent ranges of environments from simple to complex,

the DPA algorithm is at least 60% faster than the CP

algorithm [12.31].

Discrete TSE Algorithm

Lanctôt and Oommen also discretized the TSE algo-

rithm, and have referred to it as the discrete TSE

algorithm (DTSE) [12.31]. Since the algorithm is based

on the continuous version of the TSE algorithm, it ob-

viously has the same level of intricacy, if not more.

Lanctôt and Oommen theoretically proved that, like

the DPA estimator algorithm, this algorithm also pos-

sesses the moderation and the monotone properties,

while maintaining many of the qualities of the contin-

uous TSE algorithm. They also provided the proof of

convergence of this algorithm.

There are two notable parameters in the DTSE algo-

rithm:

1. Δ = 1/(rNθ), where N is the resolution parameter

as before

2. θ, an integer representing the largest value by which

any of the action probabilities can change in a single

iteration.

A formal description of theDTSE algorithmis omit-

ted here, but can be found in [12.31].

Discretized Generalized Pursuit Algorithm

Agache and Oommen [12.40] provided a discretized

version of their GPA algorithm presented earlier.

Their algorithm, called the discretized generalized pur-

suit algorithm (DGPA), also essentially generalizes

Thathachar and Sastry’s pursuit algorithm [12.36,41].

However, unlike the TSE, it pursues all those actions

that possess higher reward estimates than the chosen

action.

In essence, in any single iteration, the algorithm

computes the number of actions that have higher reward

estimates than the current chosen action, denoted by

K(t), whence the probability of all the actions that have

estimates higher than the chosen action is increased

by an amount Δ/K(t), and the probabilities for all the

other actions are decreased by an amount Δ/(r −K(t)),

where Δ = 1/(rN) denotes the resolution step, and N

the resolution parameter. The DGPA algorithm has been

proven to possess the moderation and monotone prop-

erties, and is thus -optimal [12.40]. The detailed steps

of the DGPA algorithm are omitted here.

12.5.4 Stochastic Estimator Learning

Algorithm (SELA)

The SELA algorithm belongs to the class of dis-

cretized LA, and was proposed by Vasilakos and

Papadimitriou [12.42]. It has, since then, been used

for solving problems in the domain of computer net-

works [12.18, 43]. It is an ergodic scheme, which has

the ability to converge to the optimal action irrespective

of the distribution of the initial state [12.18,42].

Part B 12.5

232 Part B Automation Theory and Scientiﬁc Foundations

As before, let A ={α

,α

,...,α

} denote the set

of actions and B ={0, 1} denote the set of responses

that can be provided by the environment, where β(t)

represents the feedback provided by the environment

corresponding to a chosen action α(t) at time t.Let

the probability of choosing the k-th action at the t-th

time instant be p

(t). SELA updates the estimated en-

vironmental characteristics as the vector E(t), which

can be deﬁned as E(t) =D(t), M(t), U(t), explained

below.

D(t) ={d

(t), d

(t),...,d

(t)}represents the vector

of the reward estimates, where

(t) =



i=1

(t) . (12.23)

In (12.23), the numerator on the right-hand side repre-

sents the total rewardsreceivedby theLA in the window

size representing the last W times a particular action α

was selected by the algorithm. W is called the learning

window.

The second parameter in E(t) is called the oldness

vector, and is represented as M(t) ={m

(t), m

(t),...,

(t)}, where m

(t) represents the time passed (counted

as the number of iterations)since the last time the action

(t) was selected.

The last parameter U(t) is called the stochas-

tic estimator vector and is represented as U(t) =

(t), u

(t),...,u

(t)}, where the stochastic estimate

(t)ofactionα

is calculated using

(t) =d

(t)+N



0,σ

(t)



, (12.24)

where N



0,σ

(t)



represents a random number se-

lected from a normal distribution that has a mean of 0

and a standard deviation of σ

(t) =min{σ

max

, am

(t)},

and a is a parameter signifying the rate at which the

stochastic estimates become independent, and σ

max

rep-

resents the maximum possible standard deviation that

the stochastic estimates can have. In symmetrically dis-

tributed noisy stochastic environments, SELA is shown

to be -optimal, and has found applications for routing

in ATM networks [12.18,43].

12.6 Experiments and Application Examples

All the continuous and the discretized versions of

the estimator algorithms presented above were ex-

perimentally evaluated [12.31, 40]. Lanctôt and Oom-

men [12.31]compared therates of convergencebetween

the discretized and the continuous versions of the

pursuit and the TSE estimator algorithms. In their ex-

periments, they required that their algorithm achieve

a level of accuracy of not making any errors in

convergence in 100 experiments. To initialize the re-

ward estimates vector, 20 iterations were performed

for each action. The experimental results for the TSE

algorithms are summarized in Table 12.3. The corre-

Table 12.3 The number of iterations until convergence

in two-action environments for the TSE algorithms (af-

ter [12.31])

Probability of reward Meaniterations

Action 1 Action 2 Continuous Discrete

0.800 0.200 28.8 24.0

0.800 0.400 37.0 29.0

0.800 0.600 115.0 76.0

0.800 0.700 400.0 380.0

0.800 0.750 2200.0 1200.0

0.800 0.775 8500.0 5600.0

sponding results of the pursuit algorithms are provided

in Table 12.4 (the numbers indicate the number of it-

erations required to attain to convergence). The results

show that the discretized TSE algorithm is faster (be-

tween 50–76%) than the continuous TSE algorithm.

Similar observations were obtained for the pursuit algo-

rithm. The discretized versionsof the pursuit algorithms

were found to be at least 60% faster than their con-

tinuous counterparts; for example, with d

= 0.8and

= 0.6, the continuous TSE algorithm required an

average of 115 iterations to converge, whereas the dis-

cretized TSE took only 76. Another set of experimental

Table 12.4 The number of iterations until convergence in

two-action environments for the pursuit algorithms (af-

ter [12.31])

Probability of reward Meaniterations

Action 1 Action 2 Continuous Discrete

0.800 0.200 22 22

0.800 0.400 22 39

0.800 0.600 148 125

0.800 0.700 636 357

0.800 0.750 2980 1290

0.800 0.775 6190 3300

Part B 12.6

Cybernetics and Learning Automata 12.7 Emerging Trends and Open Challenges 233

Table 12.5 Comparison of the discrete and continuous

estimator algorithms in a benchmark with ten-action en-

vironments (after [12.31])

Environment Algorithm Continuous Discrete

Pursuit 1140 799

TSE 310 207

Pursuit 2570 1770

TSE 583 563

comparisons was performed between all the estima-

tor algorithms presented so far in several ten-action

environments [12.31]. Their results [12.31] are summa-

rized in Table 12.5, and show that the TSE algorithm

is much faster than the pursuit algorithm. Whereas the

continuous pursuit algorithm required 1140 iterations to

converge, the TSE algorithm took only 310. The same

observation applies to their discrete versions. Similarly,

it was observed that the discrete estimator algorithms

were much faster than the continuous estimator algo-

rithms; for example, for environment E

, while the

Table 12.6 Experimental comparison of the performance

of the GPA and the DGPA algorithms in benchmark ten-

action environments (after [12.40])

Environ- GPA DGPA

ment Number Number

λ of iterations N of iterations

0.0127 948.03 24 633.64

0.0041 2759.02 52 1307.76

Note: The reward probabilities for the actions are:

: 0.70.50.30.20.40.50.40.30.50.2

: 0.10.45 0.84 0.76 0.20.40.60.70.50.3

continuous algorithm took 1140 iterations to converge,

the discretized algorithm needed only 799 iterations.

The GPA and the DGPA algorithms were compared

for the benchmark ten-action environments. The results

are summarized in Table 12.6. The DGPA algorithm

was found to converge much faster than the GPA al-

gorithm. This, once again, proves the superiority of the

discretized algorithms over the continuous ones.

12.7 Emerging Trends and Open Challenges

Although the ﬁeld of LA is relatively young, the

analytic results that have been obtained are quite phe-

nomenal. Simultaneously, however, it is also fair to

assert that the tools available in the ﬁeld have been far

too underutilized in real-life problems.

We believe that the main areas of research that

will emerge in the next few years will involve apply-

ing LA to a host of application domains. Here, as the

saying goes, the sky is the limit, because LA can prob-

ably be used in any application where the parameters

characterizing the underlying system are unknown and

random. Some possible potential applications are listed

below:

1. LA could be used in medicine to help with the diag-

nosis process.

2. LA have potential applications in intelligent tuto-

rial (or tutorial-like) systems to assist in imparting

imperfect knowledge to classrooms of students,

where the teacher is also assumed to be imperfect.

Some initial work is already available in this re-

gard [12.44].

3. The use of LA in legal arguments and the associated

decision-making processes is open.

4. Although LA have been used in some robotic ap-

plications, as far as we know, almost no work has

been done for obstacle avoidance and intelligent

path planning of real-life robots.

5. We are not aware of any results that use LA in the

biomedical applicationdomain. Inparticular, we be-

lieve that they can be fruitfully utilized for learning

targets, and in the drug design phase.

6. One of the earliest applications of LA was in the

routing of telephone calls over land lines, but the

real-life application of LA in wireless and multihop

networks is still relatively open.

We close this section by brieﬂy mentioning that the

main challenge inusing LA for each ofthese application

domains would be that of modeling what the environ-

ment and automaton are. Besides this, the practitioner

would have to consider how the response of a particular

solution can be interpreted as the reward/penalty for the

automaton, or for the network of automata.

Part B 12.7

234 Part B Automation Theory and Scientiﬁc Foundations

12.8 Conclusions

In this chapter we have discussed most of the

important learning mechanisms reported in the lit-

erature pertaining to learning automata (LA). Af-

ter brieﬂy stating the concepts of ﬁxed structure

stochastic LA, the families of continuous and dis-

cretized variable structure stochastic automata were

discussed. The chapter, in particular, concentrated on

the more recent results involving continuous and dis-

cretized pursuit and estimator algorithms. In each

case we have brieﬂy summarized the theoretical

and experimental results of the different learning

schemes.

References

12.1 M.L. Tsetlin: On the behaviour of ﬁnite automata

in random media, Autom. Remote Control 22,1210–

1219 (1962), Originally in Avtom. Telemekh. 22,

1345–1354 (1961), in Russian

12.2 M.L. Tsetlin: Automaton Theory and Modeling of

Biological Systems (Academic, New York 1973)

12.3 K.S. Narendra, M.A.L. Thathachar: Learning Au-

tomata (Prentice-Hall, Upper Saddle River 1989)

12.4 R.R. Bush, F. Mosteller: Stochastic Models for

Learning (Wiley, New York 1958)

12.5 C.R. Atkinson, G.H. Bower, E.J. Crowthers: An Intro-

duction to Mathematical Learning Theory (Wiley,

New York 1965)

12.6 V.I. Varshavskii, I.P. Vorontsova: On the behavior

of stochastic automata with a variable structure,

Autom. Remote Control 24, 327–333 (1963)

12.7 M.S. Obaidat, G.I. Papadimitriou, A.S. Pomportsis:

Learning automata: theory, paradigms, and appli-

cations, IEEE Trans. Syst. Man Cybern. B 32, 706–709

(2002)

12.8 S. Lakshmivarahan: Learning Algorithms Theory

and Applications (Springer, New York 1981)

12.9 K. Najim, A.S. Poznyak: Learning Automata: Theory

and Applications (Pergamon, Oxford 1994)

12.10 A.S. Poznyak, K. Najim: Learning Automata and

Stochastic Optimization (Springer, Berlin 1997)

12.11 M.A.L.T. Thathachar, P.S. Sastry: Networks of

Learning Automata: Techniques for Online Stochas-

tic Optimization (Kluwer, Boston 2003)

12.12 S. Misra, B.J. Oommen: GPSPA: a new adaptive al-

gorithm for maintaining shortest path routing trees

in stochastic networks, Int. J. Commun. Syst. 17,

963–984 (2004)

12.13 M.S. Obaidat, G.I. Papadimitriou, A.S. Pomportsis,

H.S. Laskaridis: Learning automata-based bus ar-

bitration for shared-medium ATM switches, IEEE

Trans. Syst. Man Cybern. B 32, 815–820 (2002)

12.14 B.J. Oommen, T.D. Roberts: Continuous learning

automata solutions to the capacity assignment

problem, IEEE Trans. Comput. C 49, 608–620 (2000)

12.15 G.I. Papadimitriou, A.S. Pomportsis: Learning-

automata-based TDMA protocols for broadcast

communication systems with bursty trafﬁc, IEEE

Commun. Lett. 3(3), 107–109 (2000)

12.16 A.F. Atlassis, N.H. Loukas, A.V. Vasilakos: The use of

learning algorithms in atm networks call admission

control problem: a methodology, Comput. Netw.

34, 341–353 (2000)

12.17 A.F. Atlassis, A.V. Vasilakos: The use of reinforce-

ment learning algorithms in trafﬁc control of high

speed networks. In: Advances in Computational

Intelligence and Learning (Kluwer, Dordrecht 2002)

pp. 353–369

12.18 A. Vasilakos, M.P. Saltouros, A.F. Atlassis,

W. Pedrycz: Optimizing QoS routing in hierarchi-

cal ATM networks using computational intelligence

techniques, IEEE Trans. Syst. Sci. Cybern. C 33,297–

312 (2003)

12.19 F. Seredynski: Distributed scheduling using simple

learning machines, Eur. J. Oper. Res. 107,401–413

(1998)

12.20 J. Kabudian, M.R. Meybodi, M.M. Homayounpour:

Applying continuous action reinforcement learn-

ing automata (CARLA) to global training of hidden

Markov models, Proc. ITCC’04 (Las Vegas 2004)

pp. 638–642

12.21 M.R. Meybodi, H. Beigy: New learning automata

based algorithms for adaptation of backpropaga-

tion algorithm parameters, Int. J. Neural Syst. 12,

45–67 (2002)

12.22 C. Unsal, P. Kachroo, J.S. Bay: Simulation study of

multiple intelligent vehicle control using stochastic

learning automata, Trans. Soc. Comput. Simul. Int.

14, 193–210 (1997)

12.23 B.J. Oommen, E.V. de St. Croix: Graph partitioning

using learning automata, IEEE Trans. Comput. C 45,

195–208 (1995)

12.24 G. Santharam, P.S. Sastry, M.A.L. Thathachar: Con-

tinuous action set learning automata for stochastic

optimization, J. Franklin Inst. 331(5), 607–628

(1994)

12.25 B.J. Oommen, G. Raghunath, B. Kuipers: Parameter

learning from stochastic teachers and stochastic

compulsive liars, IEEE Trans. Syst. Man Cybern. B

36,820–836(2006)

12.26 V. Krylov: On the stochastic automaton which is

asymptotically optimal in random medium, Au-

tom. Remote Control 24, 1114–1116 (1964)

Part B 12