Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
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?
You appear to comparing the value table update steps in policy iteration and value iteration, which are both derived from Bellman equations.
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'))$$
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.
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.
