1RL - Planning

Last time we talked about MDP's, along with the MDP are some value functions you can calculate,
and we saw how when we "know" the MDP (ie we know the tuple $<S,A,\mathcal{P},\mathbf{R},\gamma$) Then we can caluclate the value functions, and hence recursively calculate the optimal value functions, and hence the optimal policy.

Planning, unlike reinforcement learning is the act of solving (finding optimals) of a known mdp.

There are two types of planning, both when MDP is fully known.
Prediction: given a policy, figure out its value function (evaluate the policy)
Control: find the optimal policy.

Prediction in planning by DP

Above we have the bellman equation for the state value function of an MDP

How do use dynamic programming to evaluate $v_{\pi }$? well first, we can ease ourself realizing that for a given policy, from an MDP we can extract out an MRP:

Notice that ${\mathbf{R}}_{\mathbf{s}}^{\mathbf{a}}$ is a matrix that gives the immediate value for taking an action $a$ in state $s$. Hence $\sum _{a\in A}\pi (a|s){\mathbf{R}}_s^a={\mathbf{R}}_s^{\pi }$. That is, for a fixed policy, if we know the expected reward for state action pairs$(s,a)$, then under that policy, the expected reward for a state $s$ is $\sum _{a\in A}{\mathbb{P}}_{\pi }(a|s){\mathbf{R}}_s^a$, where ${\mathbb{P}}_{\pi }(a|s)=\pi (a|s)$.

And moreover, if the environment transition dynamics from state $s$ to state $s^{\prime }$ under the action $a$ is given by the distribution tensor ${\mathcal{P}}_{s\to s^{\prime }}^a$ then to get the expected dynamics for a state $s$ to $s^{\prime }$ we have to average out the contribution of actions from out policy. Hence ${\mathcal{P}}_{s\to s^{\prime }}^{\pi }=\sum _{a\in A}\pi (a|s){\mathcal{P}}_{s\to s^{\prime }}^a$.

The tuple $<S,{\mathcal{P}}^{\pi },{\mathbf{R}}^{\pi },\gamma >$is then a Markov reward process under the policy $\pi$

Now then, distributing the sums over,

Eqivalently,

So what's the time and space on the algorithm like?
well we need to store $S$ that takes $O(n)$ space ($n$ is the number of states), ${\mathbf{R}}^{\pi }$ also takes $O(n)$ space, but ${\mathcal{P}}^{\pi }$ is a matrix that takes $O(n^2)$ space. we also need to store $v_{\pi },v_{\pi }^{\prime }$. so in total $O(4n+n^2)=O(n^2)$ space complexity PER ITERATION.
And as you can see there are two loops nested, each going over the state, and the computation in the inner loop is $O(1)$ and the computation of the outer loop before the inner loop starts is also $O(1)$. Therefore overall $O(n^2)$ Time complexity PER ITERATION.

but how many iterations do we need to get a good estimate of the actual value function (of the policy) $v_{\pi }$? There is a theorem that it does converge. Suppose we need $K$ iterations to converge, the algorithm then takes $O(K{n}^2)$ Time and still occupies $O(n^2)$ space.

Control in planning by DP:

Sure we can iterate on the value function of a fixed policy to get closer to the true value function under that policy, but CAN we iterate towards a better policy? the ANSWER IS YES!

policy iteration by DP:

The rough idea is as follows: start with an initial policy DETERMINISTIC policy $\pi (s)=a$
Then extract the co-responding MRP from this policy, and then evaluate this policy and get its value function, using the above algorithm: call it $v_{\pi }$
recall $v_{\pi }(s)=\sum _{a\in A}\pi (a|s)q_{\pi }(s,a)$ and
$q_{\pi }(s,a)={\mathbf{R}}_s^a+\gamma \sum _{s^{\prime }\in S}{\mathcal{P}}_{s\to s^{\prime }}^a{v}_{\pi }(s^{\prime })$.

Using the second equation get $q_{\pi }$ from $v_{\pi }$. Then,
the new policy we get (deterministic) is one which acts greedily wrt to $v_{\pi }$ and hence $q_{\pi }$. Ie at every state, the new policy picks the action with the highest action value for that state

Now for the deterministic policies, $\pi (a|s)=0\text{unless}a=\pi (s)where\pi (a|s)=1$.

Consider any state $s$.With our old deterministic policy, suppose $\pi (a|s)=1$ if and only if $a=a_{\pi }$.
in our new policy, ${\pi }^{\prime }(a|s)=1$ if and only if $a=a^{\ast }$ where $a^{\ast }=\arg \underset{a\in A}{max}{q}_{\pi }(s,a)$. Therefore $q_{\pi }(s,a_{\pi })\le q_{\pi }(s,a^{\ast })$.

And notice that $v_{\pi }(s)=\sum _{a\ne a_{\pi }}\pi (a|s)q_{\pi }(s,a)+\pi (a_{\pi }|s)q_{\pi }(s,a_{\pi })=0+q_{\pi }(s,a_{\pi })$.
And with a similar decomposition,
$v_{{\pi }^{\prime }}(s)=\sum _{a\ne a^{\ast }}{\pi }^{\prime }(a|s)q_{{\pi }^{\prime }}(s,a)+{\pi }^{\prime }(a^{\ast }|s)q_{{\pi }^{\prime }}(s,a^{\ast })=0+q_{{\pi }^{\prime }}(s,a^{\ast })$.

And therefore, $v_{\pi }(s)\le v_{{\pi }^{\prime }}(s)$ for any state $s$. And therefore in the partial ordering defined on policies earlier $\pi \le {\pi }^{\prime }$.

This is cool! take any deterministic policy, calculates its state value using the above algorithm, then gets it action value and then make a new deterministic policy that is greedy on the action value.

We can iterate this process over and over! and if improvements stop we have the optimal value, policy and action policy!

Let us write some functions to do our bidding, and this time, we will keep the loops implict.

First we write a function to get an MRP from an MDP given a policy.

Next, we write a function that does one step of the value function calculating iteration algorithm, given the policy and its co-responding induced MRP.

Nice!

So the policy iteration algorithm looks like: (and I wont write down the whole idea)

• Initialize $\pi$
• do $<S,R^{\pi },{\mathcal{P}}^{\pi },\gamma >\leftarrow \text{extract}(S,A,\mathbf{R},\mathcal{P},\gamma ,\pi )$
• initialize $v_{\pi }$
• $v_{\pi }\leftarrow$ do ($\text{calculate-v}(v_{\pi },\pi ,S,{\mathbf{R}}^{\pi },{\mathcal{P}}^{\pi },\gamma )$ $K$ times or up to $ϵ$ closeness of each iteration).
• $\pi \leftarrow$ do $\text{p-iterate}(v_{\pi },\pi ,\mathcal{P},\mathbf{R},\gamma )$

Here is a picture to summarize it all
!Support/Pasted image 20250328055823.png

But now we think, how the fuck do do we find the optimal value function without iterating on the policy? Cause after all, if we have the optimal state value function, we can quickly get the optimal action value function, and hence the optimal policy is just argmaxing on the action value function.

So in the next idea (value iteration) we will not evaluate the a policy and get the value function that way, but we will rather try to use the BELLMAN OPTIMALITY recursion to directly get the optimal value function.

Value iteration with DP:

First of all, we need a theorem.
!Support/Pasted image 20250328060316.png

Now Let us find some intuition on this, Imagine there is a ONE PLAYER GAME where you make some decisions. Also imagine that the game ends in exactly 3 different states, $s_a,s_b,s_c$ where $s_a$ has a reward of $-1$ $s_b$ a reward of $0$ and $s_c$ of $+1$.
then obviously $v\ast (s_a)=-1,v\ast (s_b)=0,v\ast (s_c)=1$. given this initial information, we could use the bellman optimality equation to back up this optimal value function for other states (imagine backing up these values through a tree where the three final states are the leaves). Below is the bellman optimality equation.

In truth, we just start with some initial $v$ and just iterate the above equation over and over, and somehow this gives us the optimal value function. What is going on?

Think about this: no matter what $v$ we start out with, at the first iteration of the above equation, AT LEAST THE leaf states have exact rewards assigned to them, and from there, maxing of rewards can propagate back up the state-action tree. Or if you like starting out with $v=<0,...0>$ we assign the correct (optimal $v$) for the leaf states, which is just the reward for the leaf state (where you can't really take any action). But we are not going to write proofs, this works because engineering :)