8

I've seen at least two versions from the CS229, wondering if there is a comprehensive resource around this topic

The first version:

$$ B(V)(s) = V'(s) = R(s) + \gamma \max_{a \in A} \sum_{s' \in S} P_{sa}(s') V(s') $$

from problem 5 in http://cs229.stanford.edu/ps/ps4/ps4.pdf. It's called Bellman update operator in the problem description.

The second version:

$$ B(V)(s) = V'(s) = R(s) + \gamma \sum_{s' \in S} P_{s\pi(s)}(s') V(s') $$ from problem 4 in from https://see.stanford.edu/materials/aimlcs229/problemset4.pdf, it's called Bellman operator in the problem description.

Given $a$ is equivalent to $\pi(s)$, the major difference is one has a $\max$ operator which the other doesn't, so which is which, then?

Nick Cox
  • 48,377
  • 8
  • 110
  • 156
zyxue
  • 847
  • 6
  • 21

2 Answers2

7

The precise terminology might differ across sources, but according to the source I learned from, the first one is called the Bellman optimality equation or simply the Bellman equation. The second one is the Bellman expectation equation. The expectation equation is linear in $V$, so you can solve for $V$ using simple linear algebra. The optimality equation, on the other hand, is nonlinear (due to the max operation) so there is no closed-form solution... which is why there are many algorithms to find the optimal solution (Q-learning, value iteration, policy iteration etc.).

The expectation equation is usually used to evaluate a known policy $\pi$, whereas the optimality equation is used to learn the optimal policy $\pi^*$.

Moss Murderer
  • 739
  • 4
  • 12
  • Sounds the term "Bellman operator" is overloaded, which confused me. – zyxue Jan 22 '18 at 03:46
  • 1
    Cool, comparing to the comparison in https://stackoverflow.com/questions/37370015/what-is-the-difference-between-value-iteration-and-policy-iteration, **Bellman optimality equation** correspond to **Value iteration**, while **Bellman expectation equation** correspond to **Policy evalution**, insightful. – zyxue Jan 22 '18 at 03:59
2

A good resource will be the classical textbook on reinforcement learning Reinforcement Learning: An Introduction, mostly the part about dynamic programming. Another good resource will be Berkeley's opencourse on Artificial Intelligence on EdX.

The difference in their name (Bellman operator vs Bellman update operator) does not matter here. You will see other names like Bellman backup operator. They are all the same thing. Basically it refers to the operation of updating the value of state $s$ from the value of other states that could be potentially reached from state $s$.

The definition of Bellman operator requires also a policy $\pi(x)$ indicating the probability of possible actions to take at state $s$. The second definition of Bellman operator in your example means updating the value of state $s$ by taking actions with probability from any predefined policy $\pi$. On the other hand, the first definition of Bellman operator is only specific to one policy, which is to take action on state $s$ that gives the highest value of state $s$ with 100% probability.

Therefore, the first definition can be regarded as a specific example of the second definition: the second definition works for any policy, while the first definition only works for the optimal policy that gives the highest value.

DiveIntoML
  • 1,583
  • 1
  • 11
  • 21