¿Por qué siempre hay al menos una política que es mejor o igual a todas las demás políticas?

Aprendizaje de refuerzo: una introducción. Segunda edición, en progreso ., Richard S. Sutton y Andrew G. Barto (c) 2012, pp. 67-68.

Resolver una tarea de aprendizaje de refuerzo significa, más o menos, encontrar una política que logre muchas recompensas a largo plazo. Para MDP finitos, podemos definir con precisión una política óptima de la siguiente manera. Las funciones de valor definen un orden parcial sobre las políticas. Una política $\pi$ se define como mejor o igual a una política $\pi'$ si su rendimiento esperado es mayor o igual que el de $\pi'$ , para todos los estados. En otras palabras, $\pi \geq \pi'$ si y solo si $v_\pi(s) \geq v_{\pi'}(s)$ , para todos los $s \in \mathcal{S}$ .Siempre hay al menos una política que es mejor o igual que todas las demás políticas. Esta es una política óptima.

¿Por qué siempre hay al menos una política que es mejor o igual a todas las demás políticas?

Justo después de la parte citada, el mismo párrafo le dice en realidad qué es esta política: es la que toma las mejores medidas en cada estado. En un MDP, la acción que tomamos en un estado no afecta las recompensas por las acciones tomadas en otros, por lo que simplemente podemos maximizar la política estado por estado.

La existencia de una política óptima no es obvia. Para ver por qué, tenga en cuenta que la función de valor proporciona solo un orden parcial sobre el espacio de las políticas. Esto significa:

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

Dado que esto es solo un pedido parcial, podría haber un caso en el que dos políticas, y π 2 , no sean comparables. En otras palabras, hay subconjuntos del espacio de estado, S 1 y S 2 de manera que:$\pi_1$$\pi_2$$S_1$$S_2$

$$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.

$\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

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.