How to Find the Best "Playbook"

Dynamic Programing (DP)

... is the collection of algorithms that used to compute the optimal policy.

(The algorithm is basically turning Bellman's Equation into update rules for improving approximations.)

DP works best in finite MDP, not so good in continuous tasks.

Policy Iteration is the process of getting to optimal policy, it has 2 legs: Policy Evaluation and Policy Improvement. Back and Forth a bunch of times. we find the policy with the highest cumulative reward.

TL;DR

The process of DP for improving policy is:

• Starting with a initial policy π

• Step 1: Policy Evaluation - While running the simulation using π, run evaluation loop until it converges, we get eval score v_π

• Step 2: Policy Improvement - Improve upon π according to v_π (how? keep reading), get new policy π' (specifically by updating strategy for every state)

• Step 3: Check if the strategy changed between old and new policy (for all states).

  • strategy changed --> means policy unstable --> go back to step 1 with π'

  • strategy didn't change --> policy stable --> stop

Policy Evaluation - by comparing "Value Table" (V_k) a.k.a. "the Orb"

Value table is an array of rewards for every possible state. I'd like to use the RL senario of a 4 by 4 grid:

The Agent can be located in any of the squares. Its goal is to reach the "goal" square. (that's its terminal state) by going left, right, up, down, one step at a time. (if it try to go beyond the edge it will stay in the same square)

Let's say the policy to start is just agent taking random steps.

Each square is a state. There's a total of 16 possible states.

Then the value table, after a "sweep" might look like this:

... What does those numbers mean really:

Each number means, if standing at that state, doing all actions (with possibility p outlined by π, aka habits), the calculated expected total reward after you reach the goal.

p at this point is 25% for each up, down, left and right, since agent moves randomly.

higher number means higher rewards. intuitively, being located at a closer square to goal has a higher chance to "run in" to goal. thus higher rewards.

Value Table is like a magic orb that see into all possible future. But it's a bad one, to start.

It is making reward predictions based on the current policy and the last predictions.

Updating this value table (or "taking a sweep") and comparing the old values to the new is how we can tell if we're done optimizing. Because at one point the change (aka the delta) of between old value and new value of a all the squares would be so small that it "converges". (you define this small threshold θ). An example will be the top left value changed from -5o to -50.001, delta is less than θ = 0.01.

When the future predictions between old orb and new orb is not too different , we know we got the right evaluation.

So we let the training run The sweep happens at an frozen instant, indepandent of time stamps, no simulation happening, and no agents moving.

(Read the second page of the written note for a step-by-step example of how value table is being constructed.)

Policy Improvement - How is the New Policy Derived

The gist is basically:

For each state:

try every action

pick the action with the highest q_π(s,a)

put that action as the strat for being at that state

(This is greedy version)