<commit_before>---
layout:     post
title:      The Policy of Truth
date:       2018-02-14 0:00:00
summary:    An outsider tour of reinforcement learning, Part 7. Policy gradient doesn't have gradients.
author:     <NAME>
visible:    false
---

Before talking about policy gradient, let's step back and consider a pure optimization setup. This setup will seem like a bizarre caricature, but, in a moment, we'll see this is \emph{exactly what people do in Reinforcement Learning}.

Let's start with just trying to maximize a function. Given a function $R[u]$, I want to find the $u$ that makes this as large as possible. That is, I'd like to solve the optimization problem

$$
\begin{array}{ll}
	\mbox{maximize}_u & R[u] \,.
	\end{array}
$$


Now, bear with me for a second into a digression that might seem tangential. Any optimization problem like this is equivalent to an optimization over probability distributions on $u$.

$$
\begin{array}{ll}
	\mbox{maximize}_{p(u)} & \E_p[R[u]]
\end{array}
$$

The equivalence is really straight forward: if $u_\star$ is the optimal solution, then you'll get the same cost if you put a Delta-function around $u_\star$.  Moreover, if $p$ is a probability distribution, it's clear that $\E_p[R[u]]$ can never be smaller than $R[u_\star]$. So I can either optimize over $u$ or I can optimize over \emph{distributions} over $u$.

Now here is where the first sleight of hand often occurs in Reinforcement Learning... Rather than optimizing over the space of of all probability distributions, I'm going to optimize over a parametric family $p(u;\vartheta)$.  For example, I could restrict my attention to Gaussian distributions or some other model which is easy to parameterize and to sample from (the sampling part is essential as we will soon see). If this family contains all of the delta functions, then the optimal values still coincide. But, as in the case of Gaussians, if they don't contain the delta functions, you will only get an upper bound on the optimal cost no matter how good of a probability distribution you find. As a result, if you sample $u$ from the policy, their expected reward will necessarily be suboptimal.

## The REINFORCE algorithm

There is a general purpose algorithm for finding descent directions of the cost
$$
\begin{array}{ll}
	\mbox{maximize}_{\vartheta} & J(\vartheta):=\E_{p(u;\vartheta)}[R[u]]
	\end{array}
$$
The idea is to use a clever trick:
\begin{align*}
	\nabla J(\vartheta) &= \int R(u) \nabla p(u;\vartheta) du\\
	&= \int R(u) \left(\frac{\nabla p(u;\vartheta)}{p(u;\vartheta)}\right) p(u;\vartheta) dx\\
	&= \int \left( R(u) \nabla \log p(u;\vartheta) \right) p(u;\vartheta)dx
	= \E_{p(u;\vartheta)}\left[ R(u) \nabla \log p(u;\vartheta) \right]\,.
\end{align*}

Now something magical occurs. Suppose you sample $u$ from $p(u;\vartheta)$.  Then $R(u) \nabla \log p(u;\vartheta)$ is an unbiased estimate of the gradient of $J(\vartheta)$. Hence, we can use this for stochastic gradient descent.

The REINFORCE algorithm is a general purpose algorithm using this trick:
\begin{enumerate} \itemsep 0pt
 \item Choose some initial guess $\vartheta_0$ and stepsize sequence $\{\alpha_k\}$. Set $k=0$.
 \item Sample $u_k$ i.i.d., from $p(u;\vartheta_k)$.
 \item Set $\vartheta_{k+1} = \vartheta_k + \alpha_k R(u_k) \nabla \log p(u_k;\vartheta_k)$.
 \item Increment $k=k+1$ and go to 2.
\end{enumerate}

This seems weird: we get a stochastic gradient, but the function we cared about optimizing---$R$---is only accessed through function evaluations. We never compute gradients of $R$ itself. So is this algorithm any good?

It depends on what you are looking for. If you're looking for something to compete with gradients, no. It's a terrible algorithm. If you're looking for an algorithm to compete with a finite difference approximation to $R$ then... it's still a terrible algorithm. But the math is cute.

OK, you're not convinced.  Let's just start with a simple simple example.  Let
$$
	R[u] = -||u-z||^2
$$
Let $p(u;\vartheta)$ be a multivariate Gaussian with mean $\vartheta$ and variance $\sigma^2 I$.  What does policy gradient do?  First, note that

$$
	\E_{p(u;\vartheta)} = -\|\vartheta-z\|^2 - \sigma^2 d
$$

Obviously, the best thing to do would be to set $\vartheta=z$. Note that the expected cost is off by $\sigma^2 d$ at this point, but at least this would be finding a good guess for $u$.  Also, as a function of $\vartheta$, $J$ is \emph{strongly convex}, and the most important thing to know is the expected norm of the gradient as this will control the number of iterations. Now, if you start at $\vartheta=0$, then the norm of the gradient is<commit_msg>adding reinforce post<commit_after>---
layout:     post
title:      The Policy of Truth
date:       2018-02-14 0:00:00
summary:    An outsider tour of reinforcement learning, Part 7. Policy gradient doesn't have gradients.
author:     <NAME>cht
visible:    false
---

Before talking about policy gradient, let's step back and consider a pure optimization setup. This setup will seem like a bizarre caricature, but, in a moment, we'll see this is \emph{exactly what people do in Reinforcement Learning}.

Let's start with just trying to maximize a function. Given a function $R[u]$, I want to find the $u$ that makes this as large as possible. That is, I'd like to solve the optimization problem

$$
\begin{array}{ll}
	\mbox{maximize}_u & R[u] \,.
	\end{array}
$$


Now, bear with me for a second into a digression that might seem tangential. Any optimization problem like this is equivalent to an optimization over probability distributions on $u$.

$$
\begin{array}{ll}
	\mbox{maximize}_{p(u)} & \mathbb{E}_p[R[u]]
\end{array}
$$

The equivalence is really straight forward: if $u_\star$ is the optimal solution, then you'll get the same cost if you put a Delta-function around $u_\star$.  Moreover, if $p$ is a probability distribution, it's clear that $\mathbb{E}_p[R[u]]$ can never be smaller than $R[u_\star]$. So I can either optimize over $u$ or I can optimize over \emph{distributions} over $u$.

Now here is where the first sleight of hand often occurs in Reinforcement Learning... Rather than optimizing over the space of of all probability distributions, I'm going to optimize over a parametric family $p(u;\vartheta)$.  For example, I could restrict my attention to Gaussian distributions or some other model which is easy to parameterize and to sample from (the sampling part is essential as we will soon see). If this family contains all of the delta functions, then the optimal values still coincide. But, as in the case of Gaussians, if they don't contain the delta functions, you will only get an upper bound on the optimal cost no matter how good of a probability distribution you find. As a result, if you sample $u$ from the policy, their expected reward will necessarily be suboptimal.

## The REINFORCE algorithm

There is a general purpose algorithm for finding descent directions of the cost
$$
\begin{array}{ll}
	\mbox{maximize}_{\vartheta} & J(\vartheta):=\mathbb{E}_{p(u;\vartheta)}[R[u]]
	\end{array}
$$
The idea is to use a clever trick:
\begin{align*}
	\nabla J(\vartheta) &= \int R(u) \nabla p(u;\vartheta) du\\
	&= \int R(u) \left(\frac{\nabla p(u;\vartheta)}{p(u;\vartheta)}\right) p(u;\vartheta) dx\\
	&= \int \left( R(u) \nabla \log p(u;\vartheta) \right) p(u;\vartheta)dx
	= \mathbb{E}_{p(u;\vartheta)}\left[ R(u) \nabla \log p(u;\vartheta) \right]\,.
\end{align*}

Now something magical occurs. Suppose you sample $u$ from $p(u;\vartheta)$.  Then $R(u) \nabla \log p(u;\vartheta)$ is an unbiased estimate of the gradient of $J(\vartheta)$. Hence, we can use this for stochastic gradient descent.

The REINFORCE algorithm is a general purpose algorithm using this trick:
\begin{enumerate} \itemsep 0pt
 \item Choose some initial guess $\vartheta_0$ and stepsize sequence $\{\alpha_k\}$. Set $k=0$.
 \item Sample $u_k$ i.i.d., from $p(u;\vartheta_k)$.
 \item Set $\vartheta_{k+1} = \vartheta_k + \alpha_k R(u_k) \nabla \log p(u_k;\vartheta_k)$.
 \item Increment $k=k+1$ and go to 2.
\end{enumerate}

This seems weird: we get a stochastic gradient, but the function we cared about optimizing---$R$---is only accessed through function evaluations. We never compute gradients of $R$ itself. So is this algorithm any good?

It depends on what you are looking for. If you're looking for something to compete with gradients, no. It's a terrible algorithm. If you're looking for an algorithm to compete with a finite difference approximation to $R$ then... it's still a terrible algorithm. But the math is cute.

OK, you're not convinced.  Let's just start with a simple simple example.  Let
$$
	R[u] = -||u-z||^2
$$
Let $p(u;\vartheta)$ be a multivariate Gaussian with mean $\vartheta$ and variance $\sigma^2 I$.  What does policy gradient do?  First, note that

$$
	\mathbb{E}_{p(u;\vartheta)} = -\|\vartheta-z\|^2 - \sigma^2 d
$$

Obviously, the best thing to do would be to set $\vartheta=z$. Note that the expected cost is off by $\sigma^2 d$ at this point, but at least this would be finding a good guess for $u$.  Also, as a function of $\vartheta$, $J$ is \emph{strongly convex}, and the most important thing to know is the expected norm of the gradient as this will control the number of iterations. Now, if you start at $\vartheta=0$, then the norm of the gradient is
{'fraction_non_alphanumeric': 0.10984079495672615, 'fraction_numerical': 0.005556149161235174, 'mean_word_length': 4.073170731707317, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3841999', 'n_tokens_mistral': 2886, 'n_tokens_neox': 2651, 'n_words': 1341}