1
$\begingroup$

In reinforcement learning, what guarantees that policy iteration would find the globally optimal solution and not just any local maximum?

I'm reading the book "Reinforcement Learning: An Introduction (second edition)" by Richard S. Sutton and Andrew G. Barto.

In chapter 4 they are discussing dynamic programming methods and on several occasions they mention that policy iteration is guaranteed to converge to the optimal policy because it satisfies the bellman optimality equation.

From wikipedia:

Bellman equation ... is a necessary condition for optimality

Necessary, but not sufficient. The bellman equation is non-linear so I don't see why there couldn't be multiple local maxima for the policy.

Why is policy iteration guaranteed to converge to the global optimum?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I think this is a duplicate of this, or, at least, your question should be answered there too. Let me know if that's the case, so that we can link the 2. $\endgroup$
    – nbro
    Dec 11, 2022 at 16:02

1 Answer 1

Reset to default
4
$\begingroup$

Let me see if I can cover all of the points you mentioned.

  1. The Bellman equation is linear (not nonlinear) in the state values of a given policy. The Bellman equation describes the relationship between the values of different states.

  2. The optimal policy is defined as the one that has the greatest state values, which are called optimal state values. Optimal state values are unique! Optimal policies may not be unique.

  3. The optimal state values and optimal policies are described by the Bellman optimality equation. The Bellman optimality equation is nonlinear in the optimal state values. If you can solve the Bellman optimality equation, then you can get the optimal state value and an optimal policy.

  4. Value iteration and policy iteration are two dynamical programming algorithms than can find optimal state values and hence optimal policies.

  5. Why can the policy iteration algorithm converge (or find the optimal state value for sure)? That is because value iteration can converge because it is an iterative algorithm suggested by the Contraction Mapping Theorem. The convergence of policy iteration can be obtained based on that of the value iteration algorithm.

The detailed proof (and all the points I mentioned above) can be found in this book: Mathematical Foundations of Reinforcement Learning especially chapter 2 and chapter 3.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .