Open access peer-reviewed chapter

Superposition-Inspired Reinforcement Learning and Quantum Reinforcement Learning

By Chun-Lin Chen and Dao-Yi Dong

Published: January 1st 2008

DOI: 10.5772/5275

Downloaded: 3978

1. Introduction

Reinforcement Learning (RL) remains an active research area for a long time (Kaelbling et al., 1996, Sutton & Barto, 1998) and is still one of the most rapidly developing machine learning methods in recent years (Barto & Mahadevan, 2003). Related algorithms and techniques have been used in different applications such as motion control, operations research, robotics and sequential decision process (He & Jagannathan, 2005, Kondo & Ito, 2004, Morimoto & Doya, 2001, Chen et al., 2006b). However how to speed up learning has always been one of the key problems for the theoretical research and applications of RL methods (Sutton & Barto, 1998).

Recently there comes up a new approach for solving this problem owning to the rapid development of quantum information and quantum computation (Preskill, 1998, Nielsen & Chuang, 2000). Some results have shown that quantum computation can efficiently speed up the solutions of some classical problems, and even can solve some difficult problems that classical algorithms can not solve. Two important quantum algorithms, Shor’s factoring algorithm (Shor, 1994, Ekert & Jozsa, 1996) and Grover’s searching algorithm (Grover, 1996, Grover, 1997), have been proposed in 1994 and 1996 respectively. Shor’s factoring algorithm can give an exponential speedup for factoring large integers into prime numbers and its experimental demonstration has been realized using nuclear magnetic resonance (Vandersypen et al., 2001). Grover’s searching algorithm can achieve a square speedup over classical algorithms in unsorted database searching and its experimental implementations have also been demonstrated using nuclear magnetic resonance (Chuang et al., 1998, Jones, 1998a, Jones et al., 1998b) and quantum optics (Kwiat et al., 2000, Scully & Zubairy, 2001). Taking advantage of quantum computation, the algorithm integration inspired by quantum characteristics will not only improve the performance of existing algorithms on traditional computers, but also promote the development of related research areas such as quantum computer and machine learning. According to our recent research results (Dong et al., 2005a, Dong et al., 2006a, Dong et al., 2006b, Chen et al., 2006a, Chen et al., 2006c, Chen & Dong, 2007, Dong et al., 2007a, Dong et al., 2007b), in this chapter the RL methods based on quantum theory are introduced following the developing roadmap from Superposition-Inspired Reinforcement Learning (SIRL) to Quantum Reinforcement Learning (QRL).

As for SIRL methods we concern mainly about the exploration policy. Inspired by the superposition principle of quantum state, in a RL system, a probabilistic exploration policy is proposed to mimic the state collapse phenomenon according to quantum measurement postulate, which leads to a good balance between exploration and exploitation. In this way, the simulated experiments show that SIRL may accelerate the learning process and allow avoiding the locally optimal policies.

When SIRL is extended to quantum mechanical systems, QRL theory is proposed naturally (Dong et al., 2005a, Dong et al., 2007b). In a QRL system, the state value can be represented with quantum state and be obtained by randomly observing the quantum state, which will lead to state collapse according to quantum measurement postulate. The occurrence probability of eigenvalue is determined by probability amplitude, which is updated according to rewards. So this approach represents the whole state-action space with the superposition of quantum state, which leads to real parallel computing and a good tradeoff between exploration and exploitation using probability as well.

Besides the introduction of SIRL and QRL methods, in this chapter, the relationship between different theories and algorithms are briefly analyzed, and their applications are also introduced respectively. The organization of this chapter is as follows. Section 2 gives a brief introduction to the fundamentals of quantum computation, which include the superposition principle, parallel computation and quantum gates. In Section 3, the SIRL method is presented in a probabilistic version through mimicking the quantum behaviors. Section 4 gives the introduction of QRL method based on quantum superposition and quantum parallelism. Related issues and future work are discussed as a conclusion in Section 5.

2. Fundamentals of Quantum Computation

2.1. State superposition and quantum parallel computation

In quantum computation, information unit (also called as qubit) is represented with quantum state and a qubit is an arbitrary superposition state of two-state quantum system (Dirac’s representation) (Preskill, 1998):

|ψ=α|0+β|1E1

whereαandβare complex coefficients and satisfy|α|2+|β|2=1.|0and|1are two orthogonal states (also called basis vectors of quantum state|ψ), and they correspond to logic states 0 and 1.|α|2represents the occurrence probability of|0when the qubit is measured, and|β|2is the probability of obtaining result|1. The physical carrier of a qubit is any two-state quantum system such as two-level atom, spin-1/2 particle and polarized photon. The value of classical bit is either Boolean value 0 or value 1, but a qubit can be prepared in the coherent superposition state of 0 and 1, i.e. a qubit can simultaneously store 0 and 1, which is the main difference between classical computation and quantum computation.

According to quantum computation theory, the quantum computing process can be looked upon as a unitary transformationUfrom input qubits to output qubits. If one applies a transformationUto a superposition state, the transformation will act on all basis vectors of this superposition state and the output will be a new superposition state by superposing the results of all basis vectors. So when one processes functionf(x)by the method, the transformationUcan simultaneously work out many different results for a certain inputx. This is analogous with parallel process of classical computer and is called quantum parallelism. The powerful ability of quantum algorithm is just derived from the parallelism of quantum computation.

Suppose the input qubit|zlies in the superposition state:

|z=12(|0+|1)E2

The transformationUzdescribing computing process is defined as the following:

Uz:|z,y|z,yf(z)E3

where|z,yrepresents the input joint state and|z,yf(z)is the output joint state. Lety=0and we can easily obtain (Nielsen & Chuang, 2000):

Uz|z=12(|0,f(0)+|1,f(1))E4

The result contains information about bothf(0)andf(1), and we seem to evaluatef(z)for two values ofzsimultaneously.

Now consider an n-qubit cluster and it lies in the following superposition state:

|ψ=x=000111nCx|xwhere
x=000111n|Cx|2=1E5

whereCxis complex coefficients and|Cx|2represents occurrence probability of|xwhen state|ψis measured.|xcan take on2nvalues, so the superposition state can be looked upon as the superposition state of all integers from 0 to2n1. SinceUis a unitary transformation, computing functionf(x)can give (Preskill, 1998):

Ux=000111nCx|x,0=x=000111nCxU|x,0=x=000111nCx|x,f(x)E6

Based on the above analysis, it is easy to find that an n-qubit cluster can simultaneously process2nstates. However, this is different from the classical parallel computation, where multiple circuits built to computef(x)are executed simultaneously, since quantum parallel computation doesn’t necessarily make a tradeoff between computation time and needed physical space. In fact, quantum parallelism employs a single circuit to evaluate the function for multiple values ofxsimultaneously by exploiting the quantum state superposition principle and provides an exponential-scale computation space in the n-qubit linear physical space. Therefore quantum computation can effectively increase the computing speed of some important classical functions. So it is possible to obtain significant result through fusing quantum computation into reinforcement learning theory.

2.2. Quantum gates

Analogous to classical computer, quantum computer accomplishes some quantum computation tasks through quantum gates. A quantum gate or quantum logic gate is a basic quantum circuit operating on a small number of qubits. They can be represented by unitary matrices. Here we will introduce several simple quantum gates including quantum NOT gate, Hadamard gate, phase gate and quantum CNOT gate. The detailed description of quantum gates can refer to (Nielsen & Chuang, 2000).

A quantum NOT gate maps|0|1and|1|0respectively and that can be described by the following matrix:

UNOT=[0110]E7

When a quantum NOT gate is applied on a single qubit with state|ψ=α|0+β|1, then the output will become|ψ=α|1+β|0. The symbol for the NOT gate is drawn in Fig.1 (a).

The Hadamard gate is one of the most useful quantum gates and can be represented as:

H=12[111-1]E8

Through the Hadamard gate, a qubit in the state|0is transformed into a superposition state in the two states, i.e.

H|012[1111](10)=12(11)=12|0+12|1E9

Another important gate is phase gate which can be expressed as

Up=[100i]E10
Upgenerates a relative phaseπbetween the two basis states of the input state, i.e.
Up|ψ=α|0+iβ|1E11

The CNOT gate acts on two qubits simultaneously and can be represented by the following matrix:

UCNOT=[1000010000010010]E12

The symbol for the CNOT gate is shown as in Fig.1 (b). If the first control qubit is equal to|1, then CNOT gate flips the target (second) qubit. Otherwise the target remains unaffected. This can be described as follows:

{UCNOT|00=|00UCNOT|01=|01UCNOT|10=|11UCNOT|11=|10E13

Just like AND and NOT form a universal set for classical boolen circuits, the CNOT gate combined with one qubit rotation gate can implement any kind of quantum calculation.

Figure 1.

Symbols for NOT and CNOT gate

3. Superposition-Inspired Reinforcement Learning

Similar the standard RL, SIRL is also a RL method that is designed for the traditional computer, instead of a quantum algorithm. However, it borrows the ideas from quantum characteristics and provides an alternative exploration strategy, i.e., action selection method. In this section, the SIRL will be presented after a brief introduction of the standard RL theory and the existing exploration strategies.

3.1. Reinforcement learning and exploration strategy

Standard framework of RL is based on discrete-time, finite Markov decision processes (MDPs) (Sutton & Barto, 1998). RL algorithms assume that stateSand actionA(sn)can be divided into discrete values. At a certain step, the agent observes the state of the environment (inside and outside of the agent)st, and then choose an actionat. After executing the action, the agent receives a rewardrt+1, which reflects how good that action is (in a short-term sense).

The goal of reinforcement learning is to learn a mapping from states to actions, that is to say, the agent is to learn a policyπ:S×iSA(i)[0,1], so that expected sum of discounted reward of each state will be maximized:

V(s)π=E{rt+1+γrt+2+γ2rt+3+|st=s,π}      =E[rt+1+γV(st+1)π|st=s,π]      =aAsπ(s,a)[rsa+γs'pss'aV(s')π]E14

whereγ[0,1)is discounted factor,π(s,a)is the probability of selecting actionaaccording to statesunder policyπ,pss'a=Pr{st+1=s'|st=s,at=a}is probability for state transition andrsa=E{rt+1|st=s,at=a}is expected one-step reward. Then we have the optimal state-value function

V(s)*=maxaAs[rsa+γs'pss'aV(s')*]E15
π*=argmaxπV(s)π,sSE16

In dynamic programming, (15) is also called Bellman equation ofV*.

As for state-action pairs, there are similar value functions and Bellman equations, whereQπ(s,a)stands for the value of taking actionain statesunder policyπ:

Q(s,a)π=E{rt+1+γrt+2+γ2rt+3+|st=s,at=a,π}         =rsa+γs'pss'aVπ(s')         =rsa+γs'pss'aa'π(s',a')Q(s',a')πE17
Q(s,a)*=maxπQ(s,a)=rsa+γs'pss'amaxa'Q(s',a')*E18
Letαbe the learning rate, the one-step update rule of Q-learning (a widely used reinforcement learning algorithm) (Watkins & Dayan, 1992) is:
Q(st,at)(1α)Q(st,at)+α(rt+1+γmaxa'Q(st+1,a')E19

Besides Q-learning, there are also many other RL algorithms such as temporal difference (TD), SARSA and multi-step version of these algorithms. For more detail, please refer to (Sutton & Barto, 1998).

To approach the optimal policy effectively and efficiently, the RL algorithms always need a certain exploration strategy. One widely used exploration strategy isε-greedy (ε[0,1)), where the optimal action is selected with probability1εand a random action is selected with probabilityε. Sutton and Barto (Sutton & Barto, 1998) have compared the performance of RL for differentε, which shows that a nonzeroεis usually better thanε=0(i.e., blind greedy strategy). Moreover, the exploration probabilityεcan be reduced over time, which moves the agent from exploration to exploitation. Theε-greedy method is simple and effective, but it has one drawback that when it explores it chooses equally among all actions. This means that it makes no difference to choose the worst action or the next-to-best action. Another problem is that it is difficult to choose a proper parameterεwhich can offer the optimal balancing between exploration and exploitation.

Another kind of action selection methods are randomized strategies, such as Boltzmann exploration (i.e., Softmax method) (Sutton & Barto, 1998) and Simulated Annealing (SA) method (Guo et al., 2004). It uses a positive parameterτcalled the temperature and chooses action with the probability proportional toexp(Q(s,a)/τ). Compared withε-greedy method, the greedy action is still given the highest selection probability, but all the others are ranked and weighted according to their value estimates. It can also move from exploration to exploitation by adjusting the "temperature" parameterτ. It is natural to sample actions according to this distribution, but it is very difficult to set and adjust a good parameterτand may converge unnecessarily slowly unless the parameterτis manually tuned with great care. It also has another potential shortcoming that it may works badly when the values of the actions are close and the best action can not be separated from the others. A third problem is that when the parameterτis reduced over time to acquire more exploitation, there is no effective mechanism to guarantee re-exploration when necessary.

Therefore, the existing exploration strategies usually suffer from the difficulties to hold the good balancing between exploration and exploitation and to provide an easy method of parameter setting. Hence new ideas are necessary to explore more effective exploration strategies to achieve better performance. Inspired by the main characteristics of quantum computation, we present the SIRL algorithm with a probabilistic exploration policy.

3.2. Superposition-Inspired RL

The exploration strategy for SIRL is inspired by the state superposition principle of a quantum system and collapse postulate, where a combined action form is adopted to provide a probabilistic mechanism for each state in the SIRL system. At states, the action to be selected is represented as:

as=f(s)=c1a1+c2a2+...+cmam=i=1mciaiE20

Wherei=1mci=10ci1i=1,2,...masis the action to be selected at statesand the action selection set is{a1,a2,...,am}. Equation (20) is not for numerical computation and it just means that at the states, the agent will choose the actionaiwith the occurrence probabilityci, which leads to a natural exploration strategy for SIRL.

After the execution of actionaifrom states, the corresponding probabilityciis updated according to the immediate rewardrand the estimated value of the next stateV(s')

cici+k(r+V(s'))E21

wherekis the updating step and the probability distribution(c1,c2,...,cm)is normalized after each updating process. The procedural algorithm of standard SIRL is shown as in Fig. 2.

Figure 2.

A standard SIRL algorithm

In the SIRL algorithm, the exploration policy is accomplished through a probability distribution over the action set. When the agent is going to choose an action at a certain state, the actionaiwill be selected with probabilityci, which is also updated along with the value funcion updating. Comparing the SIRL algorithm with basic RL algorithms, the main difference is that with the probabilistic exploration policy, the SIRL algorithm makes better tradeoff between exporation and exploitation without bothering to tune it by the designers.

3.3. Simulated experiments

The performance of the SIRL algorithm is tested with two examples, which are a puzzle problem and a mobile robot navigation problem.

1. The puzzle problem

First, let’s consider a puzzle problem as shown in Fig. 3, which is in a13×13(0~12)gridworld environment. From any state the agent can perform one of four primary actions: up, down, left and right, and actions that would lead into a blocked cell are not executed. The task is to find an optimal policy which will let the agent move from S(11,1) to G(1,11) with minimized cost (number of moving steps).

The experiment setting is as follows. Once the agent finds the goal state it receives a reward of 100 and then ends this episode. All steps are punished by a reward of -1. The discount factorγis set to 0.99 for all the algorithms that we have carried out in this example. In this experiment, we compare the proposed method with TD algorithm. For the action selection policy of TD algorithm, we useε-greedy policy (ε= 0.01). As for SIRL method, the action selecting policy uses the values ofcito denote the probability of an action, which is defined asas=f(s)=c1a1+c2a2+...+cmam=i=1mciai. For the four cell-to-cell actionsciis initialized uniformly.

Figure 3.

A puzzle problem. The task is to move from start (S) to goal (G) with minimum number of steps

Figure 4.

Performance of SIRL (the left figure) compared with TD algorithm (the right figure)

The experimental results of the SIRL method compared with TD method are plotted in Fig. 4. It is obvious that at the beginning phase SIRL with this superposition-inspired exploration strategy learns extraordinarily fast, and then steadily converges to the optimal policy that costs 40 steps to the goal G. The results show that the SIRL method makes a good tradeoff between exploration and exploitation.

2. Mobile robot navigation

A simulation environment has also been set up with a larger grid-map of 400×600. And the configuration of main parameters is as follows: learning rateα=0.5, discount factorγ=0.9. Fig. 5. shows the result in complex indoor environment, which verifies the effectiveness of robot learning using SIRL for navigation in large unknown environments.

Figure 5.

Simulation result of robot navigation in indoor environment

4. Quantum Reinforcement Learning

When the SIRL is applied to a real quantum system, for example, to run the algorithm on a quantum computer, the representation and the computation mode will be dramatically different, which will lead to quantum reinforcement learning (QRL). Then we can take the most advantages of this quantum algorithm, such as the speeding up due to quantum parallel computation.

4.1. Representation

One of the most fundamental principles of quantum mechanics is the state superposition principle. As we represent a QRL system with quantum concepts, similarly, we have the following definitions and propositions for QRL.

Definition 1: (Eigenvalue of states or actions) Statessor actionsain a RL system are denoted as corresponding orthogonal quantum states|sn(or|an) and are called the eigenvalue of states or actions in QRL.

Then we get the set of eigenvalues of states:S={|sn}and that of actions for statei:

A(i)={|an}E22

Corollary 1: Every possible state|sor action|acan be expanded in terms of an orthogonal complete set of functions, respectively. We have
|s=nβn|snE23
|a=nβn|anE24

whereβnis probability amplitude, which can be a complex number,|snand|anare eigenvalues of states and actions, respectively. And theβnin equation (22) is not necessarily the same as the ones in equation (23), which just mean this corollary holds for both of|sand|a|βn|2means the probability of corresponding eigenvalues and satisfies

n|βn|2=1E25
Proof: (sketch)

(1) State space{|s}in QRL system is aN-dimension Hilbert space,

(2) States{|sn}in traditional RL system are the eigenvalue of states|sin QRL system, (Definition 1)

Then{|sn}areNlinear independent vectors for thisN-dimension Hilbert space, according to the definition of Hilbert space, any possible state|scan be expanded in terms of the complete set of|sn. And it is the same for action space{|a}

So the states and actions in QRL are different from those in traditional RL.

  1. The sum of several states (or actions) does not have a definite meaning in traditional RL, but the sum of states (or actions) in QRL is still a possible state (or action) of the same quantum system, and it will simultaneously take on the superposition state of some eigenvalues.

  2. The measurement value of|srelates to its probability density. When|stakes on an eigenstate|si, its value is exclusive. Otherwise, its value has the probability of|βi|2to be one of the eigenstate|si

Like what has been described in Section 2, quantum computation is built upon the concept of qubit. Now we consider the systems of multiple qubits and propose a formal representation of them for QRL system.

LetNsandNabe the numbers of states and actions respectively, then choose numbers m and n, which are characterized by the following inequalities:
Ns2m2Ns,Na2n2NaE26

And use m and n qubits to represent eigenstate set S={s} and eigenaction set A={a} respectively:

s:[a1b1|a2b2||ambm], where|ai|2+|bi|2=1
i=1,2,...mE27
a:[α1β1|α2β2||αnβn], where|αi|2+|βi|2=1
i=1,2,...nE28

Thus the states and actions of a QRL system may lie in superposition states:

|s(m)=s=00011...1mCs|sE29
|a(n)=a=00011...1nCa|aE30

whereCsandCacan be complex numbers and satisfy

s=00011...1m|Cs|2=1E31
a=00011...1n|Ca|2=1E32

4.2. Action selection policy

In QRL, the agent is also to learn a policyπ:S×iSA(i)[0,1], which will maximize the expected sum of discounted reward of each state. That is to say, the mapping from states to actions isf(s)=π:SA, and we have

f(s)=|as(n)=a=00011...1nCa|aE33

whereCais probability amplitude of action|aand satisfies (29).

Definition 2: (Collapse) When a quantum state|ψ=nβn|ψnis measured, it will be changed and collapse randomly into one|ψnof its eigenstates with corresponding probability|ψn|ψ|2:
|ψn|ψ|2=|(|ψn)*|ψ|2=|βn|2E34

Then when an action|as(n)is measured, we will get|awith the occurrence probability of|Ca|2. In QRL algorithm, we will amplify the probability of “good” action according to corresponding rewards. It is obvious that the collapse action selection method is not a real action selection method theoretically. It is just a fundamental phenomenon when a quantum state is measured, which results in a good balancing between exploration and exploitation and a natural “action selection” without setting parameters.

4.3. Value function updating and reinforcement strategy

In Corollary 1 we pointed out that every possible state of QRL|scan be expanded in terms of an orthogonal complete set of eigenstate|sn:|s=nβn|sn. If we use an m-qubit register, it will be|s(m)=s=00011...1mCs|s

According to quantum parallel computation theory, a certain unitary transformationUfrom input qubit to output qubit can be implemented. Suppose we have such a “quantum black box” which can simultaneously process these2mstates with the value updating rule

V(s)V(s)+α(r+V(s')V(s))E35

whereαis learning rate, andris the immediate reward. It is like parallel value updating of traditional RL over all states, however, it provides an exponential-scale computation space in the m-qubit linear physical space and can speed up the solutions of related functions.

The reinforcement strategy is accomplished by changing the probability amplitudes of the actions according to the updated value function. As we know that action selection is executed by measuring action|as(n)related to certain state|s(m), which will collapse to|awith the occurrence probability of|Ca|2. So it is no doubt that probability amplitude updating is the key of recording the “trial-and-error” experience and learning to be more intelligent. When an action|ais executed, it should be able to memorize whether it is “good” or “bad” by changing its probability amplitudeCa. For more details, please refer to (Chen et al., 2006a, Dong et al., 2006b, Dong et al., 2007b).

As action|as(n)is the superposition of n possible eigenactions, to find out|aand to change its probability amplitudes are usually interactional for a quantum system. So we simply update the probability amplitude of|as(n)without searching|a, which is inspired by Grover’s searching algorithm (Grover, 1996).

The updating of probability amplitude is based on Grover iteration. First, prepare the equally weighted superposition of all eigenactions

|a0(n)=12n(a=00011...1n|a)E36

This process can be done easily by applying the Hadamard transformation to each qubit of an initial state|a=0. We know that|ais an eigenaction and can get

a|a0(n)=12nE37

Now assume the eigenaction to be reinforced is|aj, and we can construct Grover iteration through combining two reflectionsUajandUa0(n)(Preskill, 1998, Nielsen & Chuang, 2000)

Uaj=I2|ajaj|E38
Ua0(n)=2|a0(n)a0(n)|IE39

whereIis unitary matrix.Uajflips the sign of the action|aj, but acts trivially on any action orthogonal to|aj. This transformation has a simple geometrical interpretation. Acting on any vector in the2n-dimensional Hilbert space,Uajreflects the vector about the hyperplane orthogonal to|aj. On the other hand,Ua0(n)preserves|a0(n), but flips the sign of any vector orthogonal to|a0(n). Grover iteration is the unitary transformation

UGrov=Ua0(n)UajE40

By repeatedly applying the transformationUGrovon|a0(n), we can enhance the probability amplitude of the basis action|ajwhile suppressing the amplitude of all other actions. This can also be looked upon as a kind of rotation in two-dimensional space. Applying Grover iterationUGrovforKtimes on|a0(n)can be represented as

UGrovK|a0(n)=sin((2K+1)θ)|aj+cos((2K+1)θ)|φE41

where|φ=12n1aaj|a,θsatisfyingsinθ=1/2n. Through repeating Grover iteration, we can reinforce the probability amplitude of corresponding action according to the reward value.

Thus when an action|a0(n)is executed, the probability amplitude of|ajis updated by carrying out[k(r+V(s'))](an integer) times of Grover iteration.kis a parameter and the probability amplitudes will be normalized witha|Ca|2=1after each updating.

4.4. Quantum reinforcement learning algorithm

The procedural form of a standard QRL algorithm is described as Fig. 6 (Dong et al., 2007b). QRL is inspired by the superposition principle of quantum state and quantum parallel computation. The state value can be represented with quantum state and be obtained by randomly observing the simulated quantum state, which will lead to state collapse according to quantum measurement postulate. And the occurrence probability of eigenvalue is determined by probability amplitude, which is updated according to rewards. So this approach represents the whole state-action space with the superposition of quantum state and makes a good tradeoff between exploration and exploitation using probability. The merit of QRL is twofold. First, as for simulation algorithm on traditional computer it is an effective algorithm with novel representation and computation methods. Second, the representation and computation mode are consistent with quantum parallel computation system and can speed up learning in exponential scale with quantum computer or quantum logic gates.

In this QRL algorithm we use temporal difference (TD) prediction for the state value updating, and TD algorithm has been proved to converge for absorbing Markov chain when the stepsize is nonnegative and digressive (Sutton & Barto, 1998, Watkins & Dayan, 1992). Since QRL is a stochastic iterative algorithm and Bertsekas and Tsitsiklis have verified the convergence of stochastic iterative algorithms (Bertsekas & Tsitsiklis, 1996), we give the convergence result about the QRL algorithm as Theorem 1. The proof and related discussions can be found in (Dong et al., 2006a, Chen et al., 2006c, Dong et al., 2007b):

Theorem 1: For any Markov chain, quantum reinforcement learning algorithm converges at the optimal state value functionV(s)*with probability 1 under proper exploration policy when the following conditions hold (whereαkis stepsize and nonnegative):
limTk=1Tαk=,limTk=1Tαk2E42

From the procedure of QRL in Fig. 6, we can see that the learning process of QRL is carried out through parallel computation, which also provides a mechanism of parallel updating. Sutton and Barto (Sutton & Barto, 1998) have pointed out that for the basic RL algorithms the parallel updating does not affect such performances of RL as learning speed and convergence in general. But we find that the parallel updating will speed up the learning process for the RL algorithms with a hierarchical setting (Sutton et al., 1999, Barto & Mahadevan, 2003, Chen et al., 2005), because the parallel updating rules give more chance to the updating of the upper level learning process and this experience for the agent can work as the “sub-goals” intrinsically that will speed up the lower learning process.

Figure 6.

The algorithm of a standard QRL (Dong et al., 2007b)

4.5. Physical implementation

Now let’s simply consider the physical realization of QRL and detailed discussion can be found in (Dong et al., 2006b). In QRL algorithm, the three main operations occur in preparing the equally weighted superposition state for calculating the times of Grover iteration, initializing the quantum system for representing states or actions, and carrying out a certain times of Grover iteration for updating probability amplitude according to reward value. In fact, we can initialize the quantum system by equally weighted superposition for representing states or actions. So the main operations required are preparing the equally weighted superposition state and carrying out Grover iteration. These can be implemented using the Hadamard transform and the conditional phase shift operation, both of which are relatively easy in quantum computation.

Consider a quantum system described by n qubits, it has2npossible states. To prepare an equally weighted superposition state, initially let each qubit lie in the state|0, then we can perform the transformationHon each qubit independently in sequence and thus change the state of the system. The state transition matrix representing this operation will be of dimension2n×2nand it can be implemented by n shunt-wound Hadamard gates. This process can be represented into:

Hn|000n=12na=00011...1n|aE43

The other operation is the conditional phase shift operation which is an important element to carry out the Grover iteration. According to quantum information theory, this transformation may be efficiently implemented using phase gates on a quantum computer. The conditional phase shift operation does not change the probability of each state since the square of the absolute value of the amplitude in each state stays the same.

4.6. Simulated experiments

The presented QRL algorithm is also tested using two examples: Prisoner’s Diploma and the control of a five-qubit system.

1. Prisoner’s Diploma

The first example is derived from typical Prisoners’ Dilemma. In the Prisoners’ Dilemma, each of the two prisoners, prisoner I and prisoner II, must independently make the action selection to agree to give evidence against the other guy or to refuse to do so. The situation is as described in Table 1 with the entries giving the length of the prison sentence (years in prison) for each prisoner, in every possible situation. In this case, each of the prisoners is assumed to minimize his sentence. As we know, this play may lead to Nash equilibrium by giving the action selection (agree to give evidence, agree to give evidence) with the outcome of (3, 3) years in prison.

prisoner = 2 \* ROMAN II Prisoner = 1 \* ROMAN IAgree to give evidenceRefuse to give evidence
Agree(3, 3)(0, 5)
Refuse(5, 0)(1, 1)

Table 1.

The Prisoners’ Dilemma

Now, we assume that this Prisoners game can be played repeatedly. Each of them can choose to agree or refuse to give evidence against the other guy and the probabilities of the action selection (agree to give evidence, agree to give evidence) are initially equal. To find a better outcome, the two prisoners try to improve their action selection using learning. By applying the QRL method proposed in this chapter, we get the results as shown in Fig. 6 and Fig. 7 (Chen et al., 2006a; Chen et al., 2006c). From the results, it is obvious that the two prisoners get smarter when they try to cooperate indeliberately and both of them select the action of “Refuse to give evidence” after about 40 episodes of play. Then they steadily get the outcome of (1, 1) instead of (3, 3) (Nash equilibrium).

Figure 7.

The outcome (years in prison) of the Prisoners problem for each prisoner

Figure 8.

The whole outcome of the Prisoners problem (Sum of years in prison for both prisoners)

2. Control of a five-qubit system

The second axample is about the control of a five-qubit system (Dong et al., 2006c). With the development of quantum information technology, quantum control theory has drawn the attention of many scientists (Chen et al., 2005). The objective of quantum control is to determine how to drive quantum systems from an initial given quantum state to a pre-determined target quantum state with some given time. According to quantum mechanics, the state|ψ(t)of arbitary time t can be reached through an evolution on the initial state|ψ(0). It can be expressed as

|ψ(t)=U^|ψ(0)E44

whereU^is a unitary operator and satisfies:

U^U^+=U^+U^=IE45

whereU^+is the Hermitian conjugate operator ofU^. So the control problem of quantum state can be converted into finding appropriate unitary operatorU^

In this example, we consider the five-qubit system, it has 32 eigenstates. In practical quantum information technology, some state transitions can easily be completed through appropriate unitary transformations but the other ones are not easy to be accomplished. Assume we know its state transitions satisfy the following equations through some experiments:

|00001=U^00|00000|00010=U^01|00001
|00011=U^02|00010E46
;|00100=U^03|00011;|00101=U^04|00100;
|00111=U^11|00001E47
;|01000=U^12|00010;|01010=U^14|00100;
|01011=U^15|00101E48
;|01000=U^21|00111;|01011=U^24|01010;
|01101=U^31|00111E49
;|10000=U^34|01010;|10001=U^35|01011;
|01101=U^40|01100E50
;|10001=U^44|10000;|10010=U^50|01100;
|10110=U^54|10000E51
;|10111=U^55|10001;|10101=U^62|10100;
|10110=U^63|10101E52
;|10111=U^64|10110;|11000=U^70|10010;
|11100=U^74|10110E53
;|11101=U^75|10111;|11001=U^80|11001;
|11101=U^84|11100E54
|11111=U^91|11001E55

In the above equations,U^is reversible operator. For example, we can easily get

|00000=U^00-1|00001E56

Assume the other transitions are impossible except the above transitions and corresponding inverse transitions. If the initial state and the target state are|11100and|11111respectively, the following task is to find optimal control sequence through QRL.

Figure 9.

The grid representation for the quantum control problem of a five-qubit system

Therefor we first fill the eigenstates of five-qubit system in a grid room and they can be described as shown in Fig. 8. Every eigenstate is arranged in a corresponding grid and the hatched grid indicates that the corresponding state can not be attained. The two states with a common side are mutually reachable through one-step control and other states can not directly reach each other through one-step control. Now the task of the quantum learning system is to find an optimal control sequence which will let the five-qubit system transform from|11100to|11111. Using the QRL method proposed previously, we get the results as shown in Fig. 9. And more experimental results are shown in Fig. 10 to demonstrate its performance with different learning rates. From the results, it is obvious that the control system can robustly find the optimal control sequence for the five-qubit system through learning and the optimal control sequences are shown in Fig. 11. We can easily obtain two optimal control sequences from Fig. 11:

Sequence_1={U^74-1,U^54-1,U^34-1U^14-1,U^03-1U^02-1,U^12,U^21-1,U^31,U^40-1,U^50U^70U^80U^91}E57
Sequence_2={U^74-1,U^54-1,U^34-1,U^14-1,U^03-1,U^02-1,U^01-1,U^11,U^31U^40-1,U^50,U^70U^80U^91}E58

Figure 10.

The performance of QRL for optimal control sequence

Figure 11.

The performance of QRL with different learning rates

Figure 12.

The control paths for the control of a five-qubit system

5. Conclusion

According to the existing problems in RL area, such as low learning speed and tradeoff between exploration and exploitation, SIRL and QRL methods are introduced based on the theory of RL and quantum computation in this chapter, which follows the developing roadmap from the superposition-inspired methods to the RL methods in quantum systems. Just as simulated annealing algorithm comes from mimicking the physical annealing process, quantum characteristics also broaden our mind and provide alternative approaches to novel RL methods.

In this chapter, SIRL method emphasizes the exploration policy and uses a probabilistic action selection method that is inspired by the state superposition principle and collapse postulate. The experiments, which include a puzzle problem and a mobile robot navigation problem, demanstrate the effectiveness of SIRL algorithm and show that it is superior to basic TD algorithm withε-greedy policy. As for QRL, the state/action value is represented with quantum superposition state and the action selection is carried out by observing quantum state according to quantum collapse postulate, which means a QRL system is designed for the real quantum system although it can also be simulated on a traditional computer. The results of simulated experiments verified its feasibility and effectiveness with two examples: Prisoner’s Dilemma and the control of a five-qubit system. The contents presented in this chapter are mainly the basic ideas and methods related to the combination of RL theory and quantum computation. More theoretic research and applictions are to be investigated in the future.

© 2008 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike-3.0 License, which permits use, distribution and reproduction for non-commercial purposes, provided the original is properly cited and derivative works building on this content are distributed under the same license.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Chun-Lin Chen and Dao-Yi Dong (January 1st 2008). Superposition-Inspired Reinforcement Learning and Quantum Reinforcement Learning, Reinforcement Learning, Cornelius Weber, Mark Elshaw and Norbert Michael Mayer, IntechOpen, DOI: 10.5772/5275. Available from:

chapter statistics

3978total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

An Extension of Finite-state Markov Decision Process and an Application of Grammatical Inference

By Takeshi Shibata and Ryo Yoshinaka

Related Book

First chapter

Different Tools on Multi-Objective Optimization of a Hybrid Artificial Neural Network – Genetic Algorithm for Plasma Chemical Reactor Modelling

By Nor Aishah Saidina Amin and I. Istadi

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us