Reinforcement Learning Note

Markov Decision Process

Markov Property

Definition

Markov property refers to the memoryless property of a Stochastic Process.

Consider a Probability Space $(\Omega ,\mathcal{F},P)$ with a Filtration $({\mathcal{F}}_s,s\in I)$, and a Measurable Space $(S,\mathcal{S})$. A Stochastic Process $X=\{X_t|\Omega \to S{\}}_{t\in I}$ is said to possess the Markov property if $\forall A\in \mathcal{S},\forall s,t\in I\text{s.t.}s<t,P(X_t\in A|{\mathcal{F}}_s)=P(X_t\in A|X_s)$ Here, ${\mathcal{F}}_s$ in the LHS represents all information up to time $s$, whereas $X_s$ conditions only on the single value at time $s$.

In the case where $S$ is a discrete set and $I=\mathbb{N}$, this can be reformulated as follows $\forall n\in \mathbb{N},P(X_{t+1}=x_{n+1}|X_n=x_n,\dots ,X_1=x_1)=P(X_{n+1}=x_{n+1}|X_n=x_n)$

Link to original

Markov Chain

Definition

$(S,P)$ A Markov chain is a Stochastic Process $\{X_t\}$ that satisfies Markov Property. It consists of a set of states $S$ and a Transition Probability Matrix $P$

Summary

Conditions and Properties of Markov Chain (Finite States)

Example	Finite	IRR	Aperiodicity	$\exists !{\mathbf{p}}^{\star }$^[a unique Limiting Distribution]	$\exists !\mathbf{\pi }$^[a unique Stationary Distribution]	$\bar{\mathbf{\pi }}\to \mathbf{\pi }$^[Ergodic Theorem]	$\bar{\mathbf{\pi }}\to \mathbf{\pi }={\mathbf{p}}^{\star }$^[Ergodicity]
	O	X	X	X	X	X	X
Identity/Block matrix	O	X	O	X	X	X	X
Exchange matrix	O	O	X	X	O	O	X
Ergodic Markov Chain	O	O	O	O	O	O	O

flowchart LR
  mc[HMC] --> finite
  
  subgraph finiteness
    finite([finite])
  end
  
  finite --> finite_mc
  finite_mc --> irreducible
  finite_mc --> reducible
  
  subgraph Irreducibility
    irreducible([irreducible])
    reducible([reducible])
  end
  irreducible --> irr_mc[Irreducible MC]
  reducible -->|divide|irr_mc

  irr_mc ---|holds|egt([Ergodic Theorem])
  irr_mc --> aperiodic
  
  subgraph Aperiodicity
    aperiodic([aperiodic])
  end
  
  aperiodic --> ergmc[Ergodic MC]

Conditions and Properties of Markov Chain (Infinite States)

IRR	Nature	Aperiodicity	$\exists !{\mathbf{p}}^{\star }$^[a unique Limiting Distribution]	$\exists !\mathbf{\pi }$^[a unique Stationary Distribution]	$\bar{\mathbf{\pi }}\to \mathbf{\pi }$^[Ergodic Theorem]	$\bar{\mathbf{\pi }}\to \mathbf{\pi }={\mathbf{p}}^{\star }$^[Ergodicity]
O	Transient	can’t define	X	X	X	X
O	Null recurrent	no matter	X	X	X	X
O	Positive recurrent	X	X	O	O	X
O	Positive recurrent	O	O	O	O	O

flowchart LR
  mc[HMC]
  mc --> irreducible
  mc --> reducible
  
  subgraph Irreducibility
    irreducible([irreducible])
    reducible([reducible])
  end
  
  irr_mc[Irreducible MC]
  irreducible --> irr_mc
  reducible -->|divide|irr_mc
  
  irr_mc --> pr
  irr_mc --> nr
  irr_mc --> tr
  
  subgraph Recurrence
    pr([positive recurrent])
    nr([null recurrent])
    tr([transient])
  end
    
  pr_mc[Recurrent MC]
  pr --> pr_mc
  pr_mc --> aperiodic

  egt([Ergodic Theorem])
  pr_mc ---|holds|egt

  subgraph Aperiodicity
    aperiodic([aperiodic])
  end
  
  aperiodic --> ergmc[Ergodic MC]

Link to original

Transition

Definition

${\mathbf{\mu }}_{t+1}={\mathbf{P}}^{⊺{\mathbf{\mu }}_t}\iff {\mathbf{\mu }}_{t+1}^{⊺}={\mathbf{\mu }}_t^{⊺}\mathbf{P}$

where $\mathbf{\mu }$ is the distribution of states and $\mathbf{P}$ is Transition Matrix

Link to original

Transition Probability

Definition

$p_{ij}=P(j|i)=P(X_{t+1}=j|X_t=i)$ where $\{X_t{\}}_{t\ge 0}$ is HMC that has countable state space $E$

The conditional probability of the Transition from state $i$ to $j$

Facts

$p_{ij}\ge 0$

Link to original

Transition Probability Matrix

Definition

$P=[P_{ij}]$ A transition probability matrix $P$ is a matrix whose $(i,j)$-th element is $p_{ij}$. where each $p_{ij}$ is a Transition Probability of HMC $\{X_t{\}}_{t\ge 0}$ having countable state space

Facts

Since the number of elements of state space can be infinity, strictly speaking $P$ is not a matrix. However, several operations of matrix are satisfied for the $P$

${\sum }_{j\in E}{p}_{ij}=1$ The sum of each row of a transition matrix is one

Link to original

Markov Decision Processes

Definition

Example of a simple MDP with three states (green circles) and two actions (orange circles), with two rewards (orange arrows)

Markov decision process (MDP) is a tuple $(S,A,P,R)$. Where:

• $S$: A set of states (State space)
• $A$: A set of actions (Action space)
• $P_{s{s}^{\prime }}^a=p(s^{\prime }|s,a)=P(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$: A Transition Probability from $s$ to $s^{\prime }$ given $a$.
• $R_{s{s}^{\prime }}^a=r(s,a,s^{\prime })$: The immediate Reward received after transitioning from state $s$ to $s^{\prime }$ due to action $a$.

Facts

Environmental model in MDP is the Transition Probability. If the Transition Probability is known, it is called a model-based MDP, otherwise called a model-free MDP.

Any Markov decision process satisfies the followings:

• There exists an optimal policy $\exists {\pi }_{\ast }\text{s.t.}\forall \pi ,\forall s,v_{{\pi }_{\ast }}(s)\ge v_{\pi }(s)$
• All optimal policies achieve the optimal state-value function $v_{{\pi }_{\ast }}(s)=v_{\ast }(s)$
• All optimal policies achieve the optimal action-value function $q_{{\pi }_{\ast }}(s,a)=q_{\ast }(s,a)$

Link to original

Reward

Definition

Reward $R_t$ is a scalar feedback indicating how well the agent is doing at step $t$.

There are three reward types:

• $R_s=r(s)$: the reward in the state $s$.
• $R_s^a=r(s,a)$: the reward by the action $a$ in the state $s$.
• $R_{s{s}^{\prime }}^a=r(s,a,s^{\prime })$: the reward received after transitioning from state $s$ to $s^{\prime }$ due to action $a$.

Expected Reward

Under known dynamics $p(s^{\prime },r|s,a)$ of all transitions $(s,a,s^{\prime },r)$, one can compute the followings:

• State transition probability $P_{s{s}^{\prime }}^a=p(s^{\prime }|s,a)=P(S_{t+1}=s^{\prime }|S_t=s,A_t=a)=\sum _{r\in \mathcal{R}}p(s^{\prime },r|s,a)$

• Expected reward for (state, action) pair $R_s^a=r(s,a)=E[R_{t+1}|S_t=s,A_t=a]=\sum _{r\in \mathcal{R}}r\sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime },r|s,a)$

• Expected reward for (state, action, next state) triple $R_{s{s}^{\prime }}^a=r(s,a,s^{\prime })=E[R_{t+1}|S_t=s,A_t=a,S_{t+1}=s^{\prime }]=\frac{\sum _{r\in \mathcal{R}}rp(s^{\prime },r|s,a)}{p(s^{\prime }|s,a)}$

Facts

Reinforcement learning is based on the Reward Hypothesis.

Link to original

Reward Hypothesis

Definition

All goals can be described by the maximization of the expected value of the cumulative sum of rewards.

Link to original

Return

Definition

$G_t:=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}=R_{t+1}+\gamma G_{t+1}$ where $\gamma \in [0,1]$ is a discount factor

Return $G_t$ is the total discounted Reward from time step $t$.

Link to original

Policy

Definition

Deterministic Policy

$\pi :S\to A,\pi (s)$ A deterministic policy $\pi$ is a mapping from state space $S$ to action space $A$.

Stochastic Policy

$\pi (a|s)=P(A_t=a|S_t=s)$ A stochastic policy $\pi$ is a probability distribution over actions $A$ for a given state $S$.

Optimal Policy

${\pi }_{\ast }(s)=\underset{a}{\mathrm{argmax}}{q}_{\ast }(s,a)$ A policy maximizing the cumulative sum of rewards is called an optimal policy.

Better Policy

Consider two policies $\pi$ and ${\pi }^{\prime }$. ${\pi }^{\prime }$ is better policy than $\pi$ if $\forall s,v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$

Facts

• Under known MDP, there exists deterministic optimal policy ${\pi }_{\ast }(s)$.
• Under unknown MDP, stochastic policy is needed.

Link to original

State-Value Function

Definition

$v_{\pi }(s)=E_{\pi }[G_t|S_t=s]=\sum _a\pi (a|s)q_{\pi }(s,a)$ where $q_{\pi }(s,a)$ is a Action-Value Function.

A state-value function $v_{\pi }(s)$ is the expected discounted Return starting in state $s$ under policy $\pi$.

Optimal State-Value Function

$v_{\ast }(s)=v_{{\pi }_{\ast }}(s)={\max }_{\pi }{v}_{\pi }(s)={\max }_a{q}_{\ast }(s,a)$ An optimal state-value function is the maximum possible state-value function (a state-value function under optimal policy).

Link to original

Action-Value Function

Definition

$q_{\pi }(s,a)=E_{\pi }[G_t|S_t=s,A_t=a]$ An action-value function $q_{\pi }(s,a)$ is the expected discounted Return of taking action $a$ starting in state $s$ under policy $\pi$.

Optimal Action-Value Function

$q_{\ast }(s,a)=q_{{\pi }_{\ast }}(s,a)={\max }_{\pi }{q}_{\pi }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\ast }(s^{\prime })$ An optimal action-value function is the maximum possible action-value function (an action-value function under optimal policy).

Link to original

Advantage Function

Definition

$A_{\pi }(s,a)=q_{\pi }(s,a)-v_{\pi }(s)$ An advantage function $A_{\pi }(s,a)$ is the difference between the Action-Value Function $q_{\pi }(s,a)$ and the State-Value Function $v_{\pi }(s)$ under policy $\pi$. It represents how much better it is to take action $a$ in state $s$ compared to the average action.

Link to original

Bellman Equation

Law of Total Probability

Definition

Suppose $\{B_n|n\in \mathbb{N}\}$ is a set of mutually and collectively exclusive events, then for any event $A$: $P(A)=\sum _{n}P(A|B_n)P(B_n)=\sum _{n}P(A,B_n)$

Link to original

Law of Large Numbers

Definition

Weak Law of Large Numbers

Consider a Sequence $\{X_n\}$ of i.i.d. random variables with mean $E[X_i]=\mu$, variance ${\sigma }^2<\infty$. Let ${\bar{X}}_n=\frac{1}{n}\sum _{i=1}^n{X}_i$ be the sample average. Then, the sample average converges in probability to the expected value. ${\lim }_{n\to \infty }{\bar{X}}_n\stackrel{P}{\to }\mu$

Strong Law of Large Numbers

Consider a Sequence $\{X_n\}$ of i.i.d. random variables with mean $E[X_i]=\mu$, variance ${\sigma }^2<\infty$. Let ${\bar{X}}_n=\frac{1}{n}\sum _{i=1}^n{X}_i$ be the sample average. Then, the sample average converges almost surely to the expected value. ${\lim }_{n\to \infty }{\bar{X}}_n\stackrel{a.s.}{\to }\mu$

Link to original

Bellman Expectation Equation

Definition

Bellman expectation equation is a recursive equation decomposing State-Value Function $v_{\pi }(s)$ into immediate Reward $R_s^a$ and discounted future state-value $\gamma v_{\pi }(s^{\prime })$.

Bellman Equation for State-Value Function

v_{\pi}(s) &= E_{\pi}[G_{t} | S_{t}=s]\\ &= P(A_{t}=a|S_{t}=s)\cdot E_{\pi}[G_{t} | S_{t}=s, A_{t}=a]\quad \left( = \sum\limits_{a} \pi(a|s) q_{\pi}(s, a) \right)\\ &= \sum\limits_{a} \pi(a|s) \cdot E_{\pi}[R_{t+1} + \gamma G_{t+1} | S_{t}=s, A_{t}=a]\\ &= \sum\limits_{a} \pi(a|s) \cdot \sum\limits_{s', r} E_{\pi}[R_{t+1} + \gamma G_{t+1} | S_{t}=s, A_{t}=a, S_{t+1}=s', R_{t+1}=r]\cdot P(S_{t+1}=s', R_{t+1}=r | S_{t}=s, A_{t}=a)\\ &= \sum\limits_{a} \pi(a|s) \cdot \sum\limits_{s', r} p(s', r | s, a)[r + \gamma E_{\pi}[G_{t+1} | S_{t+1}=s']]\quad \text{(by Markov property)}\\ &= \sum\limits_{a} \pi(a|s) \cdot \sum\limits_{s', r} p(s', r | s, a)[r + \gamma v_{\pi}(s')]\quad \left( =\sum\limits_{a} \pi(a|s)[R_{s}^{a} + \gamma \sum\limits_{s'}P_{ss'}^{a} v_{\pi}(s')] \right)\\ &= E_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_{t}=s] \end{aligned}$$ ## Bellman Equation for [[Action-Value Function]] ![[Pasted image 20241207130544.png|450]] $$\begin{aligned} q_{\pi}(s, a) &= E_\pi[G_{t} | S_{t}=s, A_{t}=a]\\ &= \sum\limits_{s'r}p(s', r | s, a)[r + \gamma \underbrace{\sum\limits_{a'} \pi(a'|s') q_{\pi}(s', a')}_{v_{\pi}(s')}]\quad \left( = R_{s}^{a} + \gamma \sum\limits_{s'} P_{ss'}^{a} \underbrace{\sum\limits_{a'} \pi(a'|s') q_{\pi}(s', a')}_{v_{\pi}(s')} \right)\\ &= E_{\pi}[R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_{t}=s, A_{t}=a] \end{aligned}$$Link to original

Bellman Optimality Equation

Definition

Under model-based (known MDP), the optimal value functions can be iteratively evaluated by dynamic programming.

Bellman Optimality Equation for State-Value Function

v_{*}(s) &= \max_{a} q_{*}(s, a)\\ &= \max_{a} E_{\pi_{*}}[G_{t} | S_{t}=s, A_{t}=a]\\ &= \max_{a} E_{\pi_{*}}[R_{t+1} + \gamma G_{t+1} | S_{t}=s, A_{t}=a]\\ &= \max_{a} E_{s',r}[R_{t+1} + \gamma v_{*}(S_{t+1}) | S_{t}=s, A_{t}=a]\\ &= \max_{a} \sum\limits_{s',r}p(s', r | s, a) [r + \gamma v_{*}(s')]\quad \left( =\max_{a} [R_{s}^{a} + \gamma\sum\limits_{s'}P_{ss'}^{a} v_{*}(s')] \right) \end{aligned}$$ ## Bellman Optimality Equation for [[Action-Value Function]] ![[Pasted image 20241207152144.png|450]] $$\begin{aligned} q_{*}(s, a) &= E_{s',r}[R_{t+1} + \gamma \max_{a'} q_{*}(S_{t+1}, a') | S_{t}=s, A_{t}=a]\\ &= \sum\limits_{s',r}p(s',r | s, a)[r + \gamma \max_{a'} q_{*}(s', a')]\quad \left(= R_{s}^{a} + \gamma \sum\limits_{s'}P_{ss'}^{a} \max_{a'} q_{*}(s', a') \right) \end{aligned}$$Link to original

Dynamic Programming

Dynamic Programming

Definition

Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems in a recursive manner.

Dynamic programming works when a problem has the following properties:

• Optimal substructure: An optimal solution can be constructed from optimal solutions of its sub-problems.
• Overlapping sub-problems: Solutions of same sub-problems are reused several times.

Algorithms

Value Iteration

Policy Iteration

Link to original

Value Iteration

Definition

Value iteration iteratively updates state-value function until convergence. Its time complexity is $O(S^{2}A)$ where $S$ and $A$ are the numbers of states and actions respectively.

Algorithm

1. Initialize $\forall s,V(s)=0$
2. Update $V(s)$ iteratively from all $V(s^{\prime })$ (full backup) until convergence to $V^{\ast }(s)$. $V(s)\leftarrow {\max }_a\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V(s^{\prime })]$
   • Synchronoius backups: compute $V_{k+1}(s)$ for all $s$ and update simultaneously.
   • Asynchronoius backups: compute $V_{k+1}(s)$ for one $s$ and update it immediately.
3. Compute the optimal policy ${\pi }_{\ast }$ (one-step lookahead) and return it. ${\pi }_{\ast }(s)=\underset{a}{\mathrm{argmax}}\underset{Q^{\ast }(s,a)}{\underbrace{\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\ast }(s^{\prime })]}}$

Link to original

Policy Improvement Theorem

Definition

Consider two policies $\pi$ and ${\pi }^{\prime }$. $\forall s\in S,Q^{\pi }(s,{\pi }^{\prime }(s))\ge V^{\pi }(s)(=)⟹\forall s\in S,V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s)$ This implies that ${\pi }^{\prime }$ is a better policy than $\pi$.

Link to original

Policy Iteration

Definition

Policy iteration repeats policy evaluation and policy improvement until convergence. Its time complexity is $O(S^2)$ where $S$ and $A$ are the numbers of states and actions respectively.

Compare to Value Iteration, policy iteration requires much fewer iterations to reach optimal policy.

Policy Evaluation

Compute $V^{\pi }$ from the deterministic policy $\pi$. $V_{k+1}(s)\leftarrow \sum _{s^{\prime },r}p(s^{\prime },r|s,\pi (s))[r+\gamma V_k(s^{\prime })]$

Policy Improvement

Improve $\pi$ to ${\pi }^{\prime }$ by greedy policy based on $V^{\pi }$. ${\pi }^{\prime }(s)=\underset{a}{\mathrm{argmax}}\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\pi }(s^{\prime })]=\underset{a}{\mathrm{argmax}}{Q}^{\pi }(s,a)$

Since $Q^{\pi }(s,{\pi }^{\prime }(s))\ge V^{\pi }(s)=\sum _a\pi (a|s)Q^{\pi }(s,a)$, always either ${\pi }^{\prime }$ is strictly better than $\pi$ or ${\pi }^{\prime }$ is optimal when ${\pi }^{\prime }=\pi$ by the Policy Improvement Theorem.

Algorithm

1. Initialize $\forall s,V(s)=0$, and $\forall s,\pi (s)\in \mathcal{A}(s)$ arbitrarily.
2. Update every $V(s)$ from all $V(s^{\prime })$ (full backup) until convergence to $V^{\pi }(s)$. $V(s)\leftarrow \sum _{s^{\prime },r}p(s^{\prime },r|s,\pi (s))[r+\gamma V(s^{\prime })]$
3. Improve $\pi$ by greedy policy based on $V^{\pi }$. $\pi (s)\leftarrow \underset{a}{\mathrm{argmax}}\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V(s^{\prime })]$
4. If policy is stable, then stop and return $V\approx v_{\ast }$ and $\pi \approx {\pi }_{\ast }$.

Examples

Link to original

Reinforcement Learning

Generalized Policy Iteration

Definition

Generalized policy iteration uses the repeatedly approximated value function to the true value of the current policy (sample backup) and the policy is repeatedly improved to approach the optimality.

Link to original

Monte Carlo Method

Definition

Monte Carlo method (MC) is tabular updating and model-free. MC policy iteration adapts GPI based on episode-by-episode (sample multi-step backup) of PE estimating $Q(s,a)=q_{\pi }(s,a)$ and $ϵ$-greedy PI.

MC Prediction (Policy Evaluation)

Learn $q_{\pi }$ from entire episodes of real experience under policy $\pi$.

Empirical Mean

MC policy evaluation uses empirical mean return $Q(s,a)$ instead of expected return. $Q(s,a)=\frac{S(s,a)}{n(s,a)}$ where $S(s,a)$ is increment total return and $n(s,a)$ is incremental count.

The mean return converges to true action-value function as incremental count increases. ${\lim }_{n(s,a)\to \infty }Q(s,a)=q_{\pi }(s,a)$

Incremental MC Update

The incremental mean can be expressed in a recursive manner: ${\mu }_k={\mu }_{k-1}+\frac{1}{k}(x_k-{\mu }_{k-1})$

Thus, for each state-action pair $(S_t,A_t)$ with return $G_t$, after one episode, the mean return $Q(s,a)$ can be calculated as: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\frac{1}{n(S_t,A_t)}[G_t-Q(S_t,A_t)]$

Constant-$\alpha$ MC Policy Evaluation

It substitutes the weights, $\frac{1}{n(S_t,A_t)}$ used for incremental MC, with constant step-size $\alpha$. $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [G_t-Q(S_t,A_t)]=(1-\alpha )Q(S_t,A_t)+\alpha G_t$

MC Control ($ϵ$-Greedy Policy Improvement)

Choose the greedy action with probability $1-ϵ$ and a random action with probability $ϵ$. ${\pi }^{\prime }(a|s)=\{\begin{array}{ll}1-ϵ+\frac{ϵ}{|\mathcal{A}(s)|}& a=\underset{a^{\prime }}{\mathrm{argmax}}{Q}^{\pi }(s,a^{\prime })\\ \frac{ϵ}{|\mathcal{A}(s)|}& \text{otherwise}\end{array}$

For any $ϵ$-greedy policy $\pi$, $ϵ$-greed policy ${\pi }^{\prime }$ with respect to $q_{\pi }$ is always improved i.e. $v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$.

$ϵ$-greedy policy is GLIE if ${ϵ}_k\to 0$ e.g. ${ϵ}_k=\frac{1}{k}$

Algorithm

1. Initialize $\forall s\in \mathcal{S},a\in \mathcal{A}(S),Q(S,A)$ arbitrarily, terminal $Q=0$, and arbitrary $ϵ$-soft policy $\pi$ (non-empty probability).
2. Repeat for each episode:
   1. Generate an episode following the policy $\pi$: $S_0,A_0,R_1,S_1,\dots ,S_{T-1},A_{T-1},R_T$.
   2. $G\leftarrow 0$
   3. Repeat for each step of an episode, $t=T-1,T-2,\dots ,0$ (MC Prediction):
      1. $G\leftarrow \gamma G+R_{t+1}$
      2. If $(S_t,A_t)$ is a first visit ($(S_t,A_t)\notin \{(S_i,A_i)|i=0,\dots ,t-1\}$), then $Q(S_t,A_t)\leftarrow AVG(\{G_t|t\in \{0,1,\dots ,T\},s=S_t,a=A_t\})$ where $AVG$ can be either incremental MC or constant-$\alpha$ MC.
   4. For each visited state $S_t$ in the episode (MC Control):
      1. $A^{\ast }\leftarrow \underset{a}{\mathrm{argmax}}Q(S_t,a)$
      2. $\pi (a|S_t)=\{\begin{array}{ll}1-ϵ+\frac{ϵ}{|\mathcal{A}(S)|}& a=A^{\ast }\\ \frac{ϵ}{|\mathcal{A}(S)|}& \text{otherwise}\end{array}$
3. If policy is stable, then stop and return $\pi \approx {\pi }_{\ast }$.

Facts

MC is less harmed by violations of Markov Property because it updates value estimates based on true Return $G_t$ (not based on value estimates of successor states).

Link to original

Time Difference Learnings

GLIE policy

Definition

A learning Policy is called GLIE (Greedy in Limit with Infinite Exploration) if it satisfies:

• All state-action pairs are explored infinitely many times $\forall s\in \mathcal{S},a\in \mathcal{A}(S),{\lim }_{k\to \infty }n(s,a)=\infty$ where $n(s,a)$ is incremental count of a $(s,a)$.
• The learning policy converges to a greedy policy. ${\lim }_{k\to \infty }{\pi }_k(a|s)=1$ where $a=\underset{a^{\prime }}{\mathrm{argmax}}{Q}_k(s,a^{\prime })$

Link to original

Temporal Difference Learning

Temporal Difference Learning (TD) is tabular updating and model-free. TD policy iteration adapts GPI based on one-step transitions of sample episodes.

Algorithms

Sarsa

Q-Learning

Examples

Sarsa allows for potential penalties from exploration moves, which tends to make it avoid a dangerous optimal path and prefers a slower but safer path. In contrast, Q-Learning ignores these penalties and takes action with the highest action value, which results in its occasional falling because of $ϵ$-greedy actions.

Sarsa allows for potential penalties from exploration moves, which tends to make it avoid a dangerous optimal path and prefer a slower but safer path. In contrast, Q-Learning ignores these penalties and takes action based on the highest action value, which can occasionally result in falling off due to $ϵ$-greedy action.

Link to original

Sarsa

Definition

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$ Sarsa learns $Q^{\pi }$ by using Bellman Expectation Equation. The both behavior and target policies of Sarsa is derived from $Q$, so it is an on-policy method.

Algorithm

1. Initialize $\forall s\in \mathcal{S},a\in \mathcal{A}(S),Q(s,a)$ arbitrarily, and $Q(\text{terminal},\cdot )=0$.
2. Repeat for each episode:
   1. Initialize $S$.
   2. Choose an action $A$ from the initial state $S$ using policy derived from $Q$ (e.g. $ϵ$-greedy).
   3. Repeat for each step of an episode until $S$ is terminal:
      1. Take the action $A$ and observe a reward $R$ and a next state $S^{\prime }$.
      2. Choose an action $A^{\prime }$ from the next state $S^{\prime }$ using policy derived from $Q$ (e.g. $ϵ$-greedy).
      3. $Q(S,A)\leftarrow Q(S,A)+\alpha [R+\gamma Q(S^{\prime },A^{\prime })-Q(S,A)]$
      4. Update $S\leftarrow S^{\prime }$ and $A\leftarrow A^{\prime }$

Link to original

Q-Learning

Definition

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma {\max }_{a}Q(S_{t+1},a)-Q(S_t,A_t)]$ Q-learning directly learns $Q^{\ast }$ by using Bellman Optimality Equation. The behavior policy of Q-learning is derived from $Q$ while the target policy is ${\max }_{a}Q$, so it is an off-policy method.

Algorithm

1. Initialize $\forall s\in \mathcal{S},a\in \mathcal{A}(S)$, $Q(s,a)$ arbitrarily, and $Q(\text{terminal},\cdot )=0$.
2. Repeat for each episode:
   1. Initialize $S$.
   2. Repeat for each step of an episode until $S$ is terminal:
      1. Choose an action $A$ from the initial state $S$ using policy derived from $Q$ (e.g. $ϵ$-greedy).
      2. Take the action $A$ and observe a reward $R$ and a next state $S^{\prime }$.
      3. $Q(S,A)\leftarrow Q(S,A)+\alpha [R+\gamma \underset{a}{\max }Q(S^{\prime },a)-Q(S,A)]$
      4. Update $S\leftarrow S^{\prime }$

Link to original

Importance Sampling

Definition

Importance sampling is used when we want to estimate the expectation $E_{p(x)}[f(x)]$ of a function $f$ under a probability distributtion $p(x)$, but sampling directly from the distribution is either inefficient or impossible. $E_{p(x)}[f(x)]=\int f(x)\frac{p(x)}{q(x)}q(x)dx=E_{q(x)}\left[f(x)\frac{p(x)}{q(x)}\right]\approx \frac{1}{N}\sum _{n=1}^N\frac{p(x_n)}{q(x_n)}f(x_n)$ Where

• $p(x)$ is the target distribution
• $q(x)$ is the proposal distribution whose support includes that of the support of the target distribution $p(x)$ ($\forall x,p(x)>0\Rightarrow q(x)>0$). The proposal distribution needs to be easy to evaluate and sample from. Also, to reduce the variance of the expectation, $q(x)$ should be high where $|p(x)f(x)|$ is high.
• $\frac{p(x)}{q(x)}$ is the importance weight.

Link to original

Off-Policy Control

Definition

Off-policy control uses two different policies for target policy $\pi$ and behavior policy $\mu$. The target policy $\pi$ may be deterministic while the behavior policy $\mu$ is stochastic. It enables the model to learn optimal policy while maintaining exploration.

Almost all off-policy method utilize Importance Sampling. The Return obtained under the target policy is weighted according to the relative probability of the trajectories under the target and behavior policy, called the importance-sampling ratio (importance weight).

Given a starting state $S_t$, the probability of the state-action trajectory $\{A_t,S_{t+1},A_{t+1},\dots ,S_T\}$ occurring under a policy $\pi$ is written as $P(\{A_t,S_{t+1},A_{t+1},\dots ,S_T\}|S_t,A_{t:T-1}\sim \pi )={\prod }_{k=t}^{T-1}\pi (A_k|S_k)p(S_{k+1}|S_k,A_k)$ where $p$ is the state-transition probability.

Thus, the relative probability of the trajectory under the target and behavior policies is ${\rho }_{t:T-1}={\prod }_{k=t}^{T-1}\frac{\pi (A_k|S_k)}{\mu (A_k|S_k)}$

Algorithms

Off-policy MC

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left[{\rho }_{t:T-1}{G}_t-Q(S_t,A_t)\right]$ where ${\rho }_{t:T-1}$ is the importance weight.

The variance of return in Monte Carlo method can dramatically higher.

Off-policy Sarsa

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left[\frac{\pi (A_{t+1}|S_{t+1})}{\mu (A_{t+1}|S_{t+1})}(R_{t+1}+\gamma Q(S_{t+1},A_{t+1}))-Q(S_t,A_t)\right]$

The variance of return in off-policy TD is lower than MC’s one.

Link to original

Expected Sarsa

Definition

Q(S_{t}, A_{t}) &\leftarrow Q(S_{t}, A_{t}) + \alpha [R_{t+1} + \gamma E_{\pi}[Q(S_{t+1}, A_{t+1})|S_{t+1}] - Q(S_{t}, A_{t})]\\ &(= Q(S_{t}, A_{t}) + \alpha [R_{t+1} + \gamma \sum\limits_{a \in \mathcal{A}(S_{t+1})} Q(S_{t+1}, a)\pi(a | S_{t+1}) - Q(S_{t}, A_{t})) \end{aligned}$$ Expected Sarsa uses the expected value over the next state-action pairs, so all actions viable in the state are considered. Expected Sarsa performs better than [[Sarsa]] in terms of the variance of its [[Return]] but costs more.Link to original

Double Q-Learning

Definition

Q-Learning takes the action with the highest value, which tends to overestimate the value of actions (maximization bias) in the early stages of learning, slowing the convergence to $q_{\ast }(s,a)$.

Double Q-learning uses two Q-value functions to overcome this problem: one for action selection and another for value evaluation.

Algorithm

1. Initialize $\forall s\in \mathcal{S},a\in \mathcal{A}(S)$, $Q_1(s,a)$, and $Q_2(s,a)$ arbitrarily, and $Q_1(\text{terminal},\cdot )=0$ and $Q_2(\text{terminal},\cdot )=0$.
2. Repeat for each episode:
   1. Initialize $S$.
   2. Repeat for each step of an episode until $S$ is terminal:
      1. Choose an action $A$ from the initial state $S$ using policy derived from $Q_1$ and $Q_2$ (e.g. $ϵ$-greedy in $Q_1+Q_2$).
      2. Take the action $A$ and observe a reward $R$ and a next state $S^{\prime }$.
      3. With probability $0.5$: $Q_1(S,A)\leftarrow Q_1(S,A)+\alpha [R+\gamma Q_2(S^{\prime },\underset{a}{\mathrm{argmax}}{Q}_1(S^{\prime },a))-Q_1(S,A)]$ else: $Q_2(S,A)\leftarrow Q_2(S,A)+\alpha [R+\gamma Q_1(S^{\prime },\underset{a}{\mathrm{argmax}}{Q}_2(S^{\prime },a))-Q_2(S,A)]$
      4. Update $S\leftarrow S^{\prime }$

Examples

Q-Learning initially learns to take the left action much more often than the right action despite the lower true state-value of the left. Even at asymptote, it takes the left action more than optimal (5%). In contrast, double Q-learning is unaffected by maximization bias.

Link to original

n-Step Bootstrapping

n-Step Return

Definition

G_{t:t+n} :&= \sum\limits_{k=0}^{n-1}\gamma^{k} R_{t+k+1} + \gamma^{n}V(S_{t+n}) \\ &= R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^{n}V(S_{t+n}) \end{aligned}$$ n-step returns can be considered approximations to the full [[Return]], truncated after $n$ steps and then corrected for remaining missing terms by the [[State-Value Function|state-value]] estimator $V(S_{t+n})$. # Examples - $G_{t:t+1}$: (one-step) [[Temporal Difference Learning|TD]] target - $G_{t:t+n}$: [[n-Step TD]] target - $G_{t:\infty}$: [[Monte Carlo Method|MC]] targetLink to original

n-Step TD

Definition

$V(S_t)\leftarrow V(S_t)+\alpha [G_{t:t+n}-V(S_t)]$ where $G_{t:t+n}$ is the n-Step Return.

The n-step TD learning is a method that bridges the gap between TD and MC methods.

Examples

• $n=1$: Temporal Difference Learning
• $n=\infty$: Monte Carlo Method

Larger $n$ reduces bias but increases variance.

Link to original

n-Step Sarsa

Definition

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [G_{t:t+n}-Q(S_t,A_t)]$ where $G_{t:t+n}:=\sum _{k=0}^{n-1}{\gamma }^k{R}_{t+k+1}+{\gamma }^{n}Q(S_{t+n},A_{t+n})$ is the n-Step Return.

Link to original

n-step Off-Policy Learning

Definition

The relative probability of the n-step trajectory under the target and behavior policies is ${\rho }_{t:t+n}={\prod }_{k=t}^{t+n}\frac{\pi (A_k|S_k)}{\mu (A_k|S_k)}$

Algorithms

Off-policy n-Step TD

$V(S_t)\leftarrow V(S_t)+\alpha [{\rho }_{t:t+n}{G}_{t:t+n}-V(S_t)]$ where ${\rho }_{t:t+n}$ is the importance weight.

Off-policy n-Step Sarsa

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [{\rho }_{t:t+n}{G}_{t:t+n}-Q(S_t,A_t)]$ where ${\rho }_{t:t+n}$ is the importance weight, and $G_{t:t+n}:=\sum _{k=0}^{n-1}{\gamma }^k{R}_{t+k+1}+{\gamma }^{n}Q(S_{t+n},A_{t+n})$.

Link to original

Eligibility Traces

lambda-Return

Definition

The $\lambda$-return is a way to combine $n$-step returns for different $n$‘s using a weighted average.

G_{t}^{\lambda} :&= (1-\lambda) \sum\limits_{n=1}^{\infty}\lambda^{n-1} G_{t:t+n}\\ &= (1-\lambda) \sum\limits_{n=1}^{T-t-1}\lambda^{n-1} G_{t:t+n} + \lambda^{T-t-1}G_{t} \end{aligned}$$ where $G_{t:t+n}$ is the [[n-Step Return]]. # Examples - $\lambda=0$: [[Temporal Difference Learning|TD]] target - $\lambda =1$: [[Monte Carlo Method|MC]] return - $0 < \lambda < 1$: creates a smooth blend of all $n$-step returns.Link to original

TD(lambda)

Definition

TD($\lambda$) is a TD algorithm that uses the lambda-Return for value function updates. $V(S_t)\leftarrow V(S_t)+\alpha [G_t^{\lambda }-V(S_t)]$ where $G_t^{\lambda }$ is the lambda-Return

Examples

• $TD(0)$: Temporal Difference Learning
• $TD(1)$: Monte Carlo Method

Link to original

Deep Reinforcement Learning

DQNs

Deep Q-Network

Definition

DQN has large or continuous state space and discrete action space.

Naive DQN

Naive DQN treats $r_{t+1}+\gamma {\max }_{a}Q(s_{t+1},a;\theta )$ as a target and minimizes MSE loss by SGD. $L(\theta )=[r_{t+1}+\gamma {\max }_{a}Q(s_{t+1},a;\theta )-Q(s_t,a_t;\theta ){]}^2$

Due to the training instability and correlated samples, the Naive DQN has very poor results, even worse than a linear model.

Experience Replay

Online RL agents incrementally update parameters while observing a stream of experience. This structure cause strongly temporally-correlated updates, breaking i.i.d. assumption, and rapidly forget rare experiences that would be useful later on. Experience replay stores experiences $(s,a,r,s^{\prime })$ in the replay buffer, and randomly samples temporally uncorrelated minibatches from the replay buffer when learning.

Target Network

If target function is changed too frequently, then this moving target makes training difficult (non-stationary target problem). The target network technique updates the parameters of the behavior Q-network $Q(\cdot ;\theta )$ at every step, while updating the parameters of the target Q-network $\hat{Q}(\cdot ;\hat{\theta })$ sporadically (e.g. every $k$ steps). $L(\theta )=\frac{1}{B}\sum _{i\in I}[r_{i+1}+\gamma {\max }_a\hat{Q}(s_{i+1},a;\hat{\theta })-Q(s_i,a_i;\theta ){]}^2$ where $B$ is the size of a minibatch, and $I$ is a $B$-sized index set drew from the replay buffer.

Algorithm

1. Initialize behavior network $Q$ and target network $\hat{Q}$ with random weights $\theta$, and the replay buffer $\mathcal{R}$ to max size $N$.
2. Repeat for each episode:
   1. Initialize sequence $s_0$.
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. With probability $ϵ$, select a random action $a_t$ otherwise select $a_t=\underset{a}{\mathrm{argmax}}Q(s_t,a;\theta )$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. Store transition $(s_t,a_t,r_{t+1},s_{t+1})$ in the replay buffer $\mathcal{R}$.
      4. Sample random minibatch of $B$ transitions $(s_i,a_i,r_{i+1},s_{i+1})$ from $\mathcal{R}$.
      5. $y_i\leftarrow r_{i+1}+\gamma \underset{a}{\max }\hat{Q}(s_{i+1},a;\hat{\theta })$.
      6. Perform Gradient Descent on loss $L(\theta )=(y_i-Q(s_i,a_i;\theta ){)}^2$.
      7. Update the target network parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      8. Update $s_t\leftarrow s_{t+1}$.

Link to original

Double DQN

Definition

Double DQN is a variation of DQN that uses the idea of Double Q-Learning to reduce overestimation. In this case, the target network in DQN works as the second network for double Q-learning without introducing an additional network.

$L(\theta )=[r_{t+1}+\gamma \hat{Q}(s_{t+1},\underset{a}{\mathrm{argmax}}Q(s_{t+1},a;\theta );\hat{\theta })-Q(s_t,a_t;\theta ){]}^2$

Algorithm

1. Initialize behavior network $Q$ and target network $\hat{Q}$ with random weights $\theta$, and the replay buffer $\mathcal{R}$ to max size $N$.
2. Repeat for each episode:
   1. Initialize sequence $s_0$.
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. With probability $ϵ$, select a random action $a_t$ otherwise select $a_t=\underset{a}{\mathrm{argmax}}Q(s_t,a;\theta )$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. Store transition $(s_t,a_t,r_{t+1},s_{t+1})$ in the replay buffer $\mathcal{R}$.
      4. Sample random minibatch of $B$ transitions $(s_i,a_i,r_{i+1},s_{i+1})$ from $\mathcal{R}$.
      5. $y_i\leftarrow r_{i+1}+\gamma \hat{Q}(s_{i+1},\underset{a}{\mathrm{argmax}}Q(s_{i+1},a;\theta );\hat{\theta })$.
      6. Perform Gradient Descent on loss $L(\theta )=(y_i-Q(s_i,a_i;\theta ){)}^2$.
      7. Update the target network parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      8. Update $s_t\leftarrow s_{t+1}$.

Link to original

TD Error

Definition

The TD error $\delta$ is the difference between the target and the current prediction.

TD error for State-Value Function

${\delta }_t=r_{t+1}+\gamma V(s_{t+1})-V(s_t)$

TD error for SARSA

${\delta }_t=r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)$

TD error for Q-Learning

${\delta }_t=r_{t+1}+\gamma {\max }_{a}Q(s_{t+1},a)-Q(s_t,a_t)$

Link to original

Prioritized Replay

Definition

Prioritized replay is an enhancement to the standard experience replay. Instead of uniformly sampling experiences from the replay buffer, prioritized replay samples important transitions more frequently based on their priority values. It makes it possible to learn more efficiently as the agent focuses on important experiences more.

The priority of transition $i$ is calculated by TD Error. $p_i=|{\delta }_i|+ϵ$ where $\delta$ is the TD Error, and $ϵ\in {\mathbb{R}}^{+}$.

The probability of sampling transition $i$ is $P(i)=\frac{p_i^{\alpha }}{{\sum }_k{p}_k^{\alpha }}$ where $\alpha$ controls how much prioritization is used (uniform sampling if $\alpha =0$).

However, it can lead to a loss of diversity and introduce bias, but these issues can be alleviated and corrected with stochastic sampling prioritization (using $\alpha$) and Importance Sampling weights.

The Importance Sampling weights are calculated as $w_i={\left(\frac{1}{N}\cdot \frac{1}{P(i)}\right)}^{\beta }$ where

• $N$ is the size of the replay buffer
• $\beta \in [0,1]$ is annealing parameter that fully compensates the bias when $\beta =1$. It starts from $0$ and ends with $1$.

The wight $w_i$ is normalized by $\frac{1}{\underset{k}{\max }{w}_k}$ before used for stability.

Algorithm

Double DQN with Prioritized Replay

1. Initialize behavior network $Q$ and target network $\hat{Q}$ with random weights $\theta$, and the replay buffer $\mathcal{R}$ to max size $N$.
2. Repeat for each episode:
   1. Initialize sequence $s_0$.
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. With probability $ϵ$, select a random action $a_t$ otherwise select $a_t=\underset{a}{\mathrm{argmax}}Q(s_t,a;\theta )$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. Store transition $(s_t,a_t,r_{t+1},s_{t+1})$ in the replay buffer $\mathcal{R}$ with maximal priority $p_t=\underset{i<t}{\max }{p}_i$.
      4. For every $K$ (replay period) steps:
         1. Sample random minibatch of $B$ transitions $(s_i,a_i,r_{i+1},s_{i+1})\sim P(i)=\frac{p_i^{\alpha }}{{\sum }_k{p}_k^{\alpha }}$ from $\mathcal{R}$.
         2. Compute the importance weight $w_i=\frac{(NP(i){)}^{-\beta }}{\underset{k}{\max }{w}_k}$
         3. Compute TD Error ${\delta }_t=r_{i+1}+\gamma \hat{Q}(s_{i+1},\underset{a}{\mathrm{argmax}}Q(s_{i+1},a;\theta );\hat{\theta })-Q(s_i,a_i;\theta )$
         4. Update transition priority $p_i\leftarrow |{\delta }_i|+ϵ$
         5. Accumulate weight-change $\Delta \leftarrow \Delta +w_i{\delta }_i{\nabla }_{\theta }Q(s_i,a_i;\theta )$
      5. Update behavior network weights $\theta \leftarrow \theta +\eta \Delta$ and reset $\Delta =0$
      6. Update the target network parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      7. Update $s_t\leftarrow s_{t+1}$.

Link to original

Dueling DQN

Definition

Dueling DQN has two streams: advantage $A(s,a)$ and action-independent state-value $V(s)$, sharing a feature encoder (CNN), and combined by an aggregator to produce action-value $Q(s,a)=V(s)+A(s,a)$.

Aggregating module is unidentifiable in the sense that given a Q-value function, there are multiple possible decompositions into value and advantage functions ($\because Q(s,a)=(V(s)+c)+(A(s,a)-c)$ where $c$ is a constant value). This makes learning process unstable and less efficient. To force a unique decomposition, we introduce a constraint that makes the Advantage Function have zero-mean. $Q(s,a)=V(s)+\left(A(s,a)-\frac{1}{|\mathcal{A}|}\sum _{a^{\prime }}A(s,a^{\prime })\right)$

Link to original

REINFORCE

Policy Gradient

Definition

Policy gradient algorithms directly learn the optimal policy by a parametric probability distribution ${\pi }_{\theta }(a|s)$. The policy stochastically selects an action $a$ in a state $s$ according to a parameter $\theta$. It typically proceeds by sampling a stochastic policy and adjusting the parameter $\theta$ in the direction of maximizing the total reward.

The objective function of policy gradient algorithm is defined as: $J(\theta )=E_{{\pi }_{\theta }}[r(\tau )]=\int p(\tau ;\theta )r(\tau )d\tau$ where $\tau$ is a trajectory, $r(\tau )$ is the total reward of the trajectory $\tau$, and $p(\tau ;\theta )={\pi }_{\theta }(\tau )$ is the PDF of $\tau$.

Link to original

Policy Gradient Theorem

Definition

${\nabla }_{\theta }J(\theta )={\nabla }_{\theta }{E}_{{\pi }_{\theta }}[r(\tau )]=E_{{\pi }_{\theta }}\left[r(\tau ){\sum }_{t=0}^{T-1}{\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)\right]$ The derivative of the expected total reward is the expectation of the product of total rewards and summed gradients of log of the policy ${\pi }_{\theta }$.

Proof

$\nabla E_{\pi }[r(\tau )]=\nabla \int r(\tau )\pi (\tau )d\tau =\int \frac{\nabla \pi (\tau )}{\pi (\tau )}r(\tau )\pi (\tau )d\tau =\int \nabla \ln (\pi (\tau ))r(\tau )\pi (\tau )d\tau =E[\nabla \ln (\pi (\tau ))r(\tau )]$ $\nabla \ln \pi (\tau )=\nabla \ln (p(s_0){\prod }_{t=0}^{T-1}\pi (a_t|s_t)p(s_{t+1}|s_t,a_t))=\sum _{t=0}^{T-1}\nabla \ln \pi (a_t|s_t)$

Link to original

REINFORCE

Definition

${\nabla }_{\theta }J(\theta )\approx \frac{1}{M}\sum _{i=1}^M\left[{\sum }_{t=0}^{T-1}{G}_t^{(i)}{\nabla }_{\theta }\ln {\pi }_{\theta }(a_t^{(i)}|s_t^{(i)})\right]$ REINFORCE algorithm is a policy gradient algorithm that maximizes the expected return. The objective function of REINFORCE algorithm based on the Policy Gradient Theorem. It substitutes the expectation and the total reward of Policy Gradient with averaging and returns $G_t$.

Algorithm

1. Execute $M$ trajectories (Each starts from a state $s$ under the policy ${\pi }_{\theta }$).
2. Approximate the gradient of the objective function $J(\theta )$ $g_{\theta }\leftarrow \frac{1}{M}\sum _{i=1}^M\left[{\sum }_{t=0}^{T-1}{G}_t^{(i)}{\nabla }_{\theta }\ln {\pi }_{\theta }(a_t^{(i)}|s_t^{(i)})\right]$
3. Update policy to maximize $J(\theta )$ $\theta \leftarrow \theta +\alpha g_{\theta }$ where $\alpha$ is a learning rate.

Link to original

REINFORCE with Baseline

Definition

REINFORCE with Baseline algorithm is a variant of the REINFORCE algorithm that helps reduce variance in Policy Gradient methods by adopting Actor-Critic Method. It modifies the objective function of the REINFORCE algorithm by subtracting a baseline from the returns, which helps reduce the variance of the gradient without introducing bias. ${\nabla }_{\theta }J(\theta )={\nabla }_{\theta }{E}_{{\pi }_{\theta }}[r(\tau )]=E_{{\pi }_{\theta }}\left[{\sum }_{t=0}^{T-1}(G_t-b(s_t)){\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)\right]$ where $b(s_t)$ is a baseline function not related to $a_t$ (commonly chosen as a State-Value Function $V(s)=E_{{\pi }_{\theta }}[G_t|S_t=s]$).

Actor (Policy Gradient Update)

$\Delta \theta =\alpha (G_t-V(s_t;\varphi )){\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)$

Critic (Value Network Update)

$\Delta \varphi =\beta (G_t-V(s_t;\varphi )){\nabla }_{\varphi }V(s_t;\varphi )$

Algorithm

1. Initialize state-value $V(s;\varphi )$ and policy $\pi (a|s;\theta )$ networks randomly.
2. Set the hyperparameters: step-sizes $\alpha ,\beta >0$, and discount factor $0<\gamma \le 1$
3. Repeat for each episode (Each starts from a state $s$ under the policy ${\pi }_{\theta }$):
   1. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. $\delta \leftarrow G_t-V(s_t;\varphi )$
      2. $\varphi \leftarrow \varphi +\beta \delta {\nabla }_{\varphi }V(s_t;\varphi )$ (minimize $L(\varphi )=E_{\pi }[{\sum }_{t=0}^{T-1}(G_t-V(s_t;\varphi ){)}^2]$)
      3. $\theta \leftarrow \theta +\alpha {\gamma }^t\delta {\nabla }_{\theta }\ln \pi (a_t|s_t;\theta )$ (maximize $J(\theta )$ with the Policy Gradient ${\nabla }_{\theta }J(\theta )=E_{{\pi }_{\theta }}\left[{\sum }_{t=0}^{T-1}(G_t-V(s_t;\varphi )){\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)\right]$)

Link to original

Actor-Critics

Actor-Critic Method

Definition

Actor-Critic method consists of two networks: actor and critic networks.

Actor network updates parameter $\theta$ for policy ${\pi }_{\theta }(a|s)$ by maximizing $J(\theta )$ using Policy Gradient ${\nabla }_{\theta }J(\theta )=E_{{\pi }_{\theta }}\left[{\sum }_{t=0}^{T-1}\text{target}{\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)\right]$

Critic network updates parameter $\varphi$ for value function $V(s;\varphi )$ by minimizing $L(\varphi )=E_{\pi }[{\sum }_{t=0}^{T-1}(\text{target}-V(s_t;\varphi ){)}^2]$

Examples

REINFORCE with Baseline

Actor-Critic Method with TD(0) Return

Asynchronous Advantage Actor-Critic Method

Deterministic Policy Gradient

Deep Deterministic Policy Gradient

Link to original

Actor-Critic Method with TD(0) Return

Definition

Actor (Policy Gradient Update)

$\Delta \theta =\alpha (r_{t+1}+\gamma V(s_{t+1};\varphi )-V(s_t;\varphi )){\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)$

Critic (Value Network Update)

$\Delta \varphi =\beta (r+\gamma V(s_{t+1};\varphi )-V(s_t;\varphi )){\nabla }_{\varphi }V(s_t;\varphi )$

Algorithm

1. Initialize critic $V(s;\varphi )$ and actor $\pi (a|s;\theta )$ networks randomly.
2. Set the hyperparameters: step-sizes $\alpha ,\beta >0$, and discount factor $0<\gamma \le 1$
3. Repeat for each episode (Each starts from a state $s$ under the policy ${\pi }_{\theta }$):
   1. $I=1$
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. Select action $a$ according to policy $\pi (\cdot |s;\theta )$.
      2. Take the action $a$ and observe a reward $r$ and a next state $s^{\prime }$.
      3. $\delta \leftarrow r+\gamma V(s^{\prime };\varphi )-V(s;\varphi )$
      4. $\varphi \leftarrow \varphi +\beta \delta {\nabla }_{\varphi }V(s;\varphi )$
      5. $\theta \leftarrow \theta +\alpha I\delta {\nabla }_{\theta }\ln \pi (a|s;\theta )$
      6. $I\leftarrow \gamma I$
      7. $s\leftarrow s^{\prime }$

Link to original

Asynchronous Advantage Actor-Critic Method

Definition

A3C (Asynchronous Advantage Actor-Critic Method) is an Actor-Critic Method that utilizes multiple networks which are a global network and multiple worker agents working in parallel across multiple instances of the environment, and agents update asynchronously the global network parameter. The parallelism reduce each agent’s temporal correlation. The return $G_{t:t+n}-V(s_t)$ estimates the Advantage Function $Q(s_t,a_t)-V(s_t)$ using the n-Step Return $G_{t:t+n}$ instead of Action-Value Function $Q(s_t,a_t)$.

Actor (Policy Gradient Update)

$\Delta \theta =\alpha [(G_{t:t+n}-V(s_t;\varphi )){\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)+\lambda H({\pi }_{\theta }(a_t|s_t))]$ where $H(p(x))=-\int p(x)\ln p(x)dx$ is an Entropy that encourages exploration

Critic (Value Network Update)

$\Delta \varphi =\beta (G_{t:t+n}-V(s_t;\varphi )){\nabla }_{\varphi }V(s_t;\varphi )$

Algorithm

For each worker agent

1. Let $\theta ,\varphi$ be global network’s shared parameters, and let ${\theta }^{\prime },{\varphi }^{\prime }$ be a worker agent’s parameters.
2. Set the hyperparameters: step-sizes $\alpha ,\beta >0$, discount factor $0<\gamma \le 1$, regularization factor $\lambda$, maximum steps per update $t_{\text{max}}$.
3. Repeat:
   1. Reset gradients $d\theta \leftarrow 0$ and $d\varphi \leftarrow 0$.
   2. Synchronize parameters ${\theta }^{\prime }\leftarrow \theta$ and $\varphi \leftarrow {\varphi }^{\prime }$.
   3. Set $t_{\text{start}}\leftarrow t$ and get state $s_t$.
   4. For $t\le t_{\text{start}}+t_{\text{max}}$:
      1. Select action $a_t$ according to policy $\pi (\cdot |s_t;{\theta }^{\prime })$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. $t\leftarrow t+1$
   5. $R=V(s_t;{\varphi }^{\prime })$ (or $0$ for terminal $s_t$)
   6. For $i=t-1,t-2,\dots ,t_{\text{start}}$:
      1. $R\leftarrow r_{i+1}+\gamma R$.
      2. Accumulate gradients with respect to ${\theta }^{\prime }$ $d\theta \leftarrow d\theta +(R-V(s_i;{\varphi }^{\prime })){\nabla }_{{\theta }^{\prime }}\ln {\pi }_{{\theta }^{\prime }}(a_i|s_i)+\lambda H({\pi }_{\theta }(a_i|s_i))]$
      3. Accumulate gradients with respect to ${\varphi }^{\prime }$ $d\varphi \leftarrow d\varphi -(R-V(s_i;{\varphi }^{\prime })){\nabla }_{{\varphi }^{\prime }}V(s_t;{\varphi }^{\prime })$
   7. Update asynchronously $\theta \leftarrow \theta +\alpha d\theta$ and $\varphi \leftarrow \varphi -\beta d\varphi$.

Link to original

DPGs

Deterministic Policy Gradient

Definition

Deterministic Policy Gradient (DPG) learns a deterministic policy $a=\mu (s)$ as an actor on continuous action spaces and an Action-Value Function $Q(s,a)$ as a critic.

DPG requires fewer samples to approximate the gradient than stochastic Policy Gradient because DPG updates the parameter only over the state space, according to the Deterministic Policy Gradient Theorem. $\Delta \theta ={\nabla }_{a}Q(s,a){|}_{a=\mu (s;\theta )}{\nabla }_{\theta }\mu (s;\theta )$

Link to original

State Visitation Frequency

Definition

State visitation frequency is the discounted sum of probabilities of visiting a given state $s$ under policy $\pi$. ${\rho }_{\pi }(s)=\sum _{t=0}^{\infty }{\gamma }^{t}P(s_t=s|\pi )={\int }_S{\sum }_{t=0}^{\infty }{\gamma }^t{p}_0(s^{\prime })p_t(s^{\prime }\to s|\pi )d{s}^{\prime }$ where $p_0(s^{\prime })$ is the initial and $p_t(s^{\prime }\to s|\pi )$ is the visitation probability from $s^{\prime }$ to $s$ in $t$ step following $\pi$.

$(1-\gamma ){\rho }_{\pi }$ can be considered as a Distribution Function over the state space.

Link to original

Deterministic Policy Gradient Theorem

Definition

\nabla_{\theta}J(\theta) &= \nabla_{\theta} E_{s\sim \rho_{\mu}}[Q(s, a)|_{a=\mu(s;\theta)}]\\ &= \int_{S} \rho_{\mu}(s)\nabla_{a}Q(s, a)|_{a=\mu(s;\theta)}\nabla_{\theta}\mu(s;\theta)ds\quad\text{(by chain rule)}\\ &= E_{s\sim\rho_{\mu}}[\nabla_{a}Q(s, a)|_{a=\mu(s;\theta)}\nabla_{\theta}\mu(s;\theta)] \end{aligned}$$Link to original

Deep Deterministic Policy Gradient

Definition

Deep Deterministic Policy Gradient (DDPG) is an Actor-Critic Method based on DPG that learns deterministic policies to handle continuous action space by adapting DQN architecture such as experience replay and target network.

Due to the determinacy of the policy of DDPG, extra noise is necessary for exploration. The exploration policy is constructed by the sum of the determinant action and a noise process. $a_t=\mu (s_t;\theta )+{\mathcal{N}}_t$ where $\mathcal{N}:=({\mathcal{N}}_t)$ is a noise process.

The target network updating in DQN is substituted by soft (gradual) updating.

\hat{\phi} &\leftarrow \lambda\phi + (1-\lambda)\hat{\phi}\\ \hat{\theta} &\leftarrow \lambda\theta + (1-\lambda)\hat{\theta} \end{aligned}$$ ## Actor (Policy Gradient Update) $$J(\theta) = E_{s\sim \rho_{\mu}}[Q(s, a; \phi)]\Big|_{a = \mu(s;\theta)}$$ $$\Delta\theta = \nabla_{a}Q(s, a;\phi)|_{a=\mu(s;\theta)}\nabla_{\theta}\mu(s;\theta)$$ Where: - $\phi$: behavior critic network. - $\theta$: behavior actor network. ## Critic (Value Network Update) $$L(\phi) = E_{s\sim \rho_{\mu}}[r + \gamma \hat{Q}(s', \hat{\mu}(s';\hat{\theta}); \hat{\phi}) - Q(s, a; \phi)]^{2}\Big|_{a = \mu(s;\theta)}$$ $$\Delta\phi = (r + \gamma \hat{Q}(s', \hat{\mu}(s';\hat{\theta}); \hat{\phi}) - Q(s, a; \phi))\nabla_{\phi}Q(s, a; \phi)$$ Where: - $\phi$: behavior critic network. - $\theta$: behavior actor network. - $\hat{\phi}$: target critic network. - $\hat{\theta}$: target actor network. # Algorithm 1. Initialize critic network $Q(s, a; \phi)$ and actor network $\mu(s; \phi)$ randomly, target networks $\hat{Q}, \hat{\mu}$ with weights $\hat{\phi} = \phi, \hat{\theta} = \theta$, and the replay buffer $\mathcal{R}$ to max size $N$. 3. Repeat for each episode: 1. Initialize state $s_{0}$ and a random noise process $\mathcal{N}$. 2. Repeat for each step of an episode until terminal, $t=0, 1, \dots, T-1$ : 1. Select an action $a_{t} = \mu(s_{t}; \theta) + \mathcal{N}_{t}$. 2. Take the action $a_{t}$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$. 3. Store transition $(s_{t}, a_{t}, r_{t+1}, s_{t+1})$ in the replay buffer $\mathcal{R}$. 4. Sample random minibatch of $B$ transitions $(s_{i}, a_{i}, r_{i+1}, s_{i+1})$ from $\mathcal{R}$. 5. $y_{i} \leftarrow r_{i+1} + \gamma \hat{Q}(s_{i+1}, \hat{\mu}(s_{i+1};\hat{\theta}); \hat{\phi})$. 6. Update critic network by minimizing the loss $L = \cfrac{1}{B}\sum\limits_{i}(y_{i} - Q(s_{i}, a_{i}; \phi))^{2}$. 7. Update actor network using the [[Deterministic Policy Gradient]] $\nabla_{\theta}J \approx \cfrac{1}{B}\sum\limits_{i}\nabla_{a}Q(s_{i}, a;\phi)|_{a=\mu(s;\theta)}\nabla_{\theta}\mu(s_{i};\theta)$ 8. Update target networks $\hat{\phi} \leftarrow \lambda\phi + (1-\lambda)\hat{\phi}$ $\hat{\theta} \leftarrow \lambda\theta + (1-\lambda)\hat{\theta}$Link to original

TRPO

Trust Region Policy Optimization

Definition

The performance of DDPG does not improve monotonically. TRPO addresses the problem by adopting two concepts: Minorize-Maximization Algorithm and trust region. TRPO updates the policy parameter $\theta$ on a trust region in the policy space, guaranteeing monotonic improvement of the objective function (expected return). Although TRPO has achieved high performance, its implementation is very complex so being not practical.

TRPO starts from the maximization problem of expected return $\eta (\pi ):=E_{\tau }[\sum _{t=0}^{\infty }{\gamma }^t(s_t)]$

The original problem is approximated multiple times to find a surrogate function and be solved by MM Algorithm. The surrogate function satisfying the trust region constraint is found using the conservative policy iteration update. $\eta (\pi )\ge L_{{\pi }_{\text{old}}}(\pi )-\frac{4ϵ\gamma }{(1-\gamma {)}^2}{\max }_s{D}_{KL}({\pi }_{{\theta }_{\text{old}}}(\cdot |s)||{\pi }_{\theta }(\cdot |s))$ where $L_{{\pi }_{\text{old}}}(\pi )=\eta (\pi )+\sum _s{\rho }_{{\pi }_{\text{old}}}(s)\sum _a\pi (a|s)A_{{\pi }_{\text{old}}}(s,a)$ is a local approximation of $\eta (\pi )$, and ${\rho }_{\pi }(s)$ is a State Visitation Frequency.

The KL penalized optimization problem is transformed to a constrained optimization problem by Duality. ${\max }_{\theta }{L}_{{\pi }_{{\theta }_{\text{old}}}}({\pi }_{\theta })\text{subject to}{\max }_s{D}_{KL}({\pi }_{{\theta }_{\text{old}}}(\cdot |s)||{\pi }_{\theta }(\cdot |s))\le \delta$

By approximations, the final optimization problem is $E_{s\sim {\rho }_{{\theta }_{\text{old}}},a\sim {\pi }_{{\theta }_{\text{old}}}}\left[\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }_{\text{old}}}(a|s)}{A}_{{\theta }_{\text{old}}}(s,a)\right]\text{subject to }{E}_{s\sim {\rho }_{{\theta }_{\text{old}}}}[D_{KL}({\pi }_{{\theta }_{\text{old}}}(\cdot |s)||{\pi }_{\theta }(\cdot |s))]\le \delta$

The optimization problem is solved by the natural policy gradient and check the monotonic improvement with Backtracking Line Search $\theta ={\theta }_{\text{old}}+\sqrt{\frac{2\delta }{g^{⊺}{F}^{-1}g}}{F}^{-1}g$ where $g={\nabla }_{\theta }{L}_{{\theta }_{\text{old}}}(\theta ){|}_{\theta ={\theta }_{\text{old}}}={\nabla }_{\theta }\left(\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }_{\text{old}}}(a|s)}{A}_{{\theta }_{\text{old}}}(s,a)\right){|}_{\theta ={\theta }_{\text{old}}}$ is a policy gradient, $F$ is the Fisher Information Metric, and $\delta$ is the constraint threshold.

TRPO is performed by repeating 3 steps in each iteration

1. Collect trajectories on ${\pi }_{\text{old}}$, and update $Q$-values.
2. By averaging over samples, construct the estimated objective and constraint.
3. Approximately solve the constrained optimization by natural policy gradient and Backtracking Line Search to update the policy parameter $\theta$.

Algorithm

1. Initialize policy parameters ${\theta }_0$.
2. For $k=0,1,\dots ,K$:
   1. Collect a set of trajectories under current policy ${\pi }_k=\pi ({\theta }_k)$.
   2. Compute advantages $A^{{\pi }_k}(s,a)$ using an advantage estimation algorithm.
   3. Compute policy gradient $g_k$ and Fisher Information Metric $F_k$.
   4. Compute natural gradient $x_k\approx F_k^{-1}{g}_k$.
   5. Estimate proposed step ${\Delta }_k\leftarrow \sqrt{\frac{2\delta }{x_k^{⊺}{F}_k{x}_k}}{x}_k$
   6. Perform Backtracking Line Search to obtain final update: 2. Find minimum $j\in {\mathbb{Z}}_0^{+}$ such that the KL constraint is satisfied. $\underset{j}{\min }j\in {\mathbb{Z}}_0^{+}\text{such that}{D}_{KL}({\pi }_{{\theta }_k}(\cdot |s)||{\pi }_{{\theta }_k+{\alpha }^j{\Delta }_k}(\cdot |s))\le \delta$
   7. Update the policy ${\theta }_{k+1}\leftarrow {\theta }_k+{\alpha }^j{\Delta }_k$

Link to original

MM Algorithm

Definition

The MM algorithm is an iterative optimization method which exploits the convexity of a function in order to find its maxima or minima. The MM stands for Majorize-Minimization or Minorize-Maximization, depending on whether the desired optimization is a minimization or a maximization.

The MM algorithm works by finding a surrogate function that minorizes or majorizes the objective function. Optimizing the surrogate function will monotonically improve the value of the objective function.

Algorithm

Consider Minorize-Maximization algorithm for a maximization problem of a function $f(\theta )$.

1. Find a surrogate function $g(\theta |{\theta }_m)$ (minorized $f(\theta )$) satisfying:
   • $\forall \theta ,g(\theta |{\theta }_m)\le f(\theta )$
   • $g(\theta |{\theta }_m)=f({\theta }_m)$
2. Find a point maximizes the surrogate function ${\theta }_{m+1}=\underset{\theta }{\mathrm{argmax}}g(\theta |{\theta }_m)$ Then, $f({\theta }_m)=g({\theta }_m|{\theta }_m)\le g({\theta }_{m+1}|{\theta }_m)\le f({\theta }_{m+1})$
3. Use the maximum point ${\theta }_{m+1}$ as the next point.
4. Re-evaluate the surrogate function $g(\theta |{\theta }_{m+1})$ at the new point ${\theta }_{m+1}$ and repeat Iteration until convergence to a (local) maximum.

Link to original

Natural Gradient

Definition

The natural gradient is an optimization method that takes into account the geometry of the parameter space when updating parameters. Unlike the standard gradient, which points in the direction of the steepest ascent in the Euclidean Space of parameters, the natural gradient points in the direction of the steepest ascent in the space of probability Distribution induced by the parameters.

${\tilde{\nabla }}_{\theta }J(\theta )=F(\theta {)}^{-1}{\nabla }_{\theta }J(\theta )$ The natural gradient uses the Fisher Information matrix $F(\theta )$ to define a Metric on the parameter space (Fisher Information Metric). It can be interpreted as the steepest ascent direction in the space of probability distributions, as measured by the KL-Divergence. Instead of taking a step that maximizes the change in the objective function $J$ in the Euclidean space of parameters, the natural gradient takes a step that maximizes the change in $J$ while keeping the change in the probability distribution, as measured by KL divergence, relatively small.

Link to original

PPO

Proximal Policy Optimization

Definition

Although TRPO has achieved monotonic improvement, its implementation and computation are complicated due to KL constraint. PPO removed the KL constraint term in the optimization problem of TRPO by introducing the clipped surrogate objective, which provides penalty when the policy update is too high.

PPO apply clipping to the policy ratio $\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }_{\text{old}}}(a|s)}$. The cliiped surrogate function is defined as $L^{CLIP}(\theta )=E[\min (r(\theta )A_{{\theta }_{\text{old}}}(s,a),\mathrm{clip}(r(\theta ),1-ϵ,1+ϵ)A_{{\theta }_{\text{old}}}(s,a))]$ where $r(\theta )=\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }_{\text{old}}}(a|s)}$ is the policy ratio, and $ϵ$ is a hyperparameter that determines the clipping range.

$L^{CLIP}(\theta )$ satisfies $L^{CLIP}(\theta )\le L^{TRPO}(\theta )$, so we can still use MM Algorithm.

To minimize the value function loss simultaneously and to encourage exploration, PPO appends additional terms to the objective function. $L^{CLIP+VF+S}(\theta )=L^{CLIP}-c_1{L}^{VF}(\theta )+c_{2}S[{\pi }_{\theta }](s)$ Where

• $L^{CLIP}(\theta )$ is the clipped surrogate objective
• $L^{VF}(\theta )=(V_{\text{target}}-V_{\theta }(s){)}^2$ is the value function loss
• $S[{\pi }_{\theta }](s)=-\sum _a{\pi }_{\theta }(a|s)\ln {\pi }_{\theta }(a|s)$ is the Entropy bonus terms.
• $c_1,c_2$ are hyperparameter that controls the weight of the losses.

Link to original

Distributional RL

Distributional Reinforcement Learning

Definition

Distributional RL treats the Reward $R(x,a)$ as a Random Variable, and uses random return $Z^{\pi }(x,a)=\sum _{t\ge 0}{\gamma }^{t}R(x_t,a_t)$, called an action-value distribution, instead of the Action-Value Function.

Algorithms

C51

QR-DQN

IQN

Link to original

Distributional Bellman Equation

Definition

Distributional Bellman Equation

$Z^{\pi }(x,a)\stackrel{D}{=}R(x,a)+\gamma Z^{\pi }(X^{\prime },A^{\prime })$

Distributional Bellman Operator

$({\mathcal{T}}^{\pi }Z)(x,a)\stackrel{D}{:=}R(x,a)+\gamma Z(X^{\prime },A^{\prime })$

The distributional Bellman equation can be written with the operator as $Z^{\pi }={\mathcal{T}}^{\pi }{Z}^{\pi }$

Link to original

Distributional Bellman Optimality Equation

Definition

Distributional Bellman Optimality Equation

$Z^{\ast }(x,a)\stackrel{D}{=}R(x,a)+\gamma Z^{\ast }(X^{\prime },\underset{a^{\prime }}{\mathrm{argmax}}E[Z^{\ast }(X^{\prime },a^{\prime })])$

Distributional Bellman Optimality Operator

$\mathcal{T}Z(x,a)\stackrel{D}{:=}R(x,a)+\gamma Z(X^{\prime },\underset{a^{\prime }}{\mathrm{argmax}}E[Z(X^{\prime },a^{\prime })])$

The distributional Bellman optimality equation can be written with the operator as $Z^{\ast }={\mathcal{T}}^{\pi }{Z}^{\ast }$

Link to original

Distributional Policy Iteration

Definition

Policy Evaluation

Compute $Z^{\pi }$ from the current policy $\pi$.

Distributional Bellman operator ${\mathcal{T}}^{\pi }$ for a fixed policy $\pi$ is a Contraction Map in a maximal form of Wasserstein Metric. ${\overline{W}}_p(Z_1,Z_2)={\sup }_{x,a}{W}_p(Z_1(x,a),Z_2(x,a))$

Thus, the iteration $Z\leftarrow {\mathcal{T}}^{\pi }Z$ converges to a unique fixed point $Z^{\pi }$ (by Contraction Lemma).

Control (Policy Improvement)

Seek a greedy policy $\pi$ based on the $Z^{\ast }$, which maximizes the expectation of $Z^{\ast }$.

Distributional Bellman optimality operator $\mathcal{T}$ is not a Contraction Map, not even continuous in any Metric, causing the distributional instability. To overcome the problem, discrete action-value distributions are used to approximate the true distribution $Z$.

Link to original

C51

C51

Definition

The C51 algorithm is a Distributional Reinforcement Learning algorithm that approximates the distribution of the random return a using discretized distribution.

Architecture

The range of possible returns is divided into a fixed support of $N$-equally spaced bins $\{z_i{\}}_{i=0}^{N-1}$, where $z_i=R_{\text{min}}+i\Delta z$ and $\Delta z=\frac{R_{\text{max}}-R_{\text{min}}}{N-1}$. $R_{\text{min}}$ and $R_{\text{max}}$ are the minimum and maximum possible return values, respectively. In the C51 algorithm, the support determined once at the beginning and remains fixed throughout the entire learning process.

For each state-action pair $(s,a)$, the algorithm estimates the probabilities $\{p_i(s,a)\}$ that the return will fall into each $i$-th bin. The probabilities are estimated by a neural network, which takes the state $s$ as input and outputs a vector of probabilities $\{p_i(s,a)\}$ for each state-possible action pair $(s,a),\forall a\in \mathcal{A}(s)$. The Softmax Function ensures the properties of the probability of the output for each state-action pair. $p_i(s,a;\theta )=\frac{e^{{\theta }_i(s,a)}}{{\sum }_{j=0}^{N-1}{e}^{{\theta }_j(s,a)}}$ where ${\theta }_i(s,a)$ are the raw outputs (logits) of the network for the $i$-th atom and action $a$, and $\theta$ represents the network’s parameters.

The discrete distribution $Z_{\theta }$ over the fixed support $\{z_i{\}}_{i=0}^{N-1}$ is constructed as $Z_{\theta }(s,a)=\sum _{i=0}^{N-1}{p}_i(s,a){\delta }_{z_i}$ where ${\delta }_x$ is a Dirac’s delta function at $x$.

Projection

In a policy evaluation process, discrete distributions have a problem: $\mathcal{T}{Z}_{\theta }$ and $Z_{\theta }$ have disjoint supports. Though, Wasserstein Metric in the original setup is robust to this issue, but in practice, KL-Divergence is used instead due to the distributional instability and differentiability. Therefore, the problem still matters.

The disjoint support problem is solved by projection.

1. Compute the distributional Bellman update: ${\hat{Z}}_{\theta }\leftarrow r+\gamma Z_{\theta }(s^{\prime },a^{\ast })$ where $a^{\ast }=\underset{a}{\mathrm{argmax}}Q(s^{\prime },a)$
2. Distribute the computed probability mass ${\hat{Z}}_{\theta }$ to the neighboring bins in the support $\{z_i{\}}_{i=0}^{N-1}$ proportionally to the distance from each original point: $(\Phi \mathcal{T}{Z}_{\theta })(s,a)$, where $\Phi$ is the projection operator.

Loss Function

C51 uses the KL-Divergence as a loss function. $L_{s,a}(\theta )=D_{KL}(\Phi \hat{\mathcal{T}}{Z}_{\hat{\theta }}(s,a)||Z_{\theta }(s,a)))$ where $\theta$ and $\hat{\theta }$ are the parameters for behavior and target networks, respectively.

The loss function can be simplified to the Cross-Entropy Loss. $L(\theta )=-\sum _{i=0}^{N-1}(\Phi \hat{\mathcal{T}}Z(s,a;\hat{\theta }){)}_i\ln p_i(s,a;\theta )$

Algorithm

1. Initialize behavior network $Q$ and target network $\hat{Q}$ with random weights $\theta$, and the replay buffer $\mathcal{R}$ to max size $N$.
2. Repeat for each episode:
   1. Initialize sequence $s_0$.
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. With probability $ϵ$, select a random action $a_t$ otherwise select $a_t=\underset{a}{\mathrm{argmax}}Q(s_t,a;\theta )$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. Store transition $(s_t,a_t,r_{t+1},s_{t+1})$ in the replay buffer $\mathcal{R}$.
      4. Sample a random transition $(s_t,a_t,r_{t+1},s_{t+1})$ from $\mathcal{R}$.
      5. Compute $Q(s_{t+1},a)=\sum _{i=0}^{N-1}{z}_i{p}_i(s_{t+1},\alpha ;\hat{\theta })$ and select a greedy action $a^{\ast }=\underset{a}{\mathrm{argmax}}Q(s_{t+1},a)$.
      6. Perform Gradient Descent on the loss $L(\theta )=-\sum _{i=0}^{N-1}(\Phi \hat{\mathcal{T}}Z(s_{t+1},a^{\ast };\hat{\theta }){)}_i\ln p_i(s_t,a_t;\theta )$.
      7. Update the target network parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      8. Update $s_t\leftarrow s_{t+1}$.

Link to original

QR-DQN

QR-DQN

Definition

The Quantile-Regression DQN (QR-DQN) algorithm is a Distributional Reinforcement Learning algorithm that approximates the distribution of random return using quantile regression.

Architecture

QR-DQN estimates a set of $N$ quantiles $\{{\hat{\tau }}_i{\}}_{i=1}^N$ of return distribution, where ${\hat{\tau }}_i=\frac{2i-1}{2N}$ represents the midpoint of $i$-th quantile interval. This can be seen as adjusting the location of the supports of a uniform probability mass to approximate the desired quantile distribution.

The quantile distribution $Z$ with uniform probability $\frac{1}{N}$ is constructed as $Z(s,a)=\frac{1}{N}\sum _{i=1}^N(s,a){\delta }_{z_i(s,a)}$ where ${\delta }_x$ is a Dirac’s delta function at $x$, and $\{z_i(s,a)\}$ are the outputs of the network, representing the estimated quantile values. These values are obtained by applying the inverse CDF of the return distribution to the quantile midpoints $z_i(s,a)=F_Z^{-1}({\hat{\tau }}_i)$.

Using the estimated quantile values as a support minimizes the Wasserstein Distance between the true return distribution and the estimated distribution.

Quantile Regression

Given data set $\{x_j\}$, a $\tau$-quantile $q_{\tau }$ minimizes the loss $\sum _{j=1}^N{\rho }_{\tau }(x_j-q_{\tau })$, where ${\rho }_{\tau }(x)=x(\tau -1(x<0))$ is a quantile loss function.

The quantile values are estimated by minimizing the quantile Huber loss function. Given a transition $(s,a,r,s^{\prime })$, the loss is defined as $L(\theta )=\sum _{i=1}^N{E}_j[{\rho }_{{\hat{\tau }}_i}^{\kappa }(\mathcal{T}{z}_j-z_i(s,a))]=\frac{1}{N}\sum _{i=1}^N\sum _{j=1}^N{\rho }_{{\hat{\tau }}_i}^{\kappa }(\mathcal{T}{z}_j-z_i(s,a))$ Where:

• $\mathcal{T}{z}_j=r+\gamma z_j(s^{\prime },a^{\ast })$ and $a^{\ast }=\underset{a}{\mathrm{argmax}}Q(s^{\prime },a)$.
• ${\rho }_{\tau }^{\kappa }(x)=L_{\kappa }(x)(\tau -1(x<0))$ where $L_{\kappa }(x)$ is Huber Loss.

Algorithm

1. Initialize behavior network $Q$ and target network $\hat{Q}$ with random weights $\theta$, and the sample size $N$.
2. Repeat for each episode:
   1. Initialize sequence $s_0$.
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. With probability $ϵ$, select a random action $a_t$ otherwise select $a_t=\underset{a}{\mathrm{argmax}}Q(s_t,a;\theta )$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. Store transition $(s_t,a_t,r_{t+1},s_{t+1})$ in the replay buffer $\mathcal{R}$.
      4. Sample a random transition $(s_t,a_t,r_{t+1},s_{t+1})$ from $\mathcal{R}$.
      5. Select a greedy action $a^{\ast }=\underset{a}{\mathrm{argmax}}Q(s_{t+1},a)=\underset{a}{\mathrm{argmax}}\frac{1}{N}\sum _{i=0}^{N-1}{z}_i(s_{t+1},\alpha ;\hat{\theta })$
      6. Compute the target quantile values $\mathcal{T}{z}_j(s_{t+1},a^{\ast };\hat{\theta })=r_{t+1}+\gamma z_j(s_{t+1},a^{\ast })$.
      7. Perform Gradient Descent on the loss $L(\theta )=\sum _{i=1}^N{E}_j[{\rho }_{{\hat{\tau }}_i}^{\kappa }(\mathcal{T}{z}_j(s_{t+1},a^{\ast };\hat{\theta })-z_i(s_t,a_t;\theta ))]$.
      8. Update the target network parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      9. Update $s_t\leftarrow s_{t+1}$.

Link to original

IQN

IQN

Definition

The Implicit Quantile Network (IQN) algorithm is a Distributional Reinforcement Learning algorithm that implicitly estimates the quantiles of a return distribution by learning a function that maps a quantile fraction to the corresponding quantile value.

Architecture

IQN estimates the quantile value $Z(s,a,\tau )=F_Z^{-1}(\tau )$ for a given state $s$, action $a$, and a quantile fraction $\tau \in [0,1]$. The output is the estimated quantile value corresponding to that fraction $\tau$.

The input state $s$ processed by the encoder layers of neural network to produce a state embedding vector $\varphi (s)$.

The quantile fraction $\tau$ is embedded into a higher-dimensional vector $\psi (\tau )$ using a set of basis functions, where whose dimension is the same as the one of the state-feature $\varphi (s)$. ${\psi }_i(\tau )=\cos (i\pi \tau )$ The two embeddings: state embedding and quantile-embedding, are combined using Hadamard Product $\varphi (s)\odot \psi (\tau )$.

The combined embedding is fed into the further layers $f_{\theta }$ to predict the quantile value $Z(s,a,\tau )$

In summary, the quantile value for a given state is estimated by $Z(s,a,\tau ;\theta )\approx f_{\theta }(\varphi (s),\psi (\tau ))$

By sampling different quantile fractions $\tau$, IQN can approximate the entire return distribution. The expectation of the return can be approximated by averaging the estimated quantile values over the sampled quantile fractions $Q(s,a;\theta )\approx \frac{1}{N}\sum _{i=1}^{N}Z(s,a,{\tau }_i;\theta )$ where $\{{\tau }_i{\}}_{i=1}^N$ are sampled quantile fractions.

Loss Function

IQN uses a quantile Huber loss function, similar to QR-DQN. Given a transition $(s,a,r,s^{\prime })$, the loss is defined as $L(\theta )=\sum _{i=1}^N{E}_{{\tau }^{\prime }}[{\rho }_{{\hat{\tau }}_i}^{\kappa }(\mathcal{T}{Z}_{{\tau }_j^{\prime }}-Z(s,a,{\tau }_i;\theta ))]$ Where:

• $\{{\hat{\tau }}_i{\}}_{i=1}^N$ and $\{{\tau }_j^{\prime }{\}}_{j=1}^{N^{\prime }}$ are quantile fractions for the current state-action pair and next state, respectively.
• $\mathcal{T}{Z}_{{\tau }_j^{\prime }}=r+\gamma Z(s^{\prime },a^{\ast },{\tau }_j^{\prime };\hat{\theta })$ and $a^{\ast }=\underset{a}{\mathrm{argmax}}\frac{1}{N^{\prime }}\sum _{j=1}^{N^{\prime }}Z(s^{\prime },a,{\tau }_j^{\prime };\hat{\theta })\approx \underset{a}{\mathrm{argmax}}Q(s^{\prime },a;\hat{\theta })$.
• ${\rho }_{\tau }^{\kappa }(x)=L_{\kappa }(x)(\tau -1(x<0))$ where $L_{\kappa }(x)$ is Huber Loss.

Risk-Sensitive Policy

$\beta :[0,1]\to [0,1]$ The IQN has information about the entire distribution by estimating the distribution of returns. This property makes it suitable for implementing risk-sensitive policies, allowing for decision-making considering risk. Risk-sensitive policies focus on not just the expected return, but the variability or uncertainty in the returns. IQN makes it feasible by providing estimated quantiles of the return distribution.

The function $\beta :[0,1]\to [0,1]$ is used to define a distortion risk measure that focuses on specific parts of the return distribution. By applying $\beta$ to the quantile fraction $\tau$, we can re-wright each outcome or change the sampling distribution.

These are examples of distortion measures:

• Cumulative Probability Weighting Parametrization (CPW): $\mathrm{CPW}(\eta ,\tau )=\frac{{\tau }^{\eta }}{({\tau }^{\eta }+(1-\tau {)}^{\eta }{)}^{1/\eta }}$
• Wang: $\mathrm{Wang}(\eta ,\tau )=\Phi ({\Phi }^{-1}(\tau )+\eta )$ where $\Phi$ is the CDF for standard normal distribution.
• Power Formula: $\mathrm{Pow}(\eta ,\tau )=\{\begin{array}{ll}{\tau }^{1/(1+|\eta |)}& \eta \ge 0\\ 1-(1-\tau {)}^{1/(1+|\eta |)}& \eta <0\end{array}$
• Conditional Value at Risk (CVaR): $\mathrm{CVaR}(\eta ,\tau )=\eta \tau$

Algorithm

1. Initialize behavior quantile network $Z$ and target quantile network $\hat{Z}$ with random weights $\theta$, the sample sizes $K,N,N^{\prime }$, and a distortion measure $\beta$.
2. Repeat for each episode:
   1. Initialize sequence $s_0$.
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. Sample $K$ quantile fractions $\{{\tilde{\tau }}_k\sim \beta (\cdot ){\}}_{k=1}^K$ under the distortion measure $\beta$, | and select a greedy action $a_t=\underset{a}{\mathrm{argmax}}\frac{1}{K}\sum _{k=1}^{K}Z(s_t,a,{\tilde{\tau }}_k;\theta )\approx \underset{a}{\mathrm{argmax}}Q(s_t,a;\theta )$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. Store transition $(s_t,a_t,r_{t+1},s_{t+1})$ in the replay buffer $\mathcal{R}$.
      4. Sample a random transition $(s_t,a_t,r_{t+1},s_{t+1})$ from $\mathcal{R}$.
      5. Sample $N^{\prime }$ quantile fractions $\{{\tau }_j^{\prime }\sim U(0,1){\}}_{j=1}^{N^{\prime }}$ for the next state and select a greedy action $a^{\ast }=\underset{a}{\mathrm{argmax}}\frac{1}{N^{\prime }}\sum _{j=1}^{N^{\prime }}Z(s_{t+1},a,{\tau }_j^{\prime };\hat{\theta })\approx \underset{a}{\mathrm{argmax}}Q(s^{\prime },a;\hat{\theta })$.
      6. Compute the target quantile values $\mathcal{T}{Z}_{{\tau }_j^{\prime }}=r_{t+1}+\gamma Z(s_{t+1},a^{\ast },{\tau }_j^{\prime };\hat{\theta })$.
      7. Perform Gradient Descent on the loss $L(\theta )=\sum _{i=1}^N\sum _{j=1}^{N^{\prime }}{\rho }_{{\hat{\tau }}_i}^{\kappa }(\mathcal{T}{Z}_{{\tau }_j^{\prime }}-Z(s,a,{\hat{\tau }}_i;\theta ))$.
      8. Update the target network $\hat{Z}$ parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      9. Update $s_t\leftarrow s_{t+1}$.

Link to original