10
$\begingroup$

Reinforcement Learning: An Introduction. Second edition, in progress., Richard S. Sutton and Andrew G. Barto (c) 2012, pp. 67-68.

Solving a reinforcement learning task means, roughly, finding a policy that achieves a lot of reward over the long run. For finite MDPs, we can precisely define an optimal policy in the following way. Value functions define a partial ordering over policies. A policy $\pi$ is defined to be better than or equal to a policy $\pi'$ if its expected return is greater than or equal to that of $\pi'$, for all states. In other words, $\pi \geq \pi'$ if and only if $v_\pi(s) \geq v_{\pi'}(s)$, for all $s \in \mathcal{S}$. There is always at least one policy that is better than or equal to all other policies. This is an optimal policy.

Why is there always at least one policy that is better than or equal to all other policies?

$\endgroup$
  • $\begingroup$ A very detailed proof (that does use Banach's fixed point theorem) appears in chapter 6.2 of "Markov Decision Processes" by Puterman. $\endgroup$ – Toghs Jul 10 '18 at 22:45
3
$\begingroup$

Just past the quoted part, the same paragraph actually tells you what this policy is: it is the one that takes the best action in every state. In an MDP, the action we take in one state does not affect rewards for actions taken in others, so we can simply maximize the policy state-by-state.

$\endgroup$
  • $\begingroup$ Is not this answer completely wrong? How can you say that optimizing policy state by state leads to optimal policy. If i optimize over state $S_t$ and it takes me $S_{t+1}$ and then optimizing at $S_{t+1}$ leads to an optimal value function $V_{t+1}$ but there is another policy in which $S_t$ leads suboptimally to $S_l$ and the optimal value function of $S_l$ is higher than $V_{t+1}$. How can you rule this out by such a cursory analysis? $\endgroup$ – MiloMinderbinder Nov 13 '18 at 14:44
  • $\begingroup$ @MiloMinderbinder If the optimal policy at $S_t$ is to choose $S_{t+1}$, then the value of $S_{t+1}$ is higher than the value of $S_l$. $\endgroup$ – Don Reba Nov 14 '18 at 21:01
  • $\begingroup$ My bad. Typo corrected: 'Is not this answer completely wrong? How can you say that optimizing policy state by state leads to optimal policy? If i optimize over state $S_t$ and it takes me to $S_{t+1}$ and then optimizing at $S_{t+1}$ leads to an optimal value function $V_{t+2}$ of $S_{t+2}$ but there is another policy in which $S_t$ though leads suboptimally to $S_{l+1}$ and hence the value function of $S_{t+1}$ is higher than $V_{l+1}$ but the value function of $S_{t+2}$ is higher under this policy than under the policy found by optimizing state by state. How is this outruled by you?' $\endgroup$ – MiloMinderbinder Nov 15 '18 at 9:09
  • $\begingroup$ I think the definition of $V$ will prevent this from happening in the first place, since it should account for future returns as well. $\endgroup$ – Flying_Banana Feb 10 at 17:47
  • $\begingroup$ The question would then be: why does $q_*$ exist? You cannot get around the Banach Fixed Point Theorem :-) $\endgroup$ – Fabian Werner Feb 14 at 17:10
8
$\begingroup$

The existence of an optimal policy is not obvious. To see why, note that the value function provides only a partial ordering over the space of policies. This means:

$$\pi' \geq \pi \iff v_{\pi'}(s) \geq v_{\pi}(s), \forall s \in S $$

Since this is only a partial ordering, there could be a case where two policies, $\pi_1$ and $\pi_2$, are not comparable. In other words, there are subsets of the state space, $S_1$ and $S_2$ such that:

$$v_{\pi'}(s) \geq v_{\pi}(s), \forall s \in S_1$$

$$v_{\pi}(s) \geq v_{\pi'}(s),\forall s \in S_2$$

In this case, we can't say that one policy is better than the other. But if we are dealing with finite MDPs with bounded value functions, then such a scenario never occurs. There is exactly one optimal value functions, though there might be multiple optimal policies.

For a proof of this, you need to understand the Banach Fixed Point theorem. For a detailed analysis, please refer.

$\endgroup$
5
$\begingroup$

$\newcommand{\mc}{\mathcal} \newcommand{\mb}{\mathbb}$

Setting

We are considering in the setting of:

  • Discrete actions
  • Discrete states
  • Bounded rewards
  • Stationary policy
  • Infinite horizon

The optimal policy is defined as: $$ \pi^\ast \in \arg \max_\pi V^\pi(s), \forall s \in \mc{S} \tag{1} $$ and the optimal value function is: $$ V^\ast = \max_\pi V^\pi (s), \forall s \in \mc S \tag{2} $$ There can be a set of policies which achieve the maximum. But there is only one optimal value function: $$ V^\ast = V^{\pi^\ast} \tag{3} $$

The question

How to prove that there exists at least one $\pi^\ast$ which satisfies (1) simultaneously for all $s \in \mc{S}$ ?

Outline of proof

  1. Construct the optimal equation to be used as a temporary surrogate definition of optimal value function, which we will prove in step 2 that it is equivalent to the definition via Eq.(2). $$ V^\ast(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V^\ast(s^\prime)] \tag{4} $$

  2. Derive the equivalency of defining optimal value function via Eq.(4) and via Eq.(2).

    (Note in fact we only need the necessity direction in the proof, because the sufficiency is obvious since we constructed Eq.(4) from Eq.(2).)

  3. Prove that there is a unique solution to Eq.(4).

  4. By step 2, we know that the solution obtained in step 3 is also a solution to Eq.(2), so it is an optimal value function.

  5. From an optimal value function, we can recover an optimal policy by choosing the maximizer action in Eq.(4) for each state.

Details of the steps

1

Since $V^\ast(s) = V^{\pi^\ast}(s) = \mb E_a [Q^{\pi^\ast}(s, a)]$, we have $V^{\pi^\ast}(s) \le \max_{a \in \mc A} Q^{\pi^\ast} (s, a)$. And if there is any $\tilde{s}$ such that $V^{\pi^\ast} \neq \max_{a \in \mc A} Q^{\pi^\ast} (s, a)$, we can choose a better policy by maximizing $Q^{\ast} (s, a) = Q^{\pi^\ast} (s, a)$ over $a$.

2

(=>)

Follows by step 1.

(<=)

i.e. If $\tilde V$ satisfies $\tilde V(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) \tilde V(s^\prime)]$, then $\tilde V(s) = V^\ast(s) = \max_\pi V^\pi(s), \forall s \in \mc S$.

Define the optimal Bellman operator as $$ \mc T V(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V(s^\prime)] \tag{5} $$ So our goal is to prove that if $\tilde V = \mc T \tilde V$, then $\tilde V = V^\ast$. We show this by combining two results, following Puterman[1]:

a) If $\tilde V \ge \mc T \tilde V$, then $\tilde V \ge V^\ast$.

b) If $\tilde V \le \mc T \tilde V$, then $\tilde V \le V^\ast$.

Proof:

a)

For any $\pi = (d_1, d_2, ...)$, $$ \begin{align} \tilde V &\ge \mc T \tilde V = \max_{d} [ R_d + \gamma \, P_d \tilde V] \\ &\ge R_{d_1} + \gamma \, P_{d_1} \tilde V \\ \end{align} $$ Here $d$ is the decision rule(action profile at specific time), $R_d$ is the vector representation of immediate reward induced from $d$ and $P_d$ is transition matrix induced from $d$.

By induction, for any $n$, $$ \tilde V \ge R_{d_1} + \sum_{i=1}^{n-1} \gamma^i P_\pi^i R_{d_{i+1}} + \gamma^n P_\pi^n \tilde V $$ where $P_\pi^j$ represents the $j$-step transition matrix under $\pi$.

Since $$ V^\pi = R_{d_1} + \sum_{i=1}^{\infty}\gamma^i P_\pi^i R_{d_{i+1}} $$ we have $$ \tilde V - V^\pi \ge \underbrace{\gamma^n P_\pi^n \tilde V -\sum_{i=n}^{\infty}\gamma^i P_\pi^i R_{d_{i+1}}}_{\rightarrow 0 \ \text{as}\ n\rightarrow \infty} $$ So we have $\tilde V \ge V^\pi$. And since this holds for any $\pi$, we conclude that $$ \tilde V \ge \max_\pi V^\pi = V^\ast $$ b)

Follows from step 1.

3

The optimal Bellman operator is a contraction in $L_\infty$ norm, cf. [2].

Proof: For any $s$, $$ \begin{align} \left\vert \mc T V_1(s) - \mc TV_2(s) \right\vert &= \left\vert \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V_1(s^\prime)] -\max_{a^\prime \in \mc A} [ R(s, a^\prime) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a^\prime, s^\prime) V(s^\prime)]\right\vert \\ &\overset{(*)}{\le} \left\vert \max_{a \in \mc A} [\gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) (V_1(s^\prime) - V_2(s^\prime))] \right\vert \\ &\le \gamma \Vert V_1 - V_2 \Vert_\infty \end{align} $$ where in (*) we used the fact that $$ \max_a f(a) - \max_{a^\prime} g(a^\prime) \le \max_a [f(a) - g(a)] $$

Thus by Banach fixed point theorum it follows that $\mc T$ has a unique fixed point.

References

[1] Puterman, Martin L.. “Markov Decision Processes : Discrete Stochastic Dynamic Programming.” (2016).

[2] A. Lazaric. http://researchers.lille.inria.fr/~lazaric/Webpage/MVA-RL_Course14_files/slides-lecture-02-handout.pdf

$\endgroup$
-1
$\begingroup$

The policy $a=\pi(s)$ gives the best action $a$ to execute in state $s$ according to policy $\pi$, i.e. the value function $v_\pi(s)=\max_{a \in A} q_\pi (s,a)$ is highest for action $a$ in state $s$.

There is always at least one policy that is better than or equal to all other policies.

Thus there is always a policy $\pi_*$ which gives equal or higher expected rewards than policy $\pi$. Note that this implies that $\pi$ could be an/the optimal policy ($\pi_*$) itself.

$\endgroup$
  • 3
    $\begingroup$ How does this answer the question? You're basically repeating statements written in the quote. $\endgroup$ – nbro Dec 8 '17 at 13:25

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.