Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Aprende Condiciones de Optimalidad | Programación Dinámica
Introducción al Aprendizaje por Refuerzo

bookCondiciones de Optimalidad

En el capítulo anterior, aprendiste sobre las ecuaciones de Bellman para las funciones de valor de estado y valor de acción-estado. Estas ecuaciones describen cómo los valores de los estados pueden definirse recursivamente a través de los valores de otros estados, dependiendo de una política dada. Sin embargo, no todas las políticas son igual de efectivas. De hecho, las funciones de valor proporcionan un orden parcial para las políticas, que puede describirse de la siguiente manera:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Así, la política π\pi es mejor o igual que la política π′\pi' si para todos los estados posibles, el retorno esperado de la política π\pi no es menor que el retorno esperado de la política π′\pi'.

Note
Estudia más

Un orden parcial sigue las reglas habituales de ordenamiento pero no obliga a comparar todos los pares. En nuestro caso, solo podemos clasificar dos políticas si producen los mismos resultados, o si una claramente supera a la otra. En todos los demás casos, las políticas permanecen incomparables.

Política Óptima

Note
Definición

Para cualquier MDP, existe al menos una política que es tan buena como, o mejor que, todas las demás políticas. Esta política se denomina política óptima π∗\pi_*. Aunque puede haber muchas políticas óptimas, todas se representan como π∗\pi_*.

¿Por qué siempre existe una política óptima?

Quizás te preguntes por qué siempre existe una política óptima para cualquier MDP. Es una excelente pregunta, y la intuición detrás de esto es sorprendentemente simple. Recuerda que los estados en un MDP capturan completamente la condición del entorno. Esto implica que cada estado es independiente de los demás: la acción elegida en un estado no afecta las recompensas ni los resultados alcanzables en otro. Por lo tanto, al seleccionar la acción óptima en cada estado por separado, se llega naturalmente a la mejor secuencia global de acciones en todo el proceso. Y este conjunto de acciones óptimas en cada estado constituye una política óptima.

Además, siempre existe al menos una política que es tanto óptima como determinista. De hecho, si para algún estado ss, dos acciones aa y a′a' producen el mismo retorno esperado, seleccionar solo una de ellas no afectará la optimalidad de la política. Aplicar este principio en cada estado hará que la política sea determinista sin perder su optimalidad.

Funciones de Valor Óptimas

Las políticas óptimas comparten las mismas funciones de valor — un hecho que se vuelve evidente al considerar cómo se comparan las políticas. Esto significa que las políticas óptimas comparten tanto la función de valor de estado como la función de valor de acción.

Además, las funciones de valor óptimas tienen sus propias ecuaciones de Bellman que pueden escribirse sin hacer referencia a ninguna política específica. Estas ecuaciones se denominan ecuaciones de optimalidad de Bellman.

Función de valor de estado óptima

Note
Definición

La función de valor de estado óptima V∗V_* (o v∗v_*) representa el retorno esperado máximo alcanzable desde un cierto estado siguiendo una política óptima.

Se puede definir matemáticamente de la siguiente manera:

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

La ecuación de optimalidad de Bellman para esta función de valor se puede derivar así:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuición

Como ya se sabe, siempre existe al menos una política que es tanto óptima como determinista. Dicha política, para cada estado, seleccionaría de manera consistente una acción particular que maximiza los retornos esperados. Por lo tanto, la probabilidad de elegir esta acción óptima siempre sería 1, y la probabilidad de elegir cualquier otra acción sería 0. Dado esto, la ecuación de Bellman original ya no necesita el operador de suma. En su lugar, dado que sabemos que siempre se seleccionará la mejor acción posible, simplemente se puede reemplazar la suma tomando un máximo sobre todas las acciones disponibles.

Función de valor óptima de acción

Note
Definición

Función de valor óptima de acción Q∗Q_* (o q∗q_*) representa el retorno esperado máximo que se puede lograr al tomar una determinada acción en un determinado estado y seguir la política óptima posteriormente.

Se puede definir matemáticamente de la siguiente manera:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Ecuación de optimalidad de Bellman para esta función de valor se puede derivar de la siguiente manera:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuición

De manera similar a la función de valor de estado, la suma puede ser reemplazada por tomar el máximo sobre todas las acciones disponibles.

question mark

¿Por qué siempre existe una política óptima para cualquier proceso de decisión de Markov?

Select the correct answer

¿Todo estuvo claro?

¿Cómo podemos mejorarlo?

¡Gracias por tus comentarios!

Sección 3. Capítulo 3

Pregunte a AI

expand

Pregunte a AI

ChatGPT

Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla

Awesome!

Completion rate improved to 2.7

bookCondiciones de Optimalidad

Desliza para mostrar el menú

En el capítulo anterior, aprendiste sobre las ecuaciones de Bellman para las funciones de valor de estado y valor de acción-estado. Estas ecuaciones describen cómo los valores de los estados pueden definirse recursivamente a través de los valores de otros estados, dependiendo de una política dada. Sin embargo, no todas las políticas son igual de efectivas. De hecho, las funciones de valor proporcionan un orden parcial para las políticas, que puede describirse de la siguiente manera:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Así, la política π\pi es mejor o igual que la política π′\pi' si para todos los estados posibles, el retorno esperado de la política π\pi no es menor que el retorno esperado de la política π′\pi'.

Note
Estudia más

Un orden parcial sigue las reglas habituales de ordenamiento pero no obliga a comparar todos los pares. En nuestro caso, solo podemos clasificar dos políticas si producen los mismos resultados, o si una claramente supera a la otra. En todos los demás casos, las políticas permanecen incomparables.

Política Óptima

Note
Definición

Para cualquier MDP, existe al menos una política que es tan buena como, o mejor que, todas las demás políticas. Esta política se denomina política óptima π∗\pi_*. Aunque puede haber muchas políticas óptimas, todas se representan como π∗\pi_*.

¿Por qué siempre existe una política óptima?

Quizás te preguntes por qué siempre existe una política óptima para cualquier MDP. Es una excelente pregunta, y la intuición detrás de esto es sorprendentemente simple. Recuerda que los estados en un MDP capturan completamente la condición del entorno. Esto implica que cada estado es independiente de los demás: la acción elegida en un estado no afecta las recompensas ni los resultados alcanzables en otro. Por lo tanto, al seleccionar la acción óptima en cada estado por separado, se llega naturalmente a la mejor secuencia global de acciones en todo el proceso. Y este conjunto de acciones óptimas en cada estado constituye una política óptima.

Además, siempre existe al menos una política que es tanto óptima como determinista. De hecho, si para algún estado ss, dos acciones aa y a′a' producen el mismo retorno esperado, seleccionar solo una de ellas no afectará la optimalidad de la política. Aplicar este principio en cada estado hará que la política sea determinista sin perder su optimalidad.

Funciones de Valor Óptimas

Las políticas óptimas comparten las mismas funciones de valor — un hecho que se vuelve evidente al considerar cómo se comparan las políticas. Esto significa que las políticas óptimas comparten tanto la función de valor de estado como la función de valor de acción.

Además, las funciones de valor óptimas tienen sus propias ecuaciones de Bellman que pueden escribirse sin hacer referencia a ninguna política específica. Estas ecuaciones se denominan ecuaciones de optimalidad de Bellman.

Función de valor de estado óptima

Note
Definición

La función de valor de estado óptima V∗V_* (o v∗v_*) representa el retorno esperado máximo alcanzable desde un cierto estado siguiendo una política óptima.

Se puede definir matemáticamente de la siguiente manera:

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

La ecuación de optimalidad de Bellman para esta función de valor se puede derivar así:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuición

Como ya se sabe, siempre existe al menos una política que es tanto óptima como determinista. Dicha política, para cada estado, seleccionaría de manera consistente una acción particular que maximiza los retornos esperados. Por lo tanto, la probabilidad de elegir esta acción óptima siempre sería 1, y la probabilidad de elegir cualquier otra acción sería 0. Dado esto, la ecuación de Bellman original ya no necesita el operador de suma. En su lugar, dado que sabemos que siempre se seleccionará la mejor acción posible, simplemente se puede reemplazar la suma tomando un máximo sobre todas las acciones disponibles.

Función de valor óptima de acción

Note
Definición

Función de valor óptima de acción Q∗Q_* (o q∗q_*) representa el retorno esperado máximo que se puede lograr al tomar una determinada acción en un determinado estado y seguir la política óptima posteriormente.

Se puede definir matemáticamente de la siguiente manera:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Ecuación de optimalidad de Bellman para esta función de valor se puede derivar de la siguiente manera:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuición

De manera similar a la función de valor de estado, la suma puede ser reemplazada por tomar el máximo sobre todas las acciones disponibles.

question mark

¿Por qué siempre existe una política óptima para cualquier proceso de decisión de Markov?

Select the correct answer

¿Todo estuvo claro?

¿Cómo podemos mejorarlo?

¡Gracias por tus comentarios!

Sección 3. Capítulo 3
some-alt