1
$\begingroup$

I am reading Reinforcement Learning: An Introduction by Sutton & Barto. According to this textbook, as far as I understood, the authors claim that the policy and value iteration methods converge to an optimal stationary point. Actually, I now understand the procedure of these two iterative algorithms, but I can't accept why they converge to an optimal point.

In the textbook and many posts that I found by googling, many people say that "The value functions are monotonically increased as the iteration progresses. Thus, it will go to the optimal policy, as well as optimal value functions."

I strongly agree that "only if the algorithm's performance is monotonically improved and there exist an upper bound in terms of performance, the algorithm will converge to a stationary point." However, I cannot accept the word "Optimal." I think, to claim an algorithm converges to an optimal stationary point, we need to show not only its monotonic improving property but also "its locally non-stopping property." (Sorry, I made these words myself, but I believe you experts can understand what I mean.)

I believe that there must be some points that I was not able to understand. Can someone let me know why the policy and value iteration methods converge to an "OPTIMAL" solution?

ps. Only if the system can be represented as a Markovian decision process, are either the policy or the value iteration method optimal algorithm?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

These two algorithms converge to the optimal value function because

  1. they are instances of the generalization policy iteration, so they iteratively perform one policy evaluation (PE) step followed by a policy improvement (PI) step

  2. the PE step is an iterative/numerical implementation of the Bellman expectation operator (BEO) (i.e. it's numerical algorithm equivalent to solving a system of equations); here you have an explanation of what the Bellman operator is

  3. the BEO is a contraction (proof here), so the iterative application of the BEO makes the approximate value function closer to the optimal one, which is unique, i.e. PE convergences to the optimal value function of the current policy (proof here)

  4. Policy improvement is guaranteed to generate a policy that is better than the one in the previous iteration, unless the policy in the previous iteration was already optimal (see the policy improvement theorem in section 4.2 of the RL bible)

One thing that may confuse you is that you don't exactly know or have in mind the definition of the value function. A value function $v_\pi(s)$ is defined as the expected return that you will get starting in state $s$, then following policy $\pi$. So, if you have some policy $\pi$, then you perform one PE step until convergence, then you know that that value function is the optimal value function for $\pi$. Now, if $\pi_{t+1}$ is guaranteed to be a strict improvement over $\pi_{t}$, then it basically means that you will get more rewards with $\pi_{t+1}$ (which is the goal).

If you read the linked proofs and chapter 4 of the bible, then you should understand why these algorithms converge.

To address your last point, yes, we assume that we have an MDP. That's an assumption that most famous DP and RL algorithms make.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for your great answer. I have one more question. Can I say that "only if the system follows an MDP, the greedy-based policy iterative algorithm (despite not the epsilon-greedy-based one) provides an optimal policy as well as the corresponding optimal value functions for all states."? $\endgroup$
    – Danny_Kim
    Jan 22, 2022 at 17:40
  • $\begingroup$ For the $\epsilon$-greedy case we can do exploration with a probability of $\epsilon$, but for the greedy case we can't do. (I know, this does not imply that greedy cannot find an optimal solution, but it also does not imply that it will find an optimal solution.) Anyhow, is there no chance of getting stuck at $\pi$ such that $\pi<\pi^*$, where $\pi^*$ is the optimal policy? That is, is there a case where all the optimal value functions are found at a given $\pi$, and the policy improvement algorithm is executed based on them, but getting stuck at $\pi$ despite $\pi<\pi^*$. $\endgroup$
    – Danny_Kim
    Jan 22, 2022 at 17:51
  • $\begingroup$ I agree that if the $\epsilon$-soft (e.g., $\epsilon$-greedy)-based policy improvement is executed, a better policy will be found one day as long as it exists for a given set of value functions of all states. However, my intuition makes me think that if the greedy-based policy improvement is used, there might be the case where a better policy will not be found for a given current set of value functions of all states. Is my intuition totally wrong? $\endgroup$
    – Danny_Kim
    Jan 22, 2022 at 17:56
  • $\begingroup$ @Danny_Kim Did you understand why policy evaluation converges? Note that this happens only in the limit, i.e. if you execute "enough" iterations. Once you find the value function for a given policy, then you generate a new policy that is guaranteed to be a strict improvement over the previous one (if you read section 4.2 of the mentioned book, you will understand why). If you do this enough times, then (in the limit) you will get to the optimal policy. In practice, I am not sure how well policy iteration converges (it depends on $\gamma$ I think), but, in theory, they should converge. $\endgroup$
    – nbro
    Jan 22, 2022 at 21:36
  • $\begingroup$ Why can't you get stuck in a local optima? Because there's only one optimum. Note that we're not talking about Q-learning or SARSA, which are RL algorithms that do not use the model of the environment, while policy iteration does. Q-learning and SARSA do need to explore the environment (e.g. using the $\epsilon$-greedy policy) because they do not have the model of the environment, i.e. the probability distribution $p(s', r \mid s, a)$. The intuition of the convergence of PI can be found in the last diagram here. $\endgroup$
    – nbro
    Jan 22, 2022 at 21:38
0
$\begingroup$

Base on the fantastic answer by @nbro, let me complement a little bit clue which may help understand Policy Iteration's optimality convergence.

So Danny you said:

However, I cannot accept the word "Optimal." I think, to claim an algorithm converges to an optimal stationary point, we need to show not only its monotonic improving property but also "its locally non-stopping property."

I think here you actually worry about it may miss some possible cases which contains the optimal one in the process of iteration. However it won't. Here is a excerpt on page 75 in Reinforcement Learing: An Introduction written by Richard S. Sutton:

All the updates done in DP algorithms are called expected updates because they are based on an expectation over all possible next states rather than on a sample next state.

So it's about all possible next states rather than on a sample next state, which won't miss some possible cases in the iteration.

Improve this answer
$\endgroup$

You must log in to answer this question.

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