DQN

Paper of origin: Playing Atari with Deep Reinforcement Learning

$\mathcal{E}\dots$ environment (may be stochastic)
$a_t\in \mathcal{A}=\{1,\dots ,K\}$ … set of legal game actions
$x_t\in {\mathbb{R}}^d\dots$ observed image (vector of raw pixel values representing the screen)
$r_t\dots$ reward (change in game score)
$s_t\dots$ sequence of actions and rewards at time $t$
$Q(s,a;\theta )\approx Q^{\star }(s,a)$ … Approximate optimal action-value function with DQN $\theta$

Flow: An action is sampled at each time step $t$, passed to the environment, which modifies the internal state and game score.
The internal state is not observed by the agent; instead it observes an image of the current screen. Simmilar images can mean very different things however (environment states are perceptually aliased), e.g. when the position of a projectile is the same, but the speed different. So it is impossible to fully understand the current situation from only the current screen in the atari environmen → learn sequences of actions and observations → terminate in finite number of time-steps → finite MDP, each sequence is a distinct state → use each sequence $s_t$ as sate representation at time $t$.
Agent interact with env to max future rewards.
Standard future discounted return at time $t$ as $R_T={\sum }_{t^{\prime }=t}^T{y}^{t^{\prime }-t}{r}_{t^{\prime }}$,
where $T$ is the terminal time-step. Optimal action-value function: $Q^{\star }(s,a)={\max }_{\pi }\mathbb{E}[R_t|s_t=s,a_t=a,\pi ]$ (maximum possible return when seeing some sequence $s$, taking action $a$, chosen by policy $\pi$).

Note

The game score may depend on the whole prior sequence of actions and observations; feedback about an action may only be received after many thousands of time-steps have elapsed.

Basic idea of the Bellman Equation:
If we know the optimal value $Q^{\star }(s,a)$ of the sequence $s’$ at the next time-step for all possible actions $a’$, then the optimal strategy is to choose the action, which maximizes the expected value of $r+\gamma Q(s’,a’)$:

$$\text{displaylines}\begin{array}{r}{Q}^{\ast }(s,a)={\mathbb{E}}_{s^{\prime }\sim \mathcal{E}}\left[r+\gamma \underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })|s,a\right]\end{array}$$

The idea behind Q-Learning is to estimate this action-value function, by using the Bellman equation as an iterative update, which approximates the optimal action-value function as we approach infinite exploration steps:

$$\text{displaylines}\begin{array}{rl}& Q_{i+1}(s,a)=\mathbb{E}\left[r+\gamma \underset{a^{\prime }}{\max }{Q}_i(s^{\prime },a^{\prime })|s,a\right]\\ & Q_i\to Q^{\star }\text{as}i\to \infty \end{array}$$

I still don’t get this basic approach of how to do this with a Q-Table but nvm; Point is, it is obviously impractical and we have no generalization, as we estimate a value for each sequence separately!
This is why we use a NN to approximate the Q-function, a “Q-network” $\theta$.

$$\text{displaylines}\begin{array}{r}Q(s,a;\theta )\approx Q^{\star }(s,a)\end{array}$$

Train it by minimizing the sequence of loss functions $L_i({\theta }_i)$, which changes at each iteration $i$:

$$\text{displaylines}\begin{array}{r}{L}_i({\theta }_i)={\mathbb{E}}_{s,a\sim \rho (\cdot )}\left[(y_i-Q(s,a;{\theta }_i){)}^2\right],\end{array}$$

$s,a\sim p(\cdot )\dots$ shorthand $s,a\sim p(s,a)$
$p(s,a)\dots$ behaviour distribution (probability distribution over sequences and actions)
Target for iteration $i$: $y_i={\mathbb{E}}_{s^{\prime }\sim \mathcal{E}}\left[r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime };{\theta }_{i-1})|s,a\right]$
The parameters from the previous iteration ${\theta }_{i-1}$ are fixed when optimising the loss function $L_i({\theta }_i)$.
Targets depend on the network weights (in supervised learning, they are fixed before learning).
Dfferentiating the loss function with respect to the weights we arrive at the following gradient:

$$\text{displaylines}{\nabla }_{{\theta }_i}{L}_i({\theta }_i)={\mathbb{E}}_{s,a,\rho (\cdot );s^{\prime }\sim \mathcal{E}}\left[\left(r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime };{\theta }_{i-1})-Q(s,a;{\theta }_i)\right){\nabla }_{{\theta }_i}Q(s,a;{\theta }_i)\right]$$

We obviously can’t sample the entire state and action space, esp. with they are large or continous, so we approximate it, by replacing the expectations by single samples form the behaviour distribution $p$ and the environment $\mathcal{E}$:

$$\text{displaylines}{\nabla }_{{\theta }_t}{L}_t({\theta }_t)\approx \left(r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime };{\theta }_{t-1})-Q(s,a;{\theta }_t)\right){\nabla }_{{\theta }_t}Q(s,a;{\theta }_t)$$

(also we update the weights after every time step $t$)
This algorithm is model-free. The emulator / environment $\mathcal{E}$ is necessary, solves it directly with samples from the emulator, without constructing an estimate of $\mathcal{E}$.
It is also off-policy: Without a policy greedily taking actions to max expected future return: $a={\max }_{a}Q(s,a;\theta )$, but it explores (“behaviour distribution for adequate exploration”): epsilon greedy.
Uses experience replay.

Preprocessing applied:
Grey scale, downscaling, cropping relevant area (to make square for some optimizes conv)
Input to DQN:
4 frames stacked together (Not relevant for turn-based games)
They also “skipped” a frame every 3-4 frames, where just the last action was used instead of making the agent compute a new onee (Again doesn’t make sense for turn-based)
Learning:
2 networks, policy and target.

Transclude of Introduction-to-RL#^a06a7d

Output:
value for each action (as opposed to encoding $a$ as input and having $\#a$ forward passes)

TODO / DOING: Implementations on different envs:
Idea: Try out more sophisticated sampling methods, might be especially relevant for 2048? Cause when u are in critical situaitons which are way rarer ofc.
Idea: Compare soft vs hard paramteter updates
Should I truncate if it makes an “invalid” / useless (does not change state) move?

References

There is a long thread (above and below this message)

Q-Learning