Pourquoi y a-t-il toujours au moins une politique meilleure ou égale à toutes les autres politiques?

Résoudre une tâche d'apprentissage par renforcement signifie, en gros, trouver une politique qui obtient beaucoup de récompenses à long terme. Pour les MDP finis, nous pouvons définir précisément une politique optimale de la manière suivante. Les fonctions de valeur définissent un ordre partiel sur les stratégies. Une politique $\pi$ est définie comme étant supérieure ou égale à une politique $\pi'$ si son rendement attendu est supérieur ou égal à celui de $\pi'$ , pour tous les États. En d'autres termes, $\pi \geq \pi'$ si et seulement si $v_\pi(s) \geq v_{\pi'}(s)$ , pour tout $s \in \mathcal{S}$ . Il existe toujours au moins une stratégie meilleure ou égale à toutes les autres stratégies. Il s'agit d'une politique optimale.

markov-process reinforcement-learning sh1ng
la source

Une preuve très détaillée (qui utilise le théorème du point fixe de Banach) apparaît dans le chapitre 6.2 de "Markov Decision Processes" de Puterman.

Toghs

Réponses:

Juste après la partie citée, le même paragraphe vous dit en fait quelle est cette politique: c'est celle qui prend la meilleure action dans chaque état. Dans un MDP, l'action que nous entreprenons dans un État n'affecte pas les récompenses pour les actions entreprises dans d'autres, nous pouvons donc simplement maximiser la politique État par État.

Don Reba
la source

Cette réponse n'est-elle pas complètement fausse? Comment pouvez-vous dire que l'optimisation de la politique état par état conduit à une politique optimale. Si j'optimise sur l'état

et cela me prend

, puis l'optimisation à

conduit à une fonction de valeur optimale

mais il existe une autre politique dans laquelle

conduit de manière sous-optimale à

et l'optimal la fonction de valeur de

est supérieure à

. Comment pouvez-vous exclure cela par une analyse aussi rapide?

S_{t}

$S_t$

S_{t + 1}

$S_{t+1}$

S_{t + 1}

$S_{t+1}$

V_{t + 1}

$V_{t+1}$

S_{t}

$S_t$

S_{l}

$S_l$

S_{l}

$S_l$

V_{t + 1}

$V_{t+1}$

MiloMinderbinder

@MiloMinderbinder Si la politique optimale à

est de choisir

, alors la valeur de

est supérieure à la valeur de

S_{t}

$S_t$

S_{t + 1}

$S_{t+1}$

S_{t + 1}

$S_{t+1}$

S_{l}

$S_l$

Don Reba

Ma faute. Correction de faute de frappe: «Cette réponse n'est-elle pas complètement fausse? Comment pouvez-vous dire que l'optimisation de la politique état par état conduit à une politique optimale? Si j'optimise sur l'état

et cela m'amène à

, puis l'optimisation à

conduit à une fonction de valeur optimale

mais il existe une autre politique dans laquelle

bien que conduit de manière sous-optimale à

et donc la fonction de valeur de

S_{t}

$S_t$

S_{t + 1}

$S_{t+1}$

S_{t + 1}

$S_{t+1}$

V_{t + 2}

$V_{t+2}$

S_{t + 2}

$S_{t+2}$

S_{t}

$S_t$

S_{l + 1}

$S_{l+1}$

S_{t + 1}

$S_{t+1}$ est supérieur à

mais la fonction valeur de

est plus élevée dans cette politique que dans la politique trouvée en optimisant état par état. Comment est-ce que vous l'ignorez?

V_{l + 1}

$V_{l+1}$

S_{t + 2}

$S_{t+2}$

MiloMinderbinder

Je pense que la définition de

empêchera cela de se produire en premier lieu, car elle devrait également tenir compte des rendements futurs.

V

$V$

Flying_Banana

La question serait alors: pourquoi

existe-t-il? Vous ne pouvez pas contourner le théorème du point fixe de Banach :-)

q_{*}

$q_*$

Fabian Werner

L'existence d'une politique optimale n'est pas évidente. Pour voir pourquoi, notez que la fonction de valeur ne fournit qu'un ordre partiel sur l'espace des stratégies. Ça signifie:

π^{'} \geq π ⟺ v_{π^{'}} (s) \geq v_{π} (s), \forall s \in S

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

Comme il ne s'agit que d'un ordre partiel, il pourrait y avoir un cas où deux politiques, et , ne sont pas comparables. En d'autres termes, il existe des sous-ensembles de l'espace d'état, et tels que: $\pi_1$ $\pi_2$ $S_1$ $S_2$

v_{π^{'}} (s) \geq v_{π} (s), \forall s \in S_{1}

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

v_{π} (s) \geq v_{π^{'}} (s), \forall s \in S_{2}

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

Dans ce cas, nous ne pouvons pas dire qu'une politique est meilleure que l'autre. Mais si nous avons affaire à des MDP finis avec des fonctions de valeur bornées, un tel scénario ne se produit jamais. Il existe exactement une fonction de valeur optimale, bien qu'il puisse exister plusieurs politiques optimales.

Pour en avoir la preuve, vous devez comprendre le théorème du point fixe de Banach. Pour une analyse détaillée, veuillez vous référer .

Karthik Thiagarajan
la source

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

Réglage

Nous envisageons dans le cadre de:

Actions discrètes
États discrets
Récompenses illimitées
Politique stationnaire
Horizon infini

La politique optimale est définie comme: et la fonction de valeur optimale est: Il peut y avoir un ensemble des politiques qui atteignent le maximum. Mais il n'y a qu'une seule fonction de valeur optimale:

\begin{matrix} (1) & π^{*} \in \arg max_{π} V^{π} (s), \forall s \in S \end{matrix}

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

\begin{matrix} (2) & V^{*} = max_{π} V^{π} (s), \forall s \in S \end{matrix}

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

\begin{matrix} (3) & V^{*} = V^{π^{*}} \end{matrix}

$V^\ast = V^{\pi^\ast} \tag{3}$

La question

Comment prouver qu'il existe au moins un qui satisfait (1) simultanément pour tout ? $\pi^\ast$ $s \in \mc{S}$

Aperçu de la preuve

Construire l' équation optimale à utiliser comme définition de substitution temporaire de la fonction de valeur optimale, dont nous prouverons à l'étape 2 qu'elle est équivalente à la définition via l'équation (2).
$\begin{matrix} (4) & V^{*} (s) = max_{a \in A} [R (s, a) + γ \sum_{s^{'} \in S} T (s, a, s^{'}) V^{*} (s^{'})] \end{matrix}$ $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}$
Dérivez l'équivalence de la définition de la fonction de valeur optimale via l'équation (4) et via l'équation (2).

(Notez en fait que nous n'avons besoin que de la direction de nécessité dans la preuve, car la suffisance est évidente puisque nous avons construit l'équation (4) à partir de l'équation (2).)
Démontrer qu'il existe une solution unique à l'équation (4).
Par l'étape 2, nous savons que la solution obtenue à l'étape 3 est également une solution à l'équation (2), c'est donc une fonction de valeur optimale.
À partir d'une fonction de valeur optimale, nous pouvons récupérer une politique optimale en choisissant l'action de maximisation dans l'équation (4) pour chaque état.

Détails des étapes

Puisque , nous avons . Et s'il y a des tels que $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$

(=>)

Suit l'étape 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)]$ , then $\tilde V(s) = V^\ast(s) = \max_\pi V^\pi(s), \forall s \in \mc S$ .

Define the optimal Bellman operator as

\begin{matrix} (5) & T V (s) = max_{a \in A} [R (s, a) + γ \sum_{s^{'} \in S} T (s, a, s^{'}) V (s^{'})] \end{matrix}

$\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} = T \tilde{V}

$\tilde V = \mc T \tilde V$ , then

\tilde{V} = V^{*}

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

For any $\pi = (d_1, d_2, ...)$ ,

\begin{aligned} \tilde{V} & \geq T \tilde{V} = max_{d} [R_{d} + γ P_{d} \tilde{V}] \\ \geq R_{d_{1}} + γ P_{d_{1}} \tilde{V} \end{aligned}

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

$d$ is the decision rule(action profile at specific time),

R_{d}

$R_d$ is the vector representation of immediate reward induced from

d

$d$ and

P_{d}

$P_d$ is transition matrix induced from

d

$d$ .

By induction, for any $n$ ,

\tilde{V} \geq R_{d_{1}} + \sum_{i = 1}^{n - 1} γ^{i} P_{π}^{i} R_{d_{i + 1}} + γ^{n} P_{π}^{n} \tilde{V}

$\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_{π}^{j}

$P_\pi^j$ represents the

j

$j$ -step transition matrix under

π

$\pi$ .

Since

V^{π} = R_{d_{1}} + \sum_{i = 1}^{\infty} γ^{i} P_{π}^{i} R_{d_{i + 1}}

$V^\pi = R_{d_1} + \sum_{i=1}^{\infty}\gamma^i P_\pi^i R_{d_{i+1}}$ we have

\tilde{V} - V^{π} \geq \underset{\to 0 as n \to \infty}{\underset{⏟}{γ^{n} P_{π}^{n} \tilde{V} - \sum_{i = n}^{\infty} γ^{i} P_{π}^{i} R_{d_{i + 1}}}}

$\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} \geq V^{π}

$\tilde V \ge V^\pi$ . And since this holds for any

π

$\pi$ , we conclude that

\tilde{V} \geq max_{π} V^{π} = V^{*}

$\tilde V \ge \max_\pi V^\pi = V^\ast$ b)

Follows from step 1.

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

Proof: For any $s$ ,

\begin{aligned} | T V_{1} (s) - T V_{2} (s) | & = | max_{a \in A} [R (s, a) + γ \sum_{s^{'} \in S} T (s, a, s^{'}) V_{1} (s^{'})] - max_{a^{'} \in A} [R (s, a^{'}) + γ \sum_{s^{'} \in S} T (s, a^{'}, s^{'}) V (s^{'})] | \\ \overset{(*)}{\leq} | max_{a \in A} [γ \sum_{s^{'} \in S} T (s, a, s^{'}) (V_{1} (s^{'}) - V_{2} (s^{'}))] | \\ \leq γ ‖ V_{1} - V_{2} ‖_{\infty} \end{aligned}

$\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^{'}} g (a^{'}) \leq max_{a} [f (a) - g (a)]

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

LoveIris
la source