Reinforcement Learning: Q-Learning & Deep Q-Learning

• These notes present a Reinforcement Learning algorithm, namely Q-Learning
• Having a Probability, Stochastics and Machine Learning foundation is recommended before reading.
• It may be useful to be familiar with Dynamic Programming in the context of Reinforcement Learning.

Introduction

The goal of Q-Learning is to learn a certain measure of quality of actions given states. This measure of quality represents the long-term expected reward we can get by taking a certain action at a specific state. The higher the expected reward, the better the quality of the action.

Framework

We have an agent and an environment which interact with each-other in discrete time steps. At time $t$, the agent observes the environment's state $s_t\in \mathcal{S}$, and performs action $a_t\in \mathcal{A}(s_t)$. The agent gets a reward $r_t\in \mathbb{R}$ from performing this action, and the environement changes to state $s_{t+1}\in \mathcal{S}$.

The state transition follows a distribution $p(s_{t+1}\mid s_t,a_t)$ $\forall s_{t+1}\in \mathcal{S}$, and we assume to have the markov property $p(s_{t+1}\mid s_0,a_0,...,s_t,a_t)=p(s_{t+1}\mid s_t,a_t)$.

We assume that we don't know the environment's dynamics (model free), so we don't know the state transition $p(s_{t+1}\mid s_t,a_t)$ $\forall s_{t+1}\in \mathcal{S}$. In other words, from $s_t,a_t$ we cannot infer anything on $s_{t+1}$.

We note $\mathcal{S}$ the observable state space, $\mathcal{A}$ the action space. $\mathcal{A}(s)$ is the action space when the state of the environment is $s$, and $\mathcal{A}(s)\subseteq \mathcal{A}$.

$R:\mathcal{S}\times \mathcal{A}\to \mathbb{R}$ is the reward function, and $r_t=R(s_t,a_t)$. The notation $r_t$ will be used to denote a random variable that depends on the event $(s_t,a_t)$, and $R(s_t,a_t)$ will be used when we know its value (i.e. when we know $s_t$ and $a_t$).

We define a policy $\pi$ to be a strategy for the agent. We model it as a function $\pi :\mathcal{A}\times \mathcal{S}\to [0,1]$ such that for every $s\in \mathcal{S}$, ${\sum }_{a\in \mathcal{A}(s)}=1$, so that it defines, for every choice of $s\in \mathcal{S}$ a probability distribution over $\mathcal{A}(s)$, and we denote it with $\pi (a\mid s)$.

The notation ${\mathbb{E}}_{\pi }[...]$ means that we sample all actions according to $\pi$, and all states are sampled according to state transition.

Defining The Goal

Let's start with what we want to achieve. From a state $s$, we want to maximize the expected cumulative reward of our course of action. The expected cumulative reward is what we should obtain on average if we start at a state $s$ and follow our policy to perform actions. The expected cumulative reward is defined as $\mathbb{E}\left[{\sum }_{i=0}^{\infty }{r}_{t+i}\mid s_t=s\right]$ so our goal is:

$$\underset{\pi }{\max }{\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{r}_{t+i}\mid s_t=s\right]$$

But summing infinitely many rewards can be infinite. So we slightly change our goal to circumvent this. We prioritize the impact of the most recent rewards over the ones that come later, by introducting a discount factor $\gamma \in ]0,1[$. We thus define the discounted cumulative reward as being $G_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{r+2}+...={\sum }_{i=0}^{\infty }{\gamma }^i{r}_{t+i}$. The closer $\gamma$ is to 1, the more importance we give to long-term rewards, whereas when $\gamma$ is close to 0, we prioritize short-term rewards. This can be important if for example we are in a game where there are multiple short-term goals that don't end the game but a single long-term goal that ends the game.

The V-Function

We can now define the expected discounted cumulative reward when we start at state $s$ and follow policy $\pi$, otherwise known as the State-Value Function (V-function):

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid s_t=s]={\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+i}\mid s_t=s\right]$$

And finally we can state our ultimate goal:

$$\underset{\pi }{\max }{V}^{\pi }(s)\forall s\in \mathcal{S}\text{\hspace{1em}(1)}$$

But, sticking to our assumptions, the V-function is not sufficient. Let's say we want to use the V-function to choose an action based on $s_t$. Then we would choose the action that maximizes the next state's V-function, taking into account the reward obtained from this transition. We would want something similar to

$$\arg \underset{a_t\in \mathcal{A}(s_t)}{\max }R(s_t,a_t)+\gamma {\mathbb{E}}_{p(s_{t+1}\mid s_t,a_t)}[V^{\pi }(s_{t+1})]$$

The fact that we need to get the next state distribution (i.e. information on the state transition) goes in conflict with our model-free assumption, so the V-function cannot directly be used as a means to choose an action based on the state $s_t$ we're in.

The Q-Function

Definition

Let's introduce a new function, called the Action-Value Function (or Q-function), which is similar to the State-Value Function but takes into account the action that has been chosen.

$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t\mid s_t=s,a_t=a]={\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+i}\mid s_t=s,a_t=a\right]$$

The intuition of this function is that it gives a measure of the quality of the action we take at a certain state.

Link To Our Goal

Let's link the Q-function to the V-function.

$$\begin{array}{rl}{Q}^{\pi }(s,a)& ={\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+i}\mid s_t=s,a_t=a\right]\\ & =\sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a){\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+i}\mid s_t=s,a_t=a,s_{t+1}=s^{\prime }\right]\\ & =\sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a)\left(R(s_t,a_t)+\gamma {\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_{t+1}=s^{\prime }\right]\right)\\ & =R(s_t,a_t)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a){\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_{t+1}=s^{\prime }\right]\end{array}$$

$$\Rightarrow Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }\mid s,a)V^{\pi }(s^{\prime })\text{\hspace{1em}(∗)}$$

And the other way around is obtained by summing the conditional expectations on $a_t$:

$$\begin{array}{rl}{V}^{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t\mid s_t=s]\\ & =\sum _{a\in \mathcal{A}(s_t)}\pi (a_t=a\mid s_t=s){\mathbb{E}}_{\pi }[G_t\mid s_t=s,a_t=a]\end{array}$$

$$\Rightarrow V^{\pi }(s)=\sum _{a\in \mathcal{A}(s)}\pi (a\mid s)Q^{\pi }(s,a)\text{\hspace{1em}(∗∗)}$$

The above equation is important. It describes the relationship between two fundamental value functions in Reinforcement Learning. It is valid for any policy.

Policy Ordering

Let's define what an optimal policy ${\pi }^{\ast }$ is by first defining a partial ordering between policies:
Let ${\pi }_1$, ${\pi }_2$ be two policies. Then,

$${\pi }_1\ge {\pi }_2\iff \forall s\in \mathcal{S}{V}^{{\pi }_1}(s)\ge V^{{\pi }_2}(s)$$

Some policies might not be comparable, for example if there exists $s_1,s_2$ in $\mathcal{S}$ such that $V^{{\pi }_1}(s_1)>V^{{\pi }_2}(s_1)$ but $V^{{\pi }_1}(s_2)<V^{{\pi }_2}(s_2)$.
An optimal policy ${\pi }^{\ast }$ is one that is comparable with any other policy $\pi$, and such that ${\pi }^{\ast }\ge \pi$.

A result that we won't prove here but that we'll be using is that, in our setting, ${\pi }^{\ast }$ always exists, and moreover there alway exists a deterministic policy that is optimal. Also note that there can be multiple optimal policies that give the same optimal value, i.e. ${\pi }^{\ast }$ may not be unique.

We can rewrite our ultimate goal (1) as being $V^{\ast }(s)=V^{{\pi }^{\ast }}(s)={\max }_{\pi }{V}^{\pi }(s)$. It is the optimal V-function.
Similarly, the optimal Q-function is $Q^{\ast }(s,a)=Q^{{\pi }^{\ast }}(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$.

Finding The Optimal V-Function Is Equivalent To Finding The Optimal Q-Function

We will now derive an important result, which says that to obtain the values of the optimal V-function, we can concentrate on getting the values of the optimal Q-function. To help derive this important result, we first give the following lemma.

Policy Improvement Lemma

Lemma: If $\exists \bar{s}\in \mathcal{S}$ such that $V^{\pi }(\bar{s})<{\max }_{a\in \mathcal{A}(\bar{s})}{Q}^{\pi }(\bar{s},a)$, then

$$\exists {\pi }^{\prime }s.t.V^{\pi }(s)=V^{{\pi }^{\prime }}(s)\forall s\in \mathcal{S}\setminus \{\bar{s}\}\text{and}{V}^{\pi }(\bar{s})<V^{{\pi }^{\prime }}(\bar{s})$$

Proof.
Let $\bar{a}=\arg {\max }_{a\in \mathcal{A}(\bar{s})}{Q}^{\pi }(\bar{s},a)$.
Let ${\pi }^{\prime }(a\mid s)=\{\begin{array}{ll}\pi (a\mid s),& \text{if}s\ne \bar{s}\\ 1,& \text{if}s=\bar{s}\text{ and }a=\bar{a}\\ 0,& \text{otherwise}\end{array}$

First, $\forall s\in \mathcal{S}\setminus \{\bar{s}\}$ :

• $V^{\pi }(s)=V^{{\pi }^{\prime }}(s)$ because $s\ne \bar{s}$ so ${\pi }^{\prime }(a\mid s)=\pi (a\mid s)$.

Then, when $s=\bar{s}$ :

$$V^{\pi }(\bar{s})=\sum _{a\in \mathcal{A}(\bar{s})}\pi (a\mid \bar{s})Q^{\pi }(\bar{s},a)<\sum _{a\in \mathcal{A}(\bar{s})}{\pi }^{\prime }(a\mid \bar{s})Q^{\pi }(\bar{s},a)$$

because (lemma assumption)

$$\sum _{a\in \mathcal{A}(\bar{s})}{\pi }^{\prime }(a\mid \bar{s})Q^{\pi }(\bar{s},a)=Q^{\pi }(\bar{s},\bar{a})=\underset{a\in \mathcal{A}(\bar{s})}{\max }{Q}^{\pi }(\bar{s},a)>V^{\pi }(\bar{s})$$

Without loss of generality, let $t$ be the current timestep.
In what follows, we use multiple times the links derived between the Q-function and the V-function.

$$\begin{array}{rl}{V}^{\pi }(\bar{s})& <\sum _{a\in \mathcal{A}(\bar{s})}{\pi }^{\prime }(a\mid \bar{s})Q^{\pi }(\bar{s},a)\\ & ={\mathbb{E}}_{{\pi }^{\prime }}[Q^{\pi }(s_t,a_t)\mid s_t=\bar{s}]\\ & ={\mathbb{E}}_{{\pi }^{\prime }}[r_t+\gamma {\mathbb{E}}_p[V^{\pi }(s_{t+1})]\mid s_t=\bar{s}]\\ & ={\mathbb{E}}_{{\pi }^{\prime }}[r_t+\gamma V^{\pi }(s_{t+1})\mid s_t=\bar{s}]\text{following our notation}\\ & \le {\mathbb{E}}_{{\pi }^{\prime }}[r_t+\gamma Q^{\pi }(s_{t+1},a_{t+1})\mid s_t=\bar{s}]\end{array}$$

The last inequality is due to the fact that $V^{\pi }(s_{t+1})={\mathbb{E}}_{\pi }[Q^{\pi }(s_{t+1},a_{t+1})]$, and

• if $s_{t+1}\ne \bar{s}$, then ${\mathbb{E}}_{\pi }[Q^{\pi }(s_{t+1},a_{t+1})]={\mathbb{E}}_{{\pi }^{\prime }}[Q^{\pi }(s_{t+1},a_{t+1})]$,
• but if $s_{t+1}=\bar{s}$, then ${\mathbb{E}}_{\pi }[Q^{\pi }(s_{t+1},a_{t+1})]\le {\max }_{a\in \mathcal{A}(s_{t+1})}{Q}^{\pi }(s_{t+1},a)={\mathbb{E}}_{{\pi }^{\prime }}[Q^{\pi }(s_{t+1},a_{t+1})]$.

Thus $V^{\pi }(s_{t+1})\le {\mathbb{E}}_{{\pi }^{\prime }}[Q^{\pi }(s_{t+1},a_{t+1})]$.
Then the expectation is redundant so we can remove it.

Repeating the above reasonning, we obtain

$$\begin{array}{rl}{\mathbb{E}}_{{\pi }^{\prime }}[r_t+\gamma V^{\pi }(s_{t+1})\mid s_t=\bar{s}]& \le {\mathbb{E}}_{{\pi }^{\prime }}[r_t+\gamma Q^{\pi }(s_{t+1},a_{t+1})\mid s_t=\bar{s}]\\ & ={\mathbb{E}}_{{\pi }^{\prime }}[r_t+\gamma r_{t+1}+{\gamma }^2{V}^{\pi }(s_{t+2})\mid s_t=\bar{s}]\\ & \le {\mathbb{E}}_{{\pi }^{\prime }}[r_t+\gamma r_{t+1}+{\gamma }^2{Q}^{\pi }(s_{t+2},a_{t+2})\mid s_t=\bar{s}]\\ & ⋮\\ & \le {\mathbb{E}}_{{\pi }^{\prime }}[G_t\mid s_t=\bar{s}]\\ & =V^{{\pi }^{\prime }}(\bar{s})\end{array}$$

So finally

$$V^{\pi }(\bar{s})<V^{{\pi }^{\prime }}(\bar{s})$$

$$\text{\hspace{1em}□}$$

Now we are ready to state our important result.

Equivalence Theorem

Theorem:

$$\forall s\in \mathcal{S},V^{\ast }(s)=\underset{a\in \mathcal{A}(s)}{\max }{Q}^{\ast }(s,a)$$

Proof. Since $(\ast \ast )$ is valid for any policy, it is valid for an optimal policy. So $V^{\ast }(s)={\sum }_{a\in \mathcal{A}(s)}{\pi }^{\ast }(a\mid s)Q^{\ast }(s,a)$.
Let $\bar{a}=\arg {\max }_{a\in \mathcal{A}(s)}{Q}^{\ast }(s,a)$.
Then

$$\sum _{a\in \mathcal{A}(s)}{\pi }^{\ast }(a\mid s)Q^{\ast }(s,a)\le \sum _{a\in \mathcal{A}(s)}{\pi }^{\ast }(a\mid s)Q^{\ast }(s,\bar{a})=Q^{\ast }(s,\bar{a})=\underset{a\in \mathcal{A}(s)}{\max }{Q}^{\ast }(s,a)$$

Thus $V^{\ast }(s)\le {\max }_{a\in \mathcal{A}(s)}{Q}^{\ast }(s,a)$.

We now prove that $V^{\ast }(s)\ge {\max }_{a\in \mathcal{A}(s)}{Q}^{\ast }(s,a)\forall s\in \mathcal{S}$ by contradiction.
Let's assume that $\exists \bar{s}\in \mathcal{S}:V^{\ast }(\bar{s})<{\max }_{a\in \mathcal{A}(\bar{s})}{Q}^{\ast }(\bar{s},a)$.
By our previous lemma, this means that there exists ${\pi }^{\prime }$ such that $V^{\ast }(\bar{s})<V^{{\pi }^{\prime }}(\bar{s})$, which means ${\pi }^{\ast }$ is not optimal $\Rightarrow$ Contradiction.

$$\text{\hspace{1em}□}$$

This is extremely useful, because we can concentrate on computing the optimal Q-values to obtain the optimal V-function values, which is exactly our ultimate goal $(1)$. So computing the optimal Q-values comes back to achieving our goal.
The whole idea of Q-Learning is learning these optimal Q-values. To put in place our learning framework, we first derive a recursive formula for the optimal Q-function, called the Bellman optimality equation.

Bellman optimality equation for $Q^{\ast }$:

$$Q^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }\mid s,a)\underset{a^{\prime }\in \mathcal{A}(s^{\prime })}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })$$

This is obtained by noting that $(\ast )$ works in particular with ${\pi }^{\ast }$, and by combining it with $V^{\ast }(s)={\max }_{a\in \mathcal{A}(s)}{Q}^{\ast }(s,a)$.

Q-Learning

Let $\tilde{Q}$ be the function obtained from learning $Q^{\ast }$.
The Bellman optimality equation will help us learn $Q^{\ast }(s,a)$ for all $s\in \mathcal{S},a\in \mathcal{A}(s)$ because our learning objective is minimizing the following error measure:

$$B(s_t,a_t,s_{t+1})=\tilde{Q}(s_t,a_t)-\underset{\text{Computed once we can observe}{s}_{t+1}}{\underbrace{(R(s_t,a_t)+\gamma \underset{a\in \mathcal{A}(s_{t+1})}{\max }\tilde{Q}(s_{t+1},a))}}$$

It is the Bellman error, which is simply the difference between the current Q-value when we're at $s_t$ and about to take $a_t$, and the Q-value computed once we observe the next state $s_{t+1}$. Intuitively, the Bellman error is the update to our expected reward when we observe $s_{t+1}$. The part underlined is the RHS of the Bellman optimality equation, but knowing $s^{\prime }=s_{t+1}$.

Q-Learning is an algorithm that repeatedly adjusts $\tilde{Q}$ to minimize the Bellman error. At timestep $t+1$, we sample the tuple $(s_t,a_t,s_{t+1})$ and adjust $\tilde{Q}$ as follows:

$$\tilde{Q}(s_t,a_t)\leftarrow \tilde{Q}(s_t,a_t)-{\alpha }_{t}B(s_t,a_t,s_{t+1})$$

Where ${\alpha }_t$ is a learning rate. In practice ${\alpha }_t$ will be close to 0 and stricly less than 1 to take into account previous updates.

Now we state the theoretical constraints under which Q-Learning converges, which helps motivate implementation choices of Q-Learning in practice. The proof of convergence is not given here, but the paper for the proof can be found in Reference 2.

Constraints For Convergence

Convergence of Q-Learning: Let $t^i(s,a)$ be the timestep of the $i^{\text{th}}$ time that we're in state $s$ and we take action $a$. Let the updates to $\tilde{Q}$ be done as mentioned above. Then, $\tilde{Q}$ converges almost surely towards $Q^{\ast }$ as long as

$$\sum _{i=0}^{\infty }{\alpha }_{t^i(s,a)}=\infty \text{and}\sum _{i=0}^{\infty }{\left[{\alpha }_{t^i(s,a)}\right]}^2<\infty \forall s\in \mathcal{S},a\in \mathcal{A}$$

The convergence is almost surely because we have random variables $s_t,s_{t+1}$ and $a_t$.
This statement reveals 2 constraints:

1. The learning rate for each state-action pair $(s,a)$ must converge towards 0, but not too quickly.
2. Because ${\alpha }_t$ is bounded for all $t$, all state-action pair $(s,a)$ must be visited infinitely often.

Exploration-Exploitation tradeoff

Now the idea could be to apply Machine Learning to learn it: we sample a lot of events to adjust and learn each $\tilde{Q}$ so that it is as close as possible to $Q^{\ast }$. To do this we don’t need a specific policy, we just need enough exploration and (by the convergence constraints) enough iterations to make the values of $\tilde{Q}$ converge towards $Q^{\ast }$.

But we do Reinforcement Learning, so we also need our agent to get better over experiences. Thus our agent needs to take actions that it thinks are the best according to what it's learned until now. So the agent chooses the actions that maximize $V^{\ast }$ for each state, and from the Bellman optimality equation, it chooses ${\max }_a{Q}^{\ast }$ (In fact, the agent chooses ${\max }_a\tilde{Q}$, but $\tilde{Q}$ converges to $Q^{\ast }$ so we'll abuse notation here).

To give its best guess, the agent always chooses $\arg {\max }_{a\in \mathcal{A}(s)}{Q}^{\ast }(s,a)$, so it follows the following policy:

$$\pi (a\mid s)=\{\begin{array}{ll}1,& \text{if}a=\arg {\max }_{a^{\prime }\in \mathcal{A}(s)}{Q}^{\ast }(s,a^{\prime })\\ 0,& \text{otherwise}\end{array}$$

By identifying the Bellman optimality equation with the Bellman equation in Appendix, we can conclude that this is in fact an optimal policy.

But this policy doesn't favor exploration, because it always follows the optimal path. Due to this, our agent might never go into certain states (i.e. sample certain state-action pairs), and thus it misses some information that would help get closer to $Q^{\ast }$. This is the exploration-exploitation tradeoff: the agent should sometimes choose suboptimal actions in order to visit new states and actions.
This tradeoff is handled by changing the above optimal (greedy) policy into an $ϵ$-greedy policy. The idea is that with probability $1-ϵ$ we apply our optimal policy, and with probability $ϵ$ we choose an action uniformly at random. Formally, this gives the following policy:

$$\pi (a\mid s)=\{\begin{array}{ll}(1-ϵ)+ϵ\frac{1}{\mid \mathcal{A}(s)\mid },& \text{if}a=\arg {\max }_{a^{\prime }\in \mathcal{A}(s)}{Q}^{\ast }(s,a^{\prime })\\ ϵ\frac{1}{\mid \mathcal{A}(s)\mid },& \text{otherwise}\end{array}$$

Typically, $ϵ$ changes as we go through training. It starts with a value close to 1 to favor exploration at the beginning, and decreases to be close to 0 as $\tilde{Q}$ converges to $Q^{\ast }$.

Now, with this policy, the agent chooses most of the time the optimal action, while still learning accurately $Q^{\ast }$.

Implementation Pseudocode

We give an implementation of the algorithm:

• Parameters: discount factor $\gamma \in ]0,1[$, step size (function) $\alpha (t)\in ]0,1]$
• Initialize: $\tilde{Q}(s,a)$, $\forall (s,a)\in \mathcal{S}\times \mathcal{A}$, arbitrarily. $t\leftarrow 0$.
• Repeat for each episode:
  • Initialize state $s_t$
  • For each step of the episode:
    • Choose $a_t$ from $s_t$ using the $ϵ$-greedy policy
    • Take action $a_t$, observe reward $R(s_t,a_t)$ and next state $s^{\prime }$
    • $\tilde{Q}(s_t,a_t)\leftarrow \tilde{Q}(s_t,a_t)-{\alpha }_{t}B(s_t,a_t,s^{\prime })$
    • $t\leftarrow t+1$
    • $s_t\leftarrow s^{\prime }$
  • Until: $s_t$ ends the episode

Replay Memory trick: To improve the learning of $Q^{\ast }$, we can memorize each $(s_t,a_t,s^{\prime })$ inside a set $E$, and at the end of each episode, we can sample tuples uniformly at random from $E$ and apply the learning process to them. But this has the disadvantage of being slower and more costly.

Deep-Q-Learning

So far, we've been assuming a tabular representation of the Q-function. There is 1 Q-Value to learn per $(s,a)$ tuple, so the number of Q-Values (size of the table) can go up to $\mathcal{S}\times \mathcal{A}$.
In practice, $|\mathcal{S}|$ is very big, so having to store all the Q-values in a table is impractical.
Since for any limited-size set $\mathcal{S}$ we can uniquely represent any $s\in \mathcal{S}$ using $lo{g}_2(|\mathcal{S}|)$ bits, it would be better to have a limited-size parameterized function that approximates the Q-function.

This is what deep Q-Learning is about: have an artificial neural network approximate the Q-function. The network would get a representation of $(s,a)$ as input (achievable using $lo{g}_2(|\mathcal{S}|)+lo{g}_2(|\mathcal{A}|)$ bits), and it would output an approximate value of $Q(s,a)$.

Our deep Q-Learning network (Q-network) is noted as $Q_{\theta }$ with parameters to learn $\theta$. The loss we use is the bellman error squared:

$$y_{t,\theta }=R(s_t,a_t)+\gamma \underset{a\in \mathcal{A}(s_{t+1})}{\max }{Q}_{\theta }(s_{t+1},a)$$

$$L(s_t,a_t,s_{t+1})={\left(Q_{\theta }(s_t,a_t)-y_{t,\theta }\right)}^2$$

$y_{t,\theta }$ is the target Q-value and $\theta$ is fixed.

Now, updating Q is done using backpropagation:

$$\theta \leftarrow \theta -{\alpha }_t\frac{\partial L}{\partial \theta }$$

Where $\frac{\partial L}{\partial \theta }=2(Q_{\theta }(s_t,a_t)-y_{t,\theta })\frac{\partial Q_{\theta }}{\partial \theta }$.

Notice that, in the loss, we are using the same parameters $\theta$ for the target Q-value and for the predicted Q-value. This gives significant correlation between the target Q-value and $\theta$ that we are learning. So at each training (updating) step, both our predicted Q-value and the target Q-value will shift. We're getting closer to the target, but the target is also moving. This leads to oscillation in training.
To mitigate this, we can update the target's $\theta$ every $T$ training steps.

Implementation Pseudocode

Here is an implementation of the algorithm using Q-network $Q_{\theta }$:

• Parameters: discount factor $\gamma \in ]0,1[$, step size (function) $\alpha (t)\in ]0,1]$, $T\in {\mathbb{N}}^{\ast }$
• Initialize: $\theta$ using favorite initialization technique. ${\theta }_T\leftarrow \theta$. $t\leftarrow 0$. $i\leftarrow 0$.
• Repeat for each episode:
  • Initialize state $s_t$
  • For each step of the episode:
    • Choose $a_t$ from $s_t$ using the $ϵ$-greedy policy
    • Take action $a_t$, observe reward $R(s_t,a_t)$ and next state $s^{\prime }$
    • $y_{t,{\theta }_T}\leftarrow R(s_t,a_t)+\gamma {\max }_{a\in \mathcal{A}(s^{\prime })}{Q}_{{\theta }_T}(s^{\prime },a)$
    • $\theta \leftarrow \theta -2{\alpha }_t(Q_{\theta }(s_t,a_t)-y_{t,{\theta }_T})\frac{\partial Q_{\theta }}{\partial \theta }$
    • $t\leftarrow t+1$
    • $s_t\leftarrow s^{\prime }$
    • $i\leftarrow i+1$
    • if $i=T$, ${\theta }_T\leftarrow \theta$ and $i\leftarrow 0$
  • Until: $s_t$ ends the episode

References

1. The famous book by Richard S. Sutton and Andrew G. Barto - Reinforcement Learning: An Introduction
2. Watkins & Dayan, 1992 - Almost sure convergence of Q-Learning

Appendix

Bellman equation of the Q-Function:

$$\begin{array}{rl}{Q}^{\pi }(s,a)& ={\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+i}\mid s_t=s,a_t=a\right]\\ & =\sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a){\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+i}\mid s_t=s,a_t=a,s_{t+1}=s^{\prime }\right]\\ & =\sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a)\left(R(s_t,a_t)+\gamma {\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_{t+1}=s^{\prime }\right]\right)\\ & =R(s_t,a_t)+\sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a)\gamma {\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_{t+1}=s^{\prime }\right]\\ & =R(s_t,a_t)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a)\sum _{a^{\prime }\in \mathcal{A}(s_{t+1})}\pi (a_{t+1}=a^{\prime }\mid s_{t+1}=s^{\prime }){\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_{t+1}=s^{\prime },a_{t+1}=a^{\prime }\right]\\ & =R(s_t,a_t)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a)\sum _{a^{\prime }\in \mathcal{A}(s_{t+1})}\pi (a_{t+1}=a^{\prime }\mid s_{t+1}=s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })\end{array}$$

Simplifying the notation:

$$\Rightarrow Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }\mid s,a)\sum _{a^{\prime }\in \mathcal{A}(s^{\prime })}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })$$

---

Bellman equation of the V-Function:

$$\begin{array}{rl}{V}^{\pi }(s)& ={\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+i}\mid s_t=s\right]\\ & ={\mathbb{E}}_{\pi }\left[r_t+\gamma \sum _{i=1}^{\infty }{\gamma }^{i-1}{r}_{t+i}\mid s_t=s\right]\\ & ={\mathbb{E}}_{\pi }\left[r_t+\gamma \sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_t=s\right]\\ & =\sum _{a\in \mathcal{A}(s_t)}\pi (a_t=a\mid s_t=s){\mathbb{E}}_{\pi }\left[r_t+\gamma \sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_t=s,a_t=a\right]\\ & =\sum _{a\in \mathcal{A}(s_t)}\pi (a_t=a\mid s_t=s)\sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a){\mathbb{E}}_{\pi }\left[r_t+\gamma \sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_t=s,a_t=a,s_{t+1}=s^{\prime }\right]\\ & =\sum _{a\in \mathcal{A}(s_t)}\pi (a_t=a\mid s_t=s)\sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a)\left(R(s_t,a_t)+\gamma {\mathbb{E}}_{\pi }\left[\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+1+i}\mid s_t=s,a_t=a,s_{t+1}=s^{\prime }\right]\right)\\ & =\sum _{a\in \mathcal{A}(s_t)}\pi (a_t=a\mid s_t=s)\sum _{s^{\prime }\in \mathcal{S}}p(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a)\left(R(s_t,a_t)+\gamma V^{\pi }(s^{\prime })\right)\end{array}$$

Simplifying the notation:

$$\Rightarrow V^{\pi }(s)=\sum _{a\in \mathcal{A}(s)}\pi (a\mid s)\sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }\mid s,a)\left(R(s,a)+\gamma V^{\pi }(s^{\prime })\right)$$