This chapter presents the basics of Reinforcement Learning (RL) and, based on that, introduces value-based RL as one of the two major categories of RL algorithms. For this goal, the basic RL concepts, including Markov Decision Process and essential RL terms, like environment, state, action, value, reward and policy, will be explained first. Next we will have an RL demonstration using simple virtual environments. Then, the Bellman equation, which casts the basis for the "learning" or improvement of an RL learning agent, will be discussed. This includes the Bellman equation's mathematical formulations, deduction, and use. After going through the basics, we will start the introduction to value-based RL algorithms with an overview of popular RL algorithms. Following that, typical value-based RL algorithms including two time-difference algorithms, i.e., Q-learning and Sarsa, and one episode-update algorithm, i.e., Monte Carlo, will be introduced. Details will be provided to cover both theories and guidelines for the implementation of these algorithms.
15.2. Basics of Reinforcement Learning
15.2.1. Basic Concepts
In a loose sense, any learning problem can be conceptualized as the interaction between a learning agent and the world whereby the agent performs learning and application of the learned knowledge. In supervised and unsupervised learning, all the data, no matter whether labeled or unlabeled, is ready and carries knowledge about the world. By contrast, data in reinforcement learning is not available before a learning process starts. Instead, the agent obtains the data as the learning agent interacts with the environment. The data can be understood as "labeled" because we need to figure out what to do (described as "action" in RL; can be viewed as labels) under what conditions (described as "state" in reinforcement learning; can be viewed as data without labels). The model will be continuously improved as more data is obtained in the training process. The model's performance also needs to be evaluated with metrics in reinforcement learning. Such metrics are so-called reward functions that tell the goodness of specific actions for certain states.
Based on the above introduction, we can generally conceptualize reinforcement learning as illustrated in Fig. 15.1. The world outside of a learning agent is modeled as an environment. In this flappy bird game, the agent is the bird or the player controlling the agent, and the environment is the space consisting of the pipe obstacles. In order to describe the learning process, we need to know the current status of the learning agent, i.e., state, and the action the learning agent will take to interact with the environment. In this example, the state is the location of the bird, while the action is to fly or not. The action may bring the agent to a different (new) state and get reward from the environment that leads to beneficial results, e.g., survive longer in the game. The goal of any reinforcement learning process is to maximize the rewards so that the learning agent can gain a better performance. The Markov Decision Process (MDP) to be introduced will present a more strict model for conceptualizing such sequential decision processes [153, 154].
15.2.2. Markov Decision Process
The studies of MDP stemmed from the realm of optimal control. In 1957, a U.S. researcher, Richard Bellman [155] first proposed the discrete time MDP via an optimal control model. Between 1960 and 1962, Howard [156] and Blackwell [157] proposed a dynamic programming algorithm for solving MDP problems. The MDP and its solution methods
Figure 15.1: Example of environment and its elements in reinforcement learning
were later adopted for applications in various areas, such as autonomous control, suggestion systems, and reinforcement learning. In addition to the above essential components like state, action, and reward, MDP is characterized by the Markov property: the state at the current time is only related to the state and action at the previous time and independent of the state and action at other time points. This can be described using the following probability equation:
This equation means that the consideration of earlier states does not make a difference in MDP.
Sequential decision problems based on MDP can be grouped into two categories: model-based and model-free. Dynamic programming was proposed for model-based problems. That is, the influence of the learning agent's action on the environment - the probability P_(ss^('))^(a)P_{s s^{\prime}}^{a} and reward r_(ss^('))^(a)r_{s s^{\prime}}^{a} of entering a new state, s^(')s^{\prime}, after taking an action, aa, in the current state, ss - is known. By contrast, reinforcement learning was proposed for model-free problems, but it can also be used to solve model-based problems. More information about the classification of RL algorithms, including model-based and modelfree categories in a broad sense, will be presented before we start working on the first major category of RL algorithms, i.e., value-based RL algorithms, in this chapter.
The Bellman equation is viewed as the core of dynamic programming. Based on it, a solution to MDP problems can be derived. Because both dynamic programming and reinforcement learning are intended for sequential decision problems, they share many concepts in common including the Bellman equation. Due to this reason, many people also perceive the Bellman equation as the core of reinforcement learning. However, reinforcement learning usually includes additional materials in addition to the sole use of the Bellman equation.
15.2.3. Policy Function, State Function, State-Action Function, and Reward Function
A policy determines how an agent selects an action in a state of the environment. This policy can be deterministic, that is, one action will be selected in a specific state. Or, the policy can also be stochastic, that is, in a specific state, the agent can select an action from different candidate actions (discrete or continuous) with different probabilities. In RL, it can be more specifically referred to as the learning policy, while in applications like control tasks, it may be called the control policy. Every policy can be formulated using a policy function:
{:(15.2)pi(s):S|->A:}\begin{equation*}
\pi(s): S \mapsto A \tag{15.2}
\end{equation*}
With the above equation, when a state, ss, is entered as the input, the policy function will give out an action, aa, as the output.
Value functions, in a broad sense, contain both VV and QQ. But in a narrow sense, we call VV a value function and QQ an action-value function. Both VV and QQ are widely used in RL algorithms. These two functions are closely related, and they can be converted to each other. Thus, in some RL algorithms, such as Q-learning and Sarsa, you may only see one of them, such as QQ. These two functions can be confusing. Some aspects of these two types of functions are clarified here.
First, both of the two functions are usually associated with a specific learning policy. For example, we write them as V^(pi)(s)V^{\pi}(s) and Q^(pi)(s,a)Q^{\pi}(s, a), where the superscript pi\pi marks the policy. However, in algorithms such as Q-learning and Sarsa,
the policy is continuously improved as more data is processed by the agent to improve the policy. Thus, pi\pi may also be omitted to avoid confusion.
Second, from the symbol, we can see that, V(s)V(s) is the value of a state (without mentioning any specific action), while Q(s,a)Q(s, a) is the value associated with an action in a state, in which both an action and a state are needed. These two types of functions can be defined as follows. V^(pi)(s)V^{\pi}(s) is the expected value of rewards following policy pi\pi forever when the agent starts the learning process from the state s:V^(pi)(s)=E(R)s: V^{\pi}(s)=\mathbb{E}(R). Mathematically, this is formulated as
where RR is the long-term reward. RR at the current step tt can be obtained by summing up the rewards at different steps as R_(t)=sum_(k=0)^(oo)gamma^(k)r_(t+k+1)R_{t}=\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1}. This equation can also be written as
By contrast, Q_(pi)(s,a)Q_{\pi}(s, a) is the expected value of rewards yielded by first taking action aa in state ss and then following the policy pi\pi forever. Therefore, QQ can be related to rewards as
{:(15.5)Q^(pi)(s","pi)=E(R∣s","a","pi):}\begin{equation*}
Q^{\pi}(s, \pi)=\mathbb{E}(R \mid s, a, \pi) \tag{15.5}
\end{equation*}
Based on the definition, the two types of functions can be converted to each other using the following equations.
where pi(a∣s)\pi(a \mid s) is the probability of selecting action aa if we follow policy pi\pi (policy can be determinate but here a more general definition with indeterminate policy is adopted), P_(ss^('))^(a)P_{s s^{\prime}}^{a} is the probability of moving from state ss to s^(')s^{\prime} if we take action a,r_(ss^('))^(a)a, r_{s s^{\prime}}^{a} is the reward gained as we move from ss to s^(')s^{\prime}. In Q-learning and Sarsa, random factors were added via epsilon\epsilon-greedy, which corresponds to P_(ss^('))^(a)P_{s s^{\prime}}^{a}. In the literature, we can also see r_(s)^(a)=sum_(s^('))P_(ss^('))^(a)r_(ss^('))^(a)r_{s}^{a}=\sum_{s^{\prime}} P_{s s^{\prime}}^{a} r_{s s^{\prime}}^{a}.
It is also common to use * to represent the optimal policy, which leads to the highest long-term reward. Accordingly, V^(**)(s)V^{*}(s) is the maximum possible value of V^(pi)(s)V^{\pi}(s) :
The theory of MDP states that if pi^(**)\pi^{*} is an optimal policy, we will act optimally. Therefore, we will take the optimal action by choosing the action from Q^(**)(s,*)Q^{*}(s, \cdot), and this generates the optimal V^(**)(s)V^{*}(s) :
{:(15.8)V^(**)(s)=max_(a)Q^(**)(s","a):}\begin{equation*}
V^{*}(s)=\max _{a} Q^{*}(s, a) \tag{15.8}
\end{equation*}
It is worthwhile to point out that, in policy-based algorithms, we usually evaluate the policy, i.e., pi(a∣s)\pi(a \mid s), which can be viewed as a probability distribution of actions. By contrast, in value-based algorithms, we usually use and improve the optimal functions V^(**)V^{*} or/and Q^(**)Q^{*}, which can be viewed as VV or/and QQ values that can best help us identify the optimal action (e.g., action aa with the highest Q(s,a)Q(s, a) value in ss ).
15.2.4. Implementation of RL Environment
In this section, brief information is provided to show how to work with an RL environment. Two different ways will be illustrated. The first way involves the use of environments created by RL packages such as OpenAI Gym [158]. OpenAI Gym provides functions for users to easily employ a variety of RL environments. These environments can be used to test RL algorithms that are developed by the users, so that the user can focus on the RL algorithms instead of wasting time to find, implement, or calibrate RL environments. The second refers to the development of RL environments from scratch.
Implementation with OpenAI Gym
We use an environment called "Taxi-v3" from OpenAI Gym as an example. As illustrated in Fig. 15.2, the taxi needs to start at a random location, pick up and drop off a passenger at two locations randomly selected from the four special locations marked with four colors. There are six actions: 0 : move south, 1 : move north, 2 : move east, 3: move west, 4 : pickup passenger, and 5: drop off passenger. The map has 25 cells ( 5 rows by 5 columns). Therefore, there are 500 states: 5 rows **5* 5 columns **5* 5 passenger positions (at four special locations + in taxi) **4* 4 destinations =500=500 states.
Figure 15.2: Drawing of Taxi-v3 environment in Open Gym
The following code shows the use and check of the environment. The first step to use this environment is to import the package and initialize the environment using "gym.make('Taxi-v3')". We can also check or/and use the size of the action and state spaces to get a better understanding of the environment. Such information will also likely be needed in later use of the environment for RL.
import numpy as np
import gymnasium as gym # Old versions use "import gym"
# Initialization
env = gym.make("Taxi-v3", render_mode="human") # Call the "Taxi-v3" environment from gym with the
name "env"
action_size = env.action_space.n # Obtain the size of the action space: how many actions. There are
six here
state_size = env.observation_space.n # Obtain the size of the state space: 5 rows * 5 columns * 5
passenger positions * 4 destinations =500 states
A key step in the use of such RL environment is to make one step in an episode. In this step, a new state will be obtained. Also, a reward value will be obtained after taking the action. Another variable is the signal to indicate whether the episode ends. In OpenAI Gym, this signal is represented using a variable called "done". This can be seen in the following code.
# Update state
state_new, reward, done, _, _ = env.step(action)
When an episode is finished, i.e., some conditions for ending the episode are met, we usually need to stop the RL iterations. This can be done as follows.
# Stop an episode when the environment tells an episode ends
if done == 1:
print('This is the #%i training episode' % n)
break
After each episode or before we start testing, we will need to reset the environment. In testing, we also need to use loops by iteratively calling the "env.step()" function to add more steps within each episode. In addition, an "env.render()" function is provided in OpenAI Gym to illustrate the results. This is shown in the following code.
# Testing
state = env.reset()[0]
while True:
# Choose an action based on the Q table only
action = np.argmax(Table[state]) # Choose an action based on the Q table
state, reward, done, _, _ = env.step(action)
env.render() # Green is passenger; Red is destination
if done == 1:
break
Implementation from Scratch
In this part, the construction of a very simple environment that can be used in a way similar to OpenAI Gym environments is illustrated in the following code. Because the code for building the environment serves as Python functions that can be imported by other Python code, we used object-oriented programming to develop the code. The code includes a few key parts similar to OpenAI Gym: initialize variables and functions, develop functions to reset the environment, develop a function to make one step in the episode (including assigning rewards and stopping the episode), and develop a render function to illustrate the state when using the episode.
import numpy as np
class treasure1D:
def ___init__(self,N):
self.n_cell = N # The greater this number, the higher n_episode is needed
self.Reward = np.zeros(self.n_cell);
self.Reward[-1]=1.0 # n_cell cells, only the rightmost has reward (end of game)
self.States = range(self.n_cell)
self.state = np.random.choice(self.States)
self.reward = 0
self.done = False
self.observation_size = 1 # Number of elements in observation (there is only one in this env
: state/position)
def reset(self):
self.state = np.random.choice(self.States)
self.reward = 0
self.done = False
return self.state
def step(self,action):
# Update state
reward = 0
if action == 'left' or action == 0:
if self.state == self.States[0]: # Leftmost
state_new = self.state # Does not move
self.done = True
self.reward = -10
else:
state_new = self.state - 1 # Obtain new state s^prime
else:
if self.state == self.States[-1]: # rightmost
state_new = self.state # Does not move
self.done = True
self.reward = 10
else:
state_new = self.state + 1 # Obtain new state s^prime
self.state = state_new
return self.state, self.reward, self.done, []
def render(self):
print ("The state is ", self.state, "The reward is ",self.reward)
This environment simulates a very simple 1D treasure hunt game. In each episode, an agent will be placed at a random cell of a 1D map consisting of multiple cells. The agent needs to find the treasure in the rightmost cell. Rewards/penalties are only assigned to the cells on the two ends of the map. The agent cannot move out of the map from the left. Thus, it
will stay in the leftmost cell when it tries to move left from there, and a reward of -10 (penalty of 10 ) is applied when that happens. An episode ends when the agent reaches the rightmost cell, i.e., finding the treasure, and a reward of 10 is made.
15.3. Bellman Equation
The Bellman equation lays out a relationship between the state value function or the action-state value function in the current state and that in the following state. Therefore, this equation appears in a recursive format and can be used iteratively to obtain VV or/and QQ in an episode. In this subsection, we will first give out the Bellman equation in different forms. Then, details will be offered to show how the Bellman equation in typical forms can be derived to understand the essence of learning in RL.
15.3.1. Formulations of Bellman Equation
The Bellman equation can be formulated with the state value function and the action-state value function. The Bellman equation formulated with the state value function describes the values function in the current state ss and the value function in the following state s^(')s^{\prime} :
Likewise, the Bellman equation formulated with the action-state value function describes the action-state value function in the current state ss and that in the following state s^(')s^{\prime}
Based on the above equations and the relationship in Section 15.2.3, we can obtain the following Bellman equation for the optimal state value function and action-state value function:
Next, we need to deal with the two terms in the above equation based on the definition of the expectation of rewards in a way similar to what we did for the VV Bellman equation:
It is noted that the above two equations are different from those for the VV function because the action aa is determined in the definition of QQ. As a result, the sum weighted by pi(a∣s)\pi(a \mid s) is not needed anymore.
15.3.3. Use of Bellman Equation in Reinforcement Learning
The use of the Bellman equation in reinforcement learning is slightly different from that in dynamic programming. In dynamic programming, the Bellman equation is implemented in iterations to seek solutions to MDP problems. In reinforcement learning, two significant differences are the use of the optimal value functions and the learning rate.
The first difference is marked by the use of the greedy method in the search for a better policy. Instead of always utilizing the best action in the current policy (exploitation purpose), non-optimal actions that may lead to better policies will also be taken at certain probabilities. The search for the optimal policy can be performed via the improvements in the action-state value function or/and state value function or the whole policy represented by a distribution pi(s,a)\pi(s, a). The former is usually adopted in value-based algorithms, while the latter is used in policy-based algorithms.
In value-based RL algorithms, we usually use epsilon\epsilon-greedy method to reach a balance between exploration and exploitation. That is, in most conditions, i.e., at a probability of 1-epsilon1-\epsilon, we use the greedy policy: adopting an action, aa, with the optimal action-value function Q^(**)(s,a)Q^{*}(s, a), and select a random action in other conditions, i.e., at the probability of epsilon\epsilon.
Therefore, in the former case (1-epsilon)(1-\epsilon), we can use the relationship between the optimal state value function and the optimal action-state value function:
{:(15.20)V^(**)(s)=max_(a)Q^(**)(s","a):}\begin{equation*}
V^{*}(s)=\max _{a} Q^{*}(s, a) \tag{15.20}
\end{equation*}
Usually, in such value-based RL algorithms, such as QQ learning [159], the transfer between states is fixed. That is, we do not need to consider P_(ss^('))^(a)P_{s s^{\prime}}^{a} anymore. With the above two considerations, the Bellman equation for the optimal Q function, i.e., Eq. 15.19, becomes
"Greedy" is primarily reflected via the max function.
The second difference resides in the use of a learning rate. A learning rate is used to integrate both the old value from the history (e.g., existing Q table) and the new value obtained with the Bellman equation when making updates:
where Q^(**)(s,a)Q^{*}(s, a) on the left-hand side of the equation is the new QQ function in state ss when taking action a;Q^(**)(s,a)a ; Q^{*}(s, a) on the right-hand side of the equation is the Q^(**)(s,a)Q^{*}(s, a) from the history, e.g., the previous episode, and the second term on the right-hand side of the equation is the new Q^(**)(s,a)Q^{*}(s, a) obtained purely with the Bellman equation. The learning rate alpha\alpha gives out the weights to sum up these two values so that the update will not experience abrupt changes. That is, if alpha=1\alpha=1, then the update will be completed with the new value (from the Bellman equation) only. As a result, the update process may not be stable because the new QQ is irrelevant to the historical ones. On the contrary, if alpha=0\alpha=0, the new value (in the current episode) will always be equal to the old value (from the previous episode), and consequently, the learning will stop.
15.4. Value-Based RL
15.4.1. Overview of RL Algorithms
The classification of machine learning algorithms can be complicated and is still evolving quickly due to the fast development of RL. Fig. 15.3 presents a classification that includes the most classic and popular algorithms in the state of the practice. Currently, the RL based on MDP is predominant. Both model-based and model-free RL within this category gained success. However, more research and breakthroughs have been made in the time-difference model-free RL, which can be further categorized into value-based and policy-based algorithms. In more recent studies, both value-based and policy-based algorithms have been integrating deep neural networks to enable impactful deep reinforcement learning [160, 161].
The remaining of this chapter will use value-based RL as an entry for introducing reinforcement learning. We will show how to construct the classic Q learning (or Q-learning)[159] and Sarsa [162], from theories, procedure, to pseudocode. In the next chapter, we will focus on policy-based RL algorithms. A classic gradient-based algorithm, policy gradient, will be presented in detail. Based on that, more information will be provided for other gradient-based policybased RL algorithms.
15.4.2. Q Learning and Sarsa
The essence of Q learning is to use the average value of Q(s,a)Q(s, a) to estimate Q(s,a)Q(s, a) : a strategy called time-difference. A much different but easier to understand strategy is to collect all (or a large amount of) the data, e.g., one episode, and then calculate the average. This is the strategy adopted by episode-update methods like Monte Carlo. Therefore, distinct from episode update methods, time-difference methods like Q-learning update the average value, e.g., Q(s,a)Q(s, a), immediately after a new data point (or sample, e.g., s,a,rs, a, r ) is collected instead of after an episode is finished. The math underlying this time-difference can be derived with the following equation.
In the above equation, the average value at the current step u_(K)u_{K} is obtained by adding (1)/(K)(x_(K)-u_(K-1))\frac{1}{K}\left(x_{K}-u_{K-1}\right) to the average of the previous step u_(K-1)*(1)/(K)u_{K-1} \cdot \frac{1}{K} is the learning rate for a constant number of steps. Then, we can use alpha\alpha, a generalized learning rate, to reformulate the above equation as
Thus, this equation provides one way of understanding the world, i.e., characterized by the average or expected value, by continuously taking more measurements and using such measurements to update the average or approach the expected value.
In Q learning, we want to select the action in the current state that can lead to the highest cumulative rewards. Accordingly, we define Q^(pi)(s,a)Q^{\pi}(s, a) as the expected value of first taking action aa in state ss and then following the policy pi\pi forever. In Q learning, we are improving our understanding of the environment and, consequently, the policy by updating the Q(s,a)Q(s, a) values. Using the above equation for updating the expected value, Q(s,a)Q(s, a) can be updated as follows:
where rr is the reward gained as we move from state ss to the next state s^(')s^{\prime} after taking action aa, and max_(a^('))Q(s^('),a^('))\max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right) is the maximum of the QQ values of all the actions in the state s^(').gammamax_(a^('))Q(s^('),a^('))s^{\prime} . \gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right) represents the experience from previous
learning. For example, max_(a^('))Q(s^('),a^('))\max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right) can inform the agent in the current state if the agent previously (in an early learning process or episode) gained a high reward in state s^(')s^{\prime} after taking action a^(')a^{\prime}. As can be seen, this equation is the same as the Q update equation (Fig. 15.22) using the Bellman equation, disregarding the difference in symbols.
Q learning is off-policy learning, whereby the agent can learn from the data generated beforehand instead of learning as the agent generates data in an environment. An RL algorithm that is very close to Q learning but with a distinct onpolicy nature is Sarsa. In Sarsa, the learning agent must participate in the learning process as it improves the policy. This is achieved by replacing max_(a^('))Q(s^('),a^('))\max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right) with Q(s^('),a^('))Q\left(s^{\prime}, a^{\prime}\right). Thus, instead of selecting the action leading to the maximum reward in the next state ( s^(')s^{\prime} part of the Q table is from history only (off the policy) at this moment), the agent in Sarsa first uses the policy derived from Q\mathbf{Q} (still on the same policy, with epsilon\epsilon-greedy) to get Q(s^('),a^('))Q\left(s^{\prime}, a^{\prime}\right) (next state) and then use this Q(s^('),a^('))Q\left(s^{\prime}, a^{\prime}\right) to update the Q(s,a)Q(s, a) in the current state:
The detailed procedures for implementing Q learning and Sarsa are exemplified using the following pseudo-code.
Q learning:
Initialize Q(s,a)Q(s, a) arbitrarily
Repeat for each episode:
Initialize ss (e.g., choose a ss randomly)
Repeat for each step of the episode:
Select aa from ss using a policy derived from Q (e.g., epsilon\epsilon-greedy ^(1){ }^{1} )
Take action aa, and obtain rr and s^(')s^{\prime} based on the environment
Update Q:Q(s,a)larr(1-alpha)Q(s,a)+alpha[r+gammamax_(a^('))Q(s^('),a^('))]Q: Q(s, a) \leftarrow(1-\alpha) Q(s, a)+\alpha\left[r+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right)\right]
Update s:s larrs^(')s: s \leftarrow s^{\prime}
Until ss is terminal
Sarsa:
Initialize Q(s,a)Q(s, a) arbitrarily
Repeat for each episode:
Initialize ss (e.g., choose a ss randomly)
Select aa from ss using a policy derived from Q (e.g., epsilon\epsilon-greedy)
Repeat for each step of the episode:
Take action aa, and obtain rr and s^(')s^{\prime} based on the environment
Select a^(')a^{\prime} from s^(')s^{\prime} using a policy derived from Q (e.g., epsilon\epsilon-greedy
Update Q:Q(s,a)larr(1-alpha)Q(s,a)+alpha[r+gamma Q(s^('),a^('))]Q: Q(s, a) \leftarrow(1-\alpha) Q(s, a)+\alpha\left[r+\gamma Q\left(s^{\prime}, a^{\prime}\right)\right]
Update s:s larrs^(')s: s \leftarrow s^{\prime}
Until ss is terminal
Example code for implementing Q learning to address the Taxi-v3 problem is given in the following.
import numpy as np
import pandas as pd
import gym
# Initialization
env = gym.make("Taxi-v3") # Call the "Taxi-v3" environment from gym with the name "env"
action_size = env.action_space.n # Obtain the size of the action space: how many actions. There are
six here
state_size = env.observation_space.n # Obtain the size of the state space: 5 rows * 5 columns * 5
passenger positions * 4 destinations =500 states
Table = np.zeros((state_size, action_size)) # Initialize the Q table
# Hyperparameter
epsilon = 0.9 # Parameter for epsilon-greedy
alpha = 0.1 # Learning rate
gamma =0.8 # Decay of rewards
# Training
n_episode = 10000 # Number of episodes for training
for n in range(n_episode):
state = env.reset() # Initialize the environment for each episode
while True:
# Choose an action based on the Q table with epsilon greedy
action_Q = np.argmax(Table[state]) # Choose an action based on the Q table
action_greedy = np.random.choice(Table[state].size) # Choose an action randomly for use in
the epsilon-greedy method
action = np.random.choice([action_Q,action_greedy],size=1,p=[epsilon,1-epsilon])[0]
# Update state
state_new, reward, done, _ = env.step(action)
# Update the table
Table[state,action] = (1-alpha)*Table[state,action] + alpha*(reward+gamma*max(Table[
state_new]))
# Prepare for the next step
state = state_new
# Stop an episode when the environment tells an episode ends
if done == 1:
print('This is the %i the episode' % n)
break
# Testing
state = env.reset()
while True:
# Choose an action based on the Q table only
action = np.argmax(Table[state]) # Choose action based on Q table
state, reward, done, _ = env.step(action)
env.render() # Green is passenger; Red is destination
if done == 1:
break
15.4.3. Monte Carlo Method
In the current practices of reinforcement learning, the use of episodic update methods represented by the Monte Carlo method is less popular than step-update method (time-difference) methods. Compared to time-difference methods such as Q learning and Sarsa, the Monte Carlo method is also value-based: the learning is carried out by improving the value functions. However, instead of updating the value functions step by step in an episode, the Monte Carlo method first finishes all the steps in the episode and then updates the value. Accordingly, for each episode, a series of states will be generated randomly: s_(1),a_(1),r_(2),s_(2),a_(2),r_(3),cdots,s_(t),a_(t),r_(t+1),cdots,s_(T),a_(T)s_{1}, a_{1}, r_{2}, s_{2}, a_{2}, r_{3}, \cdots, s_{t}, a_{t}, r_{t+1}, \cdots, s_{T}, a_{T}.
Then let us recall the definition of the value function in the MDP. However, a minor difference is made so that the equation can be used to calculate the value of every state in a series of states.
Therefore, for every step in an episode, we will have one state ss (and choose one action aa ), which corresponds to a G_(t)G_{t} value in the above function. Using the average value update equation, we can update the value function of every state ss that appears in a series (episode):
where NN is the number of times that this state appears in the whole learning process (e.g., all the episodes that have been tested). It is possible that a state can appear multiple times in an episode (series). To deal with such a situation, we can choose to consider only the reward gained (G_(t))\left(G_{t}\right) in the first appearance of this state (called first visit) or use the rewards from every appearance of the state (called every visit). The second method usually requires more computational effort but may get better results when the number of series is small.
In fact, we usually update the action-value function ( Q table). This update can be performed in a similar way:
To use the equation, we need to record the NN number for every state for updating the state value and for every action in every state for updating the action-state value. This will consume a lot of memory. A convenient alternative is to replace (1)/(N)\frac{1}{N} with a learning rate alpha\alpha.
^(1){ }^{1} Select aa that has the highest QQ at the ss with probability of epsilon\epsilon and select a random action with a probability of 1-epsilon1-\epsilon
