2
$\begingroup$

I was looking at the Bellman equation, and I noticed a difference between the equations used in policy evaluation and value iteration.

In policy evaluation, there was the presence of $\pi(a \mid s)$, which indicates the probability of choosing action $a$ given $s$, under policy $\pi$. But this probability seemed to be omitted in the value iteration formula. What might be the reason? Maybe an omission?

$\endgroup$
2
  • $\begingroup$ Do you really mean "policy evaluation", or are you asking about "policy iteration"? "Policy evaluation" is also the name of a phase within policy iteration. However, value iteration and policy iteration are both optimal control solvers, so it would be more usual to compare those. Also policy evaluation in general is not a single algorithm, but a whole family of them. $\endgroup$ – Neil Slater Aug 25 '20 at 13:41
  • $\begingroup$ Iterative policy evaluation , where we iterate many times to find the value of a state wheelie following a policy, while the value iteration deals with the optimal action set, my question is the absence of Pi(a|s) in value iteration $\endgroup$ – Chukwudi Ogbonna Aug 25 '20 at 13:51
2
$\begingroup$

You appear to comparing the value table update steps in policy iteration and value iteration, which are both derived from Bellman equations.

Policy iteration

In policy iteration, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$, but can also be of the form $\pi(a|s): \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R} = Pr\{A_t = a |S_t =s\}$. Policy iteration then alternately evaluates then improves that policy, with the improvement always being to act greedily with respect to expected return. Because the policy function can be arbitrary, and also the current value estimates during evaluation might not relate to it directly, the function $\pi(s)$ or $\pi(a|s)$ needs to be shown.

Typically with policy iteration, you will see this update rule:

$$V(s) \leftarrow \sum_{r,s'} p(r,s'|s,\pi(s))(r + \gamma V(s'))$$

The above rule is for evaluating a deterministic policy, and is probably more commonly used. There is no real benefit in policy iteration to working with stochastic policies.

For completeness, the update rule for an arbitrary stochastic policy is:

$$V(s) \leftarrow \sum_a \pi(a|s) \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$

Value iteration

In value iteration, the current policy to evaluate is to always take the greedy action with respect to the current evaluations. As such, it does not need to be explicity written, because it can be derived from the value function, and so can the terms in the Bellman equation (specifically the Bellman equation for the optimal value function is used here, which usually does not refer the policy). What you would typically write for the update step is:

$$V(s) \leftarrow \text{max}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$

However, you can write this out as if there was a policy table:

$$\pi(s) \leftarrow \text{argmax}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$ $$a \leftarrow \pi(s)$$ $$V(s) \leftarrow \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$

This is not the usual way to implement it though, because of the extra maximum value search required to identify the action. In simple value iteration it does not matter what the interim action choices and policies actually are, and you can always derive them from the value function if you want to know.

Other value-based methods

You will find other algorithms that drive the current policy direct from a value function, and when they are described in pseudo-code they might not have an explicit policy function. It is still there, only the Bellman update is easily calculated directly from the value function, so the policy is not shown in the update step. Descriptions of SARSA and Q-learning are often like that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.