Basic Concepts#

Law of Total Probability#

Discrete Random Variables#

• Partition Conditions:

  • Events $B_1,B_2,\cdots,B_n$ form a partition of sample space $\Omega$.

  • $B_i\cap B_j = \varnothing$ for $i\neq j$ ($i,j = 1,2,\cdots,n$) (pair - wise mutual exclusivity).

  • $\bigcup_{i = 1}^{n}B_i=\Omega$ (union covers the whole sample space).

• Formula: For any event $A\subseteq\Omega$,

$P(A)=\sum_{i = 1}^{n}P(B_i)P(A|B_i),~E(A)=\sum_{i = 1}^{n}P(B_i)E(A|B_i)$

Continuous Random Variables#

• Given Conditions:

  • $X$ is a continuous random variable with probability density function $f(x)$.

  • $Y$ is another random variable with values $y$.

  • Conditional probability density function of $X$ given $Y = y$ is $f_{X|Y}(x|y)$.

  • Marginal probability density function of $Y$ is $f_Y(y)$.

• Formula:

$f_X(x)=\int_{-\infty}^{\infty}f_Y(y)\cdot f_{X|Y}(x|y)dy,~E(X)=\int_{-\infty}^{\infty}f_Y(y)\cdot E(X|Y = y)dy$

State and State space#

$s$ can include multi - dimensional coordinates, such as velocity, level, temperature and various other states.

• State: The status of the agent with respect to the environment.

• State space: The set of all states, denoted as $\mathcal{S} = \{s_i\}_{i = 1}^9$.

Action and Action space#

• Action：For each state, there are five possible actions: $a_1,\cdots,a_5$

  • $a_1$：move upwards, $a_2$：move rightwards;

  • $a_3$：move downwards, $a_4$：move leftwards;

  • $a_5$：stay unchanged;

• Action space: the set of all possible actions of a state, $\mathcal{A}(s_i)=\{a_i\}_{i = 1}^5$

State Transition Probability#

State transition defines the interaction with the environment.

• State Transition: When an agent takes an action and moves from one state to another, this process is called state transition.

• If action $a_2$ (move rightwards) is chosen at state $s_1$, the next state is $s_2$, denoted as $s_1\xrightarrow{a_2}s_2.$

• If action $a_1$ (move upwards) is chosen at state $s_1$, the next state remains $s_1$, denoted as $s_1\xrightarrow{a_1}s_1.$

• State Transition Probability: Use probability to describe state transition.

  • $p(s_2|s_1, a_2) = 1$, which means the probability of transitioning from state $s_1$ to state $s_2$ when action $a_2$ is taken is $1$.

  • $p(s_i|s_1, a_2) = 0$ for all $i\neq2$, that is, the probability of transitioning from state $s_1$ to any state other than $s_2$ when taking action $a_2$ is $0$.

• This is a deterministic case. State transition can also be stochastic, for example, $p(s_1|s_1, a_2) = 0.5,p(s_5|s_1, a_2) = 0.5$.

Policy#

• Definition：the agent which actions to perform in a given state.

• Intuitive Representation：Arrows in a grid - like illustration can be used to demonstrate a policy. For example, the arrows in the provided grid show the recommended actions from different states.

• Mathematical Representation：Use conditional probability (Take state $s_1$ as an example)

Deterministic policy	Stochastic policy

Left: $\pi(a_1|s_1) = 0,~~\pi(a_2|s_1) = 1,~~\pi(a_3|s_1) = 0,~~\pi(a_4|s_1) = 0,~~\pi(a_5|s_1) = 0.$

Right: $\pi(a_1|s_1) = 0,~~\pi(a_2|s_1) = 0.5,~~\pi(a_3|s_1) = 0.5,~~\pi(a_4|s_1) = 0,~~\pi(a_5|s_1) = 0$

Reward#

• Definition: It is a real number obtained after an agent takes an action.

  • A positive reward encourages taking such actions, while a negative reward punishes taking them.

  • Zero reward implies no punishment. In some cases, a positive value can even represent punishment.

• Representation Method：Use conditional probability for mathematical description.

• Example at State $s_1$: $p(r = - 1|s_1,a_1)=1$ and $p(r\neq - 1|s_1,a_1)=0$.

• Role of Reward: Reward can be regarded as a human - machine interface. It is used to guide the agent to behave as expected.

  • Grid - world Example Rewards

    • If the agent tries to exit the boundary, $r_{bound}=-1$.

    • If the agent attempts to enter a forbidden cell, $r_{forbid} = - 1$.

    • When the agent reaches the target cell, $r_{target}=+1$.

    • Otherwise, the agent gets a reward of $r = 0$.

    

Trajectory and Return#

• Trajectory: A trajectory is a chain of state - action - reward. It shows the path an agent takes, like a sequence of states it visits, actions it takes, and rewards it gets.

• Return: Also called total rewards or cumulative rewards. It’s the sum of all the rewards collected along a trajectory.

  

• Example Left：starting from $s_1$,

  • The trajectory: $s_1\xrightarrow[a_2]{r = 0}s_2\xrightarrow[a_3]{r = 0}s_5\xrightarrow[a_3]{r = 0}s_8\xrightarrow[a_2]{r = 1}s_9.$

  • Return = $0 + 0+0 + 1=1$.

• Example Right：starting from $s_1$,

  • The trajectory: $s_1\xrightarrow[a_3]{r = 0}s_4\xrightarrow[a_3]{r=-1}s_7\xrightarrow[a_2]{r = 0}s_8\xrightarrow[a_2]{r = 1}s_9.$

  • Return = $0-1 + 0+1 = 0$.

Infinite Trajectories and Divergence Problem#

• Infinite Trajectory：Suppose a policy generates an infinitely long trajectory like

If we calculate the return as the direct sum of rewards $0 + 0+0 + 1+1 + 1+\cdots=\infty$

This makes it impossible to properly evaluate the policy using this simple sum.

To deal with infinitely long trajectories, we introduce the concept of discounted return.

$\text{Discounted return} = 0+\gamma0+\gamma^{2}0+\gamma^{3}1+\gamma^{4}1+\gamma^{5}1+\cdots=\gamma^{3}\frac{1}{1 - \gamma},$

where $\gamma\in(0, 1)$ is the discount rate.

• If $\gamma$ is close to $0$, the value of the discounted return is mainly determined by the rewards received in the near future.
• If $\gamma$ is close to $1$, the value of the discounted return is mainly determined by the rewards received in the far future.

Markov decision process#

Key elements of MDP:

• Sets:

  • State: the set of states $\mathcal{S}$

  • Action: the set of actions $\mathcal{A}(s)$ is associated for state $s\in\mathcal{S}$.

  • Reward: the set of rewards $\mathcal{R}(s, a)$.

• Probability distribution:

  • State transition probability: at state $s$, taking action $a$, the probability to transit to state $s'$ is $p(s'|s, a)$

  • Reward probability: at state $s$, taking action $a$, the probability to get reward $r$ is $p(r|s, a)$

• Policy: at state $s$, the probability to choose action $a$ is $\pi(a|s)$

• Markov property: memoryless property

  • $p(s_{t + 1}|a_{t + 1}, s_t, \dots, a_1, s_0)=p(s_{t + 1}|a_{t + 1}, s_t)$

  • $p(r_{t + 1}|a_{t + 1}, s_t, \dots, a_1, s_0)=p(r_{t + 1}|a_{t + 1}, s_t)$

All the concepts introduced in this lecture can be put in the framework in MDP.

State Values and Bellman Equation#

Why are returns important?#

In fact, returns play a fundamental role in reinforcement learning since they can evaluate whether a policy is good or not.

• Following the first policy, the trajectory is $s_1\rightarrow s_3\rightarrow s_4\rightarrow s_4\cdots$. The corresponding discounted return is

• Following the second policy, the trajectory is $s_1\rightarrow s_2\rightarrow s_4\rightarrow s_4\cdots$. The discounted return is

• Following the third policy, two trajectories can possibly be obtained. One is $s_1\rightarrow s_3\rightarrow s_4\rightarrow s_4\cdots$, and the other is $s_1\rightarrow s_2\rightarrow s_4\rightarrow s_4\cdots$. The probability of either of the two trajectories is $0.5$. Then, the average return that can be obtained starting from $s_1$ is

By comparing the returns of the three policies, we notice that

$$\text{return}_1>\text{return}_3>\text{return}_2.$$

How to calculate returns?#

A return equals the discounted sum of all the rewards collected along a Let $v_i$ denote the return obtained by starting from $s_i$ for $i = 1,2,3,4$.

By definition#

Let $v_i$ denote the return obtained starting from $s_i$ ($i = 1,2,3,4$)

By substitution#

Write in the following matrix - vector form:

which can be rewritten as $\mathbf{v}=\mathbf{r}+\gamma\mathbf{Pv}.$ We can solve for $v$ as $\mathbf{v}=(I - \gamma \mathbf{P})^{-1}\mathbf{r}.$

State value#

Single step Process#

• Elements

  • $t,t + 1$: Discrete time instances.

  • $S_t$: State at time $t$.

  • $A_t$: The action taken at state $S_t$.

  • $R_{t + 1}$: The reward obtained after taking $A_t$.

  • $S_{t + 1}$: The state transitioned to after taking $A_t$.

  • Note that $S_t$, $A_t$, $R_{t + 1}$ are all random variables.

• Probability Distributions

  • $S_t\rightarrow A_t$ is governed by $\pi(A_t = a|S_t = s)$.

  • $S_t,A_t\rightarrow R_{t + 1}$ is governed by $p(R_{t + 1}=r|S_t = s,A_t = a)$.

  • $S_t,A_t\rightarrow S_{t + 1}$ is governed by $p(S_{t + 1}=s'|S_t = s,A_t = a)$.

  • Assume we know the model (i.e., the probability distributions).

Multi step Trajectory#

• Discounted Return ($G_t$)

  • Formula: $G_t=R_{t + 1}+\gamma R_{t + 2}+\gamma^{2}R_{t + 3}+\cdots$, where $\gamma\in[0,1)$ is the discount rate.

  • $G_t$ is a random variable since $R_{t + 1}$, $R_{t + 2},\cdots$ are random variables.

State value Function#

• Definition

  • $v_{\pi}(s)=\mathbb{E}[G_t|S_t = s]$, which is the expectation (expected value or mean) of $G_t$.

• Remarks

  • It is a function of $s$, a conditional expectation given that the state starts from $s$.

  • It depends on the policy $\pi$. Different policies may result in different state values.

  • Represents the “value” of a state. A larger state value indicates a better policy as it implies greater cumulative rewards can be obtained.

• Relationship between Return and State Value

  • The state value is the mean of all possible returns starting from a state. If $\pi(a|s)$, $p(r|s,a)$, $p(s'|s,a)$ are deterministic, then the state value is the same as the return.

• Example

Bellman equation#

Consider a random trajectory: $S_t\xrightarrow{A_t}R_{t + 1},S_{t + 1}\xrightarrow{A_{t + 1}}R_{t + 2},S_{t + 2}\xrightarrow{A_{t + 2}}R_{t + 3},\cdots$

The return $G_t$ can be written as

Then, it follows from the definition of the state value that

First, calculate the first term $\mathbb{E}[R_{t + 1}|S_t = s]$

Second, calculate the second term $\mathbb{E}[G_{t + 1}|S_t = s]$

Therefore, we have

Every state has an equation like this!!!

Example 1

Consider the state value of $s_1$:

• $\pi(a = a_3|s_1)=1$ and $\pi(a\neq a_3|s_1)=0$.

• $p(s' = s_3|s_1,a_3)=1$ and $p(s'\neq s_3|s_1,a_3)=0$.

• $p(r = 0|s_1,a_3)=1$ and $p(r\neq 0|s_1,a_3)=0$.

Substituting them into the Bellman equation gives and similarly, we have

Solve the above equations one by one from the last to the first:

Substituting $\gamma = 0.9$ yields

$v_{\pi}(s_4)=10,~v_{\pi}(s_3)=10,~v_{\pi}(s_2)=10,~v_{\pi}(s_1)=9$.

Example 2

We have

Solve the above equations one by one from the last to the first.

Substituting $\gamma = 0.9$ yields

$v_{\pi}(s_4)=10$, $v_{\pi}(s_3)=10$, $v_{\pi}(s_2)=10$, $v_{\pi}(s_1)=-0.5 + 9=8.5$.

Matrix vector form#

Recall that:

Rewrite the Bellman equation as

where

Suppose the states could be indexed as $s_i$ ($i = 1,\cdots,n$).

For state $s_i$, the Bellman equation is

Put all these equations for all the states together and rewrite to a matrix - vector form

where

• $v_{\pi}=[v_{\pi}(s_1),\cdots,v_{\pi}(s_n)]^{T}\in\mathbb{R}^{n}$

• $r_{\pi}=[r_{\pi}(s_1),\cdots,r_{\pi}(s_n)]^{T}\in\mathbb{R}^{n}$

• $P_{\pi}\in\mathbb{R}^{n\times n}$, where $[P_{\pi}]_{ij}=p_{\pi}(s_j|s_i)$, is the state transition matrix

If there are four states, $v_{\pi}=r_{\pi}+\gamma P_{\pi}v_{\pi}$ can be written out as

Example

For this specific example:

Example

For this specific example:

Solve state values#

The Bellman equation in matrix vector form is

In practice, we still need to use numerical tools to calculate the matrix inverse.

Can we avoid the matrix inverse operation? Yes, by iterative algorithms.

An iterative solution is:

$$v_{k + 1}=r_{\pi}+\gamma P_{\pi}v_{k}.$$

This algorithm leads to a sequence $\{v_0, v_1, v_2,\cdots\}$. We can show that

$$v_{k}\rightarrow v_{\pi}=(I - \gamma P_{\pi})^{-1}r_{\pi},\quad k\rightarrow\infty.$$

Proof. Define the error as $\delta_{k}=v_{k}-v_{\pi}$. We only need to show $\delta_{k}\rightarrow0$. Substituting $v_{k + 1}=\delta_{k + 1}+v_{\pi}$ and $v_{k}=\delta_{k}+v_{\pi}$ into $v_{k + 1}=r_{\pi}+\gamma P_{\pi}v_{k}$ gives

which can be rewritten as

As a result,

Note that $0\leq P_{\pi}^{k}\leq1$, which means every entry of $P_{\pi}^{k}$ is no greater than 1 for any $k = 0,1,2,\cdots$.

That is because $P_{\pi}^{k}\mathbf{1}=\mathbf{1}$, where $\mathbf{1}=[1,\cdots,1]^{T}$. On the other hand, since $\gamma < 1$, we know $\gamma^{k}\rightarrow0$ and hence $\delta_{k + 1}=\gamma^{k + 1}P_{\pi}^{k + 1}\delta_{0}\rightarrow0$ as $k\rightarrow\infty$.

Action Value#

The action value of a state - action pair $(s, a)$ is defined as

$$q_{\pi}(s,a)\doteq\mathbb{E}[G_t|S_t = s,A_t = a].$$

It represents the expected return obtained after taking action $a$ at state $s$.

It depends on the state - action pair $(s, a)$ rather than just an action.

The relationship between action values and state values

First, it follows from the properties of conditional expectation that

It then follows that $v_{\pi}(s)=\sum_{a\in\mathcal{A}}\pi(a|s)q_{\pi}(s,a)$ As a result, a state value is the expectation of the action values associated with that state.

Second, since the state value is given by

which leads to $q_{\pi}(s,a)=\sum_{r\in\mathcal{R}}p(r|s,a)r+\gamma\sum_{s'\in\mathcal{S}}p(s'|s,a)v_{\pi}(s').$

Example

Bellman optimality equation#

Optimal#

The state value could be used to evaluate if a policy is good or not: if

$v_{\pi_1}(s)\geq v_{\pi_2}(s)\quad\text{for all }s\in\mathcal{S}$

then $\pi_1$ is “better” than $\pi_2$.

A policy $\pi^*$ is optimal if $v_{\pi^*}(s)\geq v_{\pi}(s)$ for all $s$ and for any other policy $\pi$.

For every $s\in\mathcal{S}$, the elementwise expression of the BOE is

where $v(s),v(s')$ are unknown variables to be solved and

$q(s,a)\doteq\sum_{r\in\mathcal{R}}p(r|s,a)r+\gamma\sum_{s'\in\mathcal{S}}p(s'|s,a)v(s')$

Bellman optimality equation (matrix - vector form):

$v = \max_{\pi}(r_{\pi}+\gamma P_{\pi}v)$

where the elements corresponding to $s$ or $s'$ are

$[r_{\pi}]_{s}\triangleq\sum_{a}\pi(a|s)\sum_{r}p(r|s,a)r,$

$[P_{\pi}]_{s,s'}=p(s'|s)\triangleq\sum_{a}\pi(a|s)\sum_{s'}p(s'|s,a).$

Here $\max_{\pi}$ is performed elementwise.

Example: Consider two variables $x,a\in\mathbb{R}$. Suppose they satisfy

$$x = \max_{a}(2x - 1 - a^{2})$$

This equation has two unknowns. To solve them, first consider the right hand side. Regardless the value of $x$, $\max_{a}(2x - 1 - a^{2})=2x - 1$ where the maximization is achieved when $a = 0$. Second, when $a = 0$, the equation becomes $x = 2x - 1$, which leads to $x = 1$. Therefore, $a = 0$ and $x = 1$ are the solution of the equation.

Example (How to solve $\max_{\pi}\sum_{a}\pi(a|s)q(s,a)$) Suppose $q_1,q_2,q_3\in\mathbb{R}$ are given. Find $c_1^*,c_2^*,c_3^*$ solving

$\max_{c_1,c_2,c_3}c_1q_1 + c_2q_2 + c_3q_3$

where $c_1 + c_2 + c_3 = 1$ and $c_1,c_2,c_3\geq0$.

Without loss of generality, suppose $q_3\geq q_1,q_2$. Then, the optimal solution is $c_3^* = 1$ and $c_1^* = c_2^* = 0$. That is because for any $c_1,c_2,c_3$