(1) Policy Gradients (10 points)

In this question, we consider a toy MDP and get familiar with computing policy gradients.

a1  : 1

Consider the following infinite-horizon MDP. The initial state is always s1 , and the episode terminates when s2  is reached.  The agent receives reward 1 for taking action a1  and reward 0 for taking action a2 . In this case, we can define the policy with a single parameter θ:

πθ(a1 |s1 ) = θ,    πθ(a2 |s1 ) = 1 − θ

(a) Use policy gradients to compute the gradient of the expected return of πθ with respect to the parameter θ (Eq. 3). Do not use discounting.

You may find this fact useful:

kαk−1 = αk

(b) Compute the expected return of the policy πθ  directly (Eq. 1).  Compute the gradient of this expres- sion and verify that it matches your result in (a).

(c) Reward-to-go can be helpful and improve the statistical qualities of our policy gradient.   Apply reward-to-go as an advantage estimator.  Write the new policy gradient (Eq. 4),  and verify that it is unbiased.

(2) Bounding Error in Approximate Policy Iteration (10 points)

In this problem, we look at how errors in approximating the value function affect the performance of a policy during policy iteration.

Let’s assume we are in an infinite horizon MDP with discount factor γ .  We have a reference policy π whose true value function is Vπ (s). We collect rollouts with π, and fit a neural network to approximate

this value function, where V(ˆ)(s) ≈ Vπ (s).

Let’s assume we did a really good job and can guarantee that the error from the fit is at most ϵ .  More

formally, let ||Vπ −V(ˆ)|| ∞ ≤ ϵ .1

We now choose a greedy policy to improve upon policy ˆ(π):

ˆ(π)(s) = arga(m)ax lR(s,a) + γs′(Σ) P(s′ |s,a)V(ˆ)(s′ )]

Note that this is exactly the policy improvement step, except the value function is substituted with our approximate value function. We want to know how the greedy policy ˆ(π)(s) performs with respect to π(s).

Let Vˆ(π)(s) be the value of the greedy policy ˆ(π)(s). Prove the following:

|Vπ (s) − Vˆ(π)(s)| ≤ , for all s

In other words, ˆ(π) can end up doing much worse than π.  Additionally, even though the error from fitting

the value was ϵ, the performance error scales up by a factor of .

Hint: One way to approach the question would be:

1.  For any policy we have,

Vπ (s) = R(s,π(s)) + γ Σ P(s′ |s,π(s))Vπ (s′ )

s′

Use this substitution to expand Vπ (s) − Vˆ(π)(s).

2. Next, note that you need to establish a relationship between π(s) and ˆ(π)(s).  Exploit the following

observation: ˆ(π)(s) = argmax af(s,a) must imply f(s, ˆ(π)(s)) ≥ f(s,π(s)) for any policy π .

3. Use these facts to obtain the following intermediate result. For any s,

Vπ (s) − Vˆ(π)(s) ≤ 2γϵ + γ Σ Pr[s′ |s, ˆ(π)(s)](Vπ (s′ ) − Vˆ(π)(s′ ))

s′ ∈S

From the above, you should be able to prove the final result for all s.