The (mathematical) why for not giving up.

Not really. But maybe.

"Happiness can be discrete
( ... even when melancholy seems continuous)."

### Setup: States and Actions Our 'way of doing things' is contained in the object \(\theta\). This decides *how we react* when given some state / situation in life \(s_t\) (at time \(t\)). We respond to a situation by taking an action according to the probability distribution \(a_t \sim \pi_{\theta}(a_t|s_t)\). This distribution (which depends on \(\theta\)) represents our "behaviour" and spits out our responding "action" given the situation \(s_t\). The object \(\theta\) is the "configuration" (*or* strategy) for our behaviour. We can tune our behaviour - by changing \(\theta\) which in turn changes our behaviour (distribution for actions) \(\pi_\theta(a_t|s_t)\). Let's assume our first state \(s_1\) is sampled from some distribution of initial states \(p(s_1)\). This state would be the cards we're dealt in life: $$s_1 \sim p(s_1)$$ Now our *response* as explained above would be sampled from our behaviour distribution: $$a_1 \sim \pi_{\theta}(a_t = a_1 | s_t = s_1)$$ After taking action \(a_1\) we land up in some state \(s_2\). Which state is this? Let's assume that this state is sampled from some "state transition" probability distribution that spits out a state *given some state* and *action taken*. This represents the randomness of the world. So we have: $$ s_{t+1} \sim p(s_{t+1} | a_t, s_t)$$ And so the cycle continues. This collection of specific actions taken and states landed on is a trajectory \(\tau\): $$\tau = (s_1, a_1, s_2, a_2, \dots, s_T) $$ Another way of saying the above could be that we are sampling our trajectories from some "trajectory" distribution as \(\tau \sim p_{\theta}(\tau)\) (instead of breaking down our sampling as sampling from policy {or *action distribution*} and transition distribuion {or *states distribution*}). Since both approaches are saying the same thing, we can say that: $$ p(\tau) = p(s_1, a_1, s_2, a_2, \dots, s_T)$$ $$ p_\theta(s_1, a_1, \dots) = p(s_1) \prod_{t=1}^{T} \pi_\theta(a_t | s_t) p(s_{t+1} | s_t, a_t) $$ ### Goal: Happiness and fulfillment Our "fulfillment" (*read* happiness) is captured by the function \(J(\pi_{\theta})\). This "fulfillment" function \(J\) depends on the actions we take in life and hence depends on our behaviour \(\pi_{\theta}\). More precisely \(J(\pi_\theta)\) is: $$ J(\pi_\theta) = \mathbb{E}_{\tau \sim p_{\theta}(\tau)}[\sum_{t} r_t]$$ where \(r_t\) is the reward / happiness / fullfillment we get at time \(t\). \(J\) then is basically quantifying the sum of mini-"happiness's" we're getting over all time. The expectation is because we're navigating a probabilistic world. As sincere and curious learners we want to figure out the best *way of doing things* that would make us happiest. More mathematically, we want to figure out behaviour optimum \(\pi^*_{\theta}\) that maximizes \(J\), as: $$ \pi^*_{\theta} = \arg\max_{\pi_\theta} J(\pi_{\theta}) $$ $$ = \arg\max_{\pi_{\theta}} \mathbb{E}_{p_{\theta}(\tau)}[\sum_{t} r_t] $$ $$ = \arg\max_{\pi_{\theta}} \mathbb{E}_{p_{\theta}(\tau)}[r_{\tau}] $$ Here I've just written the cumulative happiness over time \(\sum_t r_t\) as \(r_{\tau}\), the cumulative happiness over trajectory (same thing). ### Trying and learning So reiterating we're navigating this stochastic world using our current behaviour \(\pi_\theta\). If we somehow have the gradient \(\nabla_{\theta}J(\pi_\theta)\) we would get a sense of how to tune our \(\theta\) so that our fulfillment \(J(\pi_\theta)\) increases. By moving \(\theta\) in the direction of \(\nabla_{\theta} J(\pi_{\theta})\) we would move in the direction of increasing \(J\). The gradient \(\nabla_{\theta}J(\pi_\theta)\) is: $$\begin{aligned} \nabla_\theta J(\pi_\theta) &= \nabla_\theta \mathbb{E}_{p_{\theta}}[r_{\tau}] \\ &= \nabla_\theta \int_{\tau}^{}{p_\theta }{r(\tau)}\,d\tau\\ &= \int_{\tau}^{}{\nabla_\theta p_\theta } {r(\tau)}\,d\tau\\ &= \int_{\tau}^{}{\pi_\theta \nabla_\theta \log \pi_\theta } {r(\tau)} \,d\tau\\ &= \mathbb{E}_{\tau \sim \pi_\theta}\left[\nabla_\theta \log \pi_\theta r(\tau)\right]\end{aligned}$$ A subtle but beautiful point here is that we're actually tuning our *continuous* \(\theta\) knob for *discrete* rewards [Mario can collect chunky coins, Atari can have discrete points, and we can be happy in discrete bursts] that we collect along our trajectory (applies for continuous rewards too). Our integral above is a sum in \(\tau\) space - which is a sum over all possible trajectories. This is not nice at all* because we'd have to sum over all possible trajectories to get our gradient at current \(\theta\) . Let's approximate the above expectation through sampling a few '\(N\)' trajectories: $$\begin{aligned} \nabla_\theta J(\theta) &\approx \frac{1}{N} \sum_{i=1}^{N} \nabla_\theta \log \pi_\theta(\tau_i) {r(\tau_i)}\\ &\approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T}{} \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{t=1}^{T}{} r_t\end{aligned}$$ This estimator in its current form is extremely low bias and extremely high variance. Why is it high variance? Because the quantity inside the sum \(\sum^{N}_{i=1}\) can vary a lot depending on which trajectory we landed up in. Life trajectories can be pretty diverse and so the corresponding happiness over each trajectory can be pretty diverse too. This approximation approaches true gradient only when we've sampled infinite (all) trajectories. Due to this being high variance, we can very easily veer off finding potential optimal behaviours \(\pi^*_{\theta}\) when doing the optimization using this approximation. But what is the expression actually saying? It tells me how how to change my 'ways' \(\theta\). It's giving me the direction to go in \(\theta\) space, such that my expected fulfillment \(J\) is maximized. We go through each \(s_t\) observed in our trajectory and take note of the direction in \(\theta\) space we should move and *reweigh* (increase/decrease) the probability the action we took, increase it if the trajectory gave us "happiness" and decrease it if the trajectory gave us "sadness". One could argue that the true value of a trajectory can only be known if one actually follows it to the end - a thought both scary and reassuring at the same time. No one knows the right answer. But we're going to resort to extrapolating our *optimized* behaviour from only a few trajectories - that we could then use in both previously seen and unseen states. ### Can we ignore the past? Going back to our expression: $$\begin{aligned} \nabla_\theta J(\theta) &\approx \frac{1}{N} \sum_{i=1}^{N} \nabla_\theta \log \pi_\theta(\tau_i) {r(\tau_i)}\\ &\approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T}{} \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{t=1}^{T}{} r_t\end{aligned}$$ Examining the terms inside the sum, we can say that at each timestep \(t\) we're reweighing (increasing / decreasing) the probability of that "action" taken by the total happiness obtained over the entire trajectory. More precisely, we're moving in \(\theta\)-space according to \(\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)\) multiplied by cumulative reward over entire trajectory which is \(\sum^{T}_{t=1} r_t\). We need to reduce the quantity inside our estimator to reduce variance. A suggestion is to only count future happiness when evaluating the importance of the current action - thereby ignoring rewards / happinesses earned in the past. This is an acknowledgement of the fact that the action we take now should only be weighed by the happiness we get from hereon in the future and it has *nothing to do with the rewards earned in the past*. But can we show this mathematically that we can ignore past rewards when evaluating current actions? More precisely, can we say: $$\begin{aligned} \nabla_\theta J(\theta) &= \mathbb{E}_{\ {a_t | s_t} \sim\pi_\theta}\left[ \sum_{t=1}^{T}{} \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{t=1}^{T}{} r_t \right] \\ &= \mathbb{E}_{\ {a_t | s_t} \sim\pi_\theta}\left[ \sum_{t=1}^{T}{} \nabla_\theta \log \pi_\theta(a_t | s_t) \biggl(\sum_{t'=0}^{t-1}{} r_{t'} + \sum_{t'=t}^{T}{} r_{t'} \biggr)\right] \\ &\stackrel{?}{=} \mathbb{E}_{\ {a_t | s_t} \sim\pi_\theta}\left[ \sum_{t=1}^{T}{} \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{t'=t}^{T}{} r_{t'} \right] \\\end{aligned}$$ In other words we have to show: $$\begin{aligned} \mathbb{E}_{\ {a_t | s_t} \sim\pi_\theta}\left[ \sum_{t=1}^{T}{} \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{t'=0}^{t-1}{} r_{t'} \right] &= 0\end{aligned}$$ Let's go ahead and show that. ### Epiphanies emergent **Lemma:** Given a probability distribution \(P_{\ {\theta}}\) and random variable \(X\), such that \(X \sim P_{\ {\theta}}\), we have: $$\begin{aligned} \mathbb{E}_{X \sim P_\theta}\left[\nabla_\theta \log P_\theta(X)\right] = 0 \end{aligned}$$ Proof: $$\begin{aligned} \int_{x}^{}{P_\theta}\,dx &= 1\\ \end{aligned}$$ Taking gradient of both sides: $$\begin{aligned} \nabla_\theta \int_{x}^{}{P_\theta}\,dx &= \nabla_\theta 1\\\end{aligned}$$ Given gradient of \(P_\theta\) exists almost everywhere: $$\begin{aligned} \int_{x}^{}{\nabla_\theta P_\theta}\,dx &= 0 \\ \int_{x}^{}{P_\theta\nabla_\theta \log P_\theta}\,dx &= 0 \\ \mathbb{E}_{P_\theta}\left[\nabla_\theta \log P_\theta\right] &= 0 \\\end{aligned}$$ ---------------------------------\- Now, let's look at our original expectation. The happiness / reward \(r_{t'}\) for time \(t-1\) is the one obtained at time step \(t-1\) after taking action \(a_{t-1}\) in state \(s_{t-1}\): $$\begin{aligned} & \mathbb{E}_{\ {a_t | s_t}\sim\pi_\theta}\left[ \sum_{t=1}^{T}{} \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{t'=0}^{t-1}{} r_{t'} \right] \\ \end{aligned}$$ Let's condition the entire expectation on the state exactly at \(t\), \(s_t\) using iterated expectations and linearity of expectations. So the quantity above can be written as: $$\begin{aligned} & \mathbb{E}_{s_t}\left[\mathbb{E}_{\ {a_t | s_t}\sim\pi_\theta}\left[ \sum_{t=1}^{T}{} \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{t'=0}^{t-1}{} r_{t'} \right] | s_t\right] \\ &= \mathbb{E}_{s_t}\left[\sum_{t=1}^{T}{}\mathbb{E}_{a_t | s_t\sim\pi_\theta}\left[ \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{t'=0}^{t-1}{} r_{t'} \right] | s_t\right] \\ \end{aligned}$$ Now given \(s_t\) is fixed, the random variable \(\nabla_\theta \log \pi_\theta(a_t|s_t)\) is conditionally independent of the random variable involving \(\sum_{t'=0}^{t-1}{} r_{t'}\) for any \(t'\leq t\) given \(s_t\). In plain english, the value of an action taken now for total happiness is independent of past happiness if we already know our current state. By definition, the 'state' is Markovian in nature and contains all information needed to predict future states. So we can distribute the inner expectation as: $$\begin{aligned} & \mathbb{E}_{s_t}\left[\sum_{t=1}^{T}{}\mathbb{E}_{a_t | s_t\sim\pi_\theta}\left[ \nabla_\theta \log \pi_\theta(a_t | s_t) \right] \mathbb{E}_{a_{t'} | s_{t'}\sim\pi_\theta}\left[ \sum_{t'=0}^{t-1}{} r_{t'} | s_t\right] \right] \\ \end{aligned}$$ Using Lemma, the first expectation in the inner expectation is zero: $$\begin{aligned} & \mathbb{E}_{a_t|s_t \sim\pi_\theta}\left[ \nabla_\theta \log \pi_\theta(a_t | s_t) \right]=0 \\ \end{aligned}$$ so the entire expectation is zero. \(\square\) The past is gone. The future is conditionally independent of the past given the present. What could be gained (or lost) in the past has no bearing on how you change your behaviour now (to be happier). Now matters. And the future matters.

*unless quantum computers figure out monte carlo integration?