model-free reinforcement learning — Jemoka Knowledge Base

In model-based reinforcement learning, we tried real hard to get T and R. What if we just estimated Q(s,a) directly? model-free reinforcement learning tends to be quite slow, compared to model-based reinforcement learning methods.

\begin{equation} \frac{1}{2} \left(\frac{1}{2}\right) \end{equation}

review: estimating mean of a random variable we got m points x^{(1 \dots m)} \in X , what is the mean of X?

\begin{equation} \hat{x_{m}} = \frac{1}{m} \sum_{i=1}^{m} x^{(i)} \end{equation}

\begin{equation} \hat{x}_{m} = \hat{x}_{m-1} + \frac{1}{m} (x^{(m)} - \hat{x}_{m-1}) \end{equation}

every time you get a new measurement x^{(m)}. sometimes we don’t scale it by \frac{1}{m}, you can scale it with constant \alpha which actually causes exponential decay of past samples (as it keeps getting scaled by \alpha).

\begin{equation} \hat{x} = \hat{x} + \alpha (x- \hat{x}) \end{equation}

Q-Learning Let us review the action-value function:

\begin{equation} Q(s,a) = R(s,a) + \gamma \sum_{s’}^{} T(s’|s,a) U(s’) \end{equation}

this is a model-free method, substituting in the definition of the value function:

\begin{equation} Q(s,a) = R(s,a) + \gamma \sum_{s’}^{} T(s’|s,a) \max_{a} Q(s’, a’) \end{equation}

Note! The second half is know in the shape of an expectation ("probability times the value"). Recall also that R(s,a) is the expected reward r when taking s,a. Let:

\begin{equation} r = \mathbb{E}[R(s,a)] \end{equation}

So we can say that:

\begin{equation} Q(s,a) = \mathbb{E} \left[r + \gamma \max_{a’} Q(s’, a’)\right] \end{equation}

Finally, then, we can perform random variable mean estimation scheme given above; recall:

\begin{equation} \hat{x} = \hat{x} + \alpha (x- \hat{x}) \end{equation}

hence, we update our new mean with:

\begin{equation} Q(s,a) \leftarrow Q(s,a) + \alpha \left[(r + \gamma \max_{a’} Q(s’, a’)) - Q(s,a)\right] \end{equation}

SARSA SARSA is Q-Learning where you hope the model converges. You HAVE to perform some Exploration and Exploitation to try out other actions, and then you just update your function accordingly:

\begin{equation} Q(s,a) \leftarrow Q(s,a) + \alpha \left[(r + \gamma Q(s’, a’)) - Q(s,a)\right] \end{equation}

this works in theory because over time, good Exploration and Exploitation assumes that:

\begin{equation} a’ \rightarrow \arg\max_{a’} Q(s’,a’) \end{equation}

Eligibility Traces Eligibility Traces is a change to SARSA which uses the number of visits as an additional constraint that allows updates to propagate each reward backwards given the list of states which caused that reward to be distributed. Meaning, let \lambda be some decay parameter, we have:

\begin{equation} \delta = r + \gamma Q(s’,a’) - Q(s,a) \end{equation}

and, we can write:

\begin{equation} Q(s,a) \leftarrow Q(s,a) + \lambda \delta N(s,a) \end{equation}

where by the visit counts are discounted such that:

\begin{equation} N(s,a) \leftarrow \gamma \lambda N(s,a) \end{equation}

See also Sarsa (Lambda). Generalized Q-Learning with Gradient action-value Consider Value Function Approximation. We were trying to fit a set of \theta at that time to find U_{\theta} that matches U^{*}. We now want to compute some Q_{\theta} in the same flavour:

\begin{equation} Q_{\theta}(s,a) \sim Q^{*}(s,a) \end{equation}

We can measure the difference between these two values like so:

\begin{equation} \ell(\theta) = \frac{1}{2}\mathbb{E}_{(s,a)\sim \pi^{*}}\left[(Q^{*}(s,a) - Q_{\theta}(s,a))^{2}\right] \end{equation}

We want to write this expected value distributed over s,a of the optimal policy because we want to calculate more samples over those states that the optimal policy ends up at most. To optimize Q_{\theta}, then, you betcha know what’s happenin:

\begin{align} \nabla \ell &= \nabla \frac{1}{2} \nabla \mathbb{E}_{(s,a) \sim \pi^{*}} \left[(Q^{*}(s,a)-Q_{\theta}(s,a))^{2}\right] \\ &= \mathbb{E}_{(s,a) \sim \pi^{*}} \left[(Q^{*}(s,a)-Q_{\theta}(s,a)) (-1)\nabla Q_{\theta}(s,a)\right] \\ &= -\mathbb{E}_{(s,a) \sim \pi^{*}} \left[(Q^{*}(s,a)-Q_{\theta}(s,a)) \nabla Q_{\theta}(s,a)\right] \end{align}

by a healthy dose of the chain rule. Now, to minimize this loss, we go in the direction opposite the gradient. The negatives then cancel out to give us:

\begin{equation} \theta \leftarrow \theta + \alpha \left[\mathbb{E}_{(s,a) \sim \pi^{*}} \left[(Q^{*}(s,a)-Q_{\theta}(s,a)) \nabla Q_{\theta}(s,a)\right] \right] \end{equation}

where \alpha \in (0,1). Similar to the SARSA assumption, good Exploration and Exploitation assumes that:

\begin{equation} Q \to Q^{*} \end{equation}

so we can drop our expectation with:

\begin{equation} \theta \leftarrow \theta + \alpha \left[(Q^{*}(s,a)-Q_{\theta}(s,a)) \nabla Q_{\theta}(s,a)\right] \end{equation}

Now, we can make one more assumption, the assumption from Q-Learning:

\begin{equation} Q^{*}(s,a) \approx r_{s} + \gamma \max_{a’} Q_{\theta}(s’,a’) \end{equation}

that taking the best actions with the Q you have will slowly approximate optimal Q.

\begin{equation} \theta \leftarrow \theta + \alpha \left[\left((r_{s} + \gamma \max_{a’} Q_{\theta}(s’,a’))-Q_{\theta}(s,a)\right) \nabla Q_{\theta}(s,a)\right] \end{equation}

you will note! this is actually just Q-Learning multiplying with a gradient. Policy Gradient see also Policy Gradient