Por que sempre há pelo menos uma política que é melhor que ou igual a todas as outras políticas?

Aprendizado por Reforço: Uma Introdução. Segunda edição, em andamento ., Richard S. Sutton e Andrew G. Barto (c) 2012, pp. 67-68.

Resolver uma tarefa de aprendizado por reforço significa, basicamente, encontrar uma política que obtenha muitas recompensas a longo prazo. Para MDPs finitos, podemos definir com precisão uma política ideal da seguinte maneira. As funções de valor definem uma ordem parcial sobre as políticas. Uma política de $\pi$ é definido como sendo melhor do que ou igual a uma política $\pi'$ se o seu retorno esperado é maior ou igual ao de $\pi'$ , para todos os estados. Em outras palavras, $\pi \geq \pi'$ se e somente se $v_\pi(s) \geq v_{\pi'}(s)$ , para todos os $s \in \mathcal{S}$ . Sempre há pelo menos uma política que é melhor que ou igual a todas as outras políticas. Esta é uma política ideal.

Por que sempre há pelo menos uma política que é melhor que ou igual a todas as outras políticas?

Depois da parte citada, o mesmo parágrafo realmente diz qual é essa política: é a que executa as melhores ações em todos os estados. Em um MDP, a ação que realizamos em um estado não afeta as recompensas por ações realizadas em outros, portanto, podemos simplesmente maximizar a política estado a estado.

A existência de uma política ótima não é óbvia. Para ver o porquê, observe que a função value fornece apenas uma ordem parcial no espaço de políticas. Isso significa:

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

Como essa é apenas uma ordem parcial, pode haver um caso em que duas políticas, e π 2 , não sejam comparáveis. Em outras palavras, existem subconjuntos do espaço de estados, S 1 e S 2, de modo 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$$

Nesse caso, não podemos dizer que uma política é melhor que a outra. Mas, se estamos lidando com MDPs finitos com funções de valor limitado, esse cenário nunca ocorre. Há exatamente uma função de valor ideal, embora possa haver várias políticas ideais.

Para uma prova disso, você precisa entender o teorema de Banach Fixed Point. Para uma análise detalhada, consulte .

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

Configuração

Estamos considerando no cenário de:

• Ações discretas
• Estados discretos
• Recompensas limitadas
• Política estacionária
• Horizonte infinito

A política óptimo é definido como: e a função de um valor óptimo é: V * = max π V π ( s ) , ∀ s ∈ S Pode haver um conjunto de políticas que atingem o máximo. Mas existe apenas uma função de valor ideal: V ∗ = V π

$$\pi^\ast \in \arg \max_\pi V^\pi(s), \forall s \in \mc{S} \tag{1}$$ $$V^\ast = \max_\pi V^\pi (s), \forall s \in \mc S \tag{2}$$ $$V^\ast = V^{\pi^\ast} \tag{3}$$

A questão

Como para demonstrar que existe, pelo menos, um que satisfaz (1) simultaneamente para todos s ∈ S ?$\pi^\ast$$s \in \mc{S}$

Esboço da prova

1. Construa a equação ótima a ser usada como uma definição substituta temporária da função de valor ótimo, o que provaremos na etapa 2 que é equivalente à definição 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 a equivalência da definição da função de valor ótimo via Eq. (4) e via Eq. (2).

   (Observe que, de fato, precisamos apenas da direção da necessidade na prova, porque a suficiência é óbvia, pois construímos a Eq. (4) da Eq. (2).)

3. Prove que existe uma solução exclusiva para a Eq. (4).

4. Na etapa 2, sabemos que a solução obtida na etapa 3 também é uma solução para a Eq. (2), portanto é uma função de valor ideal.

5. A partir de uma função de valor ideal, podemos recuperar uma política ideal escolhendo a ação maximizadora na Eq. (4) para cada estado.

Detalhes das etapas

1

Como , temos V π ∗ ( s ) ≤ max a ∈ A Q π ∗ ( s , a ) . E se houver qualquer ~ s tais que V π * ≠ max uma $V^\ast(s) = V^{\pi^\ast}(s) = \mb E_a [Q^{\pi^\ast}(s, a)]$$V^{\pi^\ast}(s) \le \max_{a \in \mc A} Q^{\pi^\ast} (s, a)$$\tilde{s}$$V^{\pi^\ast} \neq \max_{a \in \mc A} Q^{\pi^\ast} (s, a)$$Q^{\ast} (s, a) = Q^{\pi^\ast} (s, a)$$a$

2

(=>)

Segue o passo 1.

(<=)

$\tilde V$$\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)]$$\tilde V(s) = V^\ast(s) = \max_\pi V^\pi(s), \forall s \in \mc S$

Defina o operador Bellman ideal como

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