Ecuación de Bellman

AjustarCompartirImprimirCitar

Condición necesaria para la óptimaidad asociada a la programación dinámica

A Ecuación de Bellman, nombrado por Richard E. Bellman, es una condición necesaria para la optimización asociada con el método de optimización matemática conocido como programación dinámica. Escribe el "valor" de un problema de decisión en un momento determinado en términos del pago de algunas opciones iniciales y el "valor" del problema de decisión restante que resulta de esas elecciones iniciales. Esto rompe un problema de optimización dinámica en una secuencia de subproblemas más simples, como prescribe el “principio de la optimización” de Bellman. La ecuación se aplica a las estructuras algebraicas con un orden total; para las estructuras algebraicas con un orden parcial, la ecuación genérica de Bellman se puede utilizar.

La ecuación de Bellman se aplicó por primera vez a la teoría del control de ingeniería y a otros temas de matemáticas aplicadas, y posteriormente se convirtió en una herramienta importante en la teoría económica; aunque los conceptos básicos de la programación dinámica están prefigurados en la Teoría de los juegos y el comportamiento económico de John von Neumann y Oskar Morgenstern y en el análisis secuencial de Abraham Wald. El término 'ecuación de Bellman' Generalmente se refiere a la ecuación de programación dinámica asociada con problemas de optimización en tiempo discreto. En los problemas de optimización en tiempo continuo, la ecuación análoga es una ecuación diferencial parcial que se denomina ecuación de Hamilton-Jacobi-Bellman.

En tiempo discreto, cualquier problema de optimización de múltiples etapas se puede resolver analizando la ecuación de Bellman adecuada. La ecuación de Bellman adecuada se puede encontrar introduciendo nuevas variables de estado (aumento de estado). Sin embargo, el problema de optimización de múltiples etapas de estado aumentado resultante tiene un espacio de estado dimensional más alto que el problema de optimización de múltiples etapas original, un problema que potencialmente puede hacer que el problema aumentado sea intratable debido a la "maldición de la dimensionalidad". Alternativamente, se ha demostrado que si la función de costos del problema de optimización de múltiples etapas satisface una función "separable hacia atrás" estructura, entonces se puede encontrar la ecuación de Bellman apropiada sin aumento de estado.

Conceptos analíticos en programación dinámica

Para comprender la ecuación de Bellman, se deben comprender varios conceptos subyacentes. Primero, cualquier problema de optimización tiene algún objetivo: minimizar el tiempo de viaje, minimizar el costo, maximizar las ganancias, maximizar la utilidad, etc. La función matemática que describe este objetivo se llama función objetivo.

La programación dinámica rompe un problema de planificación de varios períodos en pasos más simples en diferentes puntos en el tiempo. Por lo tanto, es necesario seguir de cerca la evolución de la situación de la decisión con el tiempo. La información sobre la situación actual que se necesita para tomar una decisión correcta se llama el "estado". Por ejemplo, para decidir cuánto consumir y gastar en cada momento, la gente necesita saber (entre otras cosas) su riqueza inicial. Por lo tanto, la riqueza ${displaystyle (W)}$ sería uno de sus variables estatales, pero probablemente habría otros.

Las variables elegidas en un momento dado a menudo se denominan variables de control. Por ejemplo, dada su riqueza actual, la gente podría decidir cuánto consumir ahora. Elegir las variables de control ahora puede equivaler a elegir el siguiente estado; De manera más general, el siguiente estado se ve afectado por otros factores además del control actual. Por ejemplo, en el caso más simple, la riqueza (el Estado) y el consumo (el control) de hoy podrían determinar exactamente la riqueza de mañana (el nuevo Estado), aunque normalmente otros factores afectarán la riqueza de mañana (el nuevo Estado). riqueza también.

El enfoque dinámico de programación describe el plan óptimo mediante la búsqueda de una regla que diga qué deben ser los controles, dada cualquier posible valor del estado. Por ejemplo, si el consumo (cDepende. sólo sobre la riquezaW), buscaríamos una regla ${displaystyle c(W)}$ que da consumo como una función de riqueza. Tal regla, determinando los controles como función de los estados, se llama una función normativa.

Finalmente, por definición, la regla de decisión óptima es la que alcanza el mejor valor posible del objetivo. Por ejemplo, si alguien elige el consumo, la riqueza dada, para maximizar la felicidad (asumiendo la felicidad H puede ser representado por una función matemática, como una función de utilidad y es algo definido por la riqueza), entonces cada nivel de riqueza se asociará con algún nivel más alto posible de felicidad, ${displaystyle H(W)}$ . El mejor valor posible del objetivo, escrito como función del estado, se llama el función de valor.

Bellman demostró que un problema de optimización dinámica en tiempo discreto se puede plantear de forma recursiva, paso a paso, conocida como inducción hacia atrás, escribiendo la relación entre la función de valor en un período y la función de valor en el siguiente período. . La relación entre estas dos funciones de valor se denomina "ecuación de Bellman". En este enfoque, la política óptima en el último período se especifica de antemano como una función del valor de la variable de estado en ese momento, y el valor óptimo resultante de la función objetivo se expresa así en términos de ese valor de la variable de estado. A continuación, la optimización del penúltimo período implica maximizar la suma de la función objetivo específica de ese período y el valor óptimo de la función objetivo futura, dando la contingencia de política óptima de ese período. sobre el valor de la variable de estado a partir de la decisión del penúltimo período. Esta lógica continúa recursivamente en el tiempo, hasta que se deriva la regla de decisión del primer período, como una función del valor de la variable de estado inicial, optimizando la suma de la función objetivo específica del primer período y el valor de la función objetivo específica del primer período y el valor de la variable de estado inicial. s función de valor, que da el valor de todos los períodos futuros. Por lo tanto, la decisión de cada período se toma reconociendo explícitamente que todas las decisiones futuras se tomarán de manera óptima.

Derivación

Un problema de decisión dinámica

Vamos. ${displaystyle x_{t}}$ ser el estado a la vez ${displaystyle t}$ . Para una decisión que comienza en el momento 0, tomamos como dado el estado inicial ${displaystyle x_{0}}$ . En cualquier momento, el conjunto de posibles acciones depende del estado actual; lo expresamos como ${displaystyle a_{t}in Gamma (x_{t})}$ , donde una acción particular ${displaystyle a_{t}}$ representa valores particulares para una o más variables de control, y ${displaystyle Gamma (x_{t})}$ es el conjunto de acciones disponibles para ser tomadas en el estado ${displaystyle x_{t}}$ . También suponemos que el estado cambia de ${displaystyle x}$ a un nuevo estado ${displaystyle T(x,a)}$ cuando la acción ${displaystyle a}$ se toma y que el pago actual de la adopción de medidas ${displaystyle a}$ en estado ${displaystyle x}$ es ${displaystyle F(x,a)}$ . Finalmente, asumimos impaciencia, representada por un factor de descuento $<math alttext="{displaystyle 0<beta 0c)β β c)1{displaystyle 0 . <img alt="{displaystyle 0<beta$ .

Bajo estas suposiciones, un problema de decisión infinita-horizona toma la siguiente forma:

{displaystyle V(x_{0});=;max _{left{a_{t}right}_{t=0}^{infty }}sum _{t=0}^{infty }beta ^{t}F(x_{t},a_{t}),}

sujetos a las limitaciones

{displaystyle a_{t}in Gamma (x_{t}),;x_{t+1}=T(x_{t},a_{t}),;forall t=0,1,2,dots }

Note que hemos definido notación ${displaystyle V(x_{0})}$ denotar el valor óptimo que se puede obtener al máximo esta función objetiva sujeta a las restricciones asumidas. Esta función es la función de valor. Es una función de la variable estado inicial ${displaystyle x_{0}}$ , ya que el mejor valor obtenido depende de la situación inicial.

Principio de optimización de Bellman

El método de programación dinámica divide este problema de decisión en subproblemas más pequeños. El principio de optimización de Bellman describe cómo hacer esto:

Principio de Optimality: Una política óptima tiene la propiedad de que cualquiera que sea el estado inicial y la decisión inicial, las decisiones restantes deben constituir una política óptima con respecto al estado resultante de la primera decisión. (Ver Bellman, 1957, Chap. III.3.)

En informática, se dice que un problema que se puede dividir de esta manera tiene una subestructura óptima. En el contexto de la teoría dinámica de juegos, este principio es análogo al concepto de equilibrio perfecto en subjuegos, aunque lo que constituye una política óptima en este caso está condicionado a que los oponentes de quienes toman las decisiones elijan políticas óptimas similares desde sus puntos de vista. .

Como sugirió el Secretario General principio de la optimización, vamos a considerar la primera decisión por separado, dejando a un lado todas las decisiones futuras (vamos a empezar de nuevo del tiempo 1 con el nuevo estado ${displaystyle x_{1}}$ ). Recopilar las futuras decisiones entre corchetes sobre la derecha, el problema de decisión infinito es equivalente a:

{displaystyle max _{a_{0}}left{F(x_{0},a_{0})+beta left[max _{left{a_{t}right}_{t=1}^{infty }}sum _{t=1}^{infty }beta ^{t-1}F(x_{t},a_{t}):a_{t}in Gamma (x_{t}),;x_{t+1}=T(x_{t},a_{t}),;forall tgeq 1right]right}}

sujetos a las limitaciones

{displaystyle a_{0}in Gamma (x_{0}),;x_{1}=T(x_{0},a_{0}).}

Aquí estamos eligiendo ${displaystyle a_{0}}$ , sabiendo que nuestra elección hará que el tiempo 1 estado sea ${displaystyle x_{1}=T(x_{0},a_{0})}$ . Ese nuevo estado entonces afectará el problema de decisión a partir del momento 1 en adelante. Todo el problema de la decisión futura aparece dentro de los corchetes de la derecha.

La ecuación de Bellman

Hasta ahora parece que sólo hemos hecho el problema más feo separando la decisión de hoy de futuras decisiones. Pero podemos simplificar notando que lo que está dentro de los corchetes de la derecha es el valor del tiempo 1 problema de decisión, a partir del estado ${displaystyle x_{1}=T(x_{0},a_{0})}$ .

Por lo tanto, podemos reescribir el problema como una definición recursiva de la función de valor:

{displaystyle V(x_{0})=max _{a_{0}}{F(x_{0},a_{0})+beta V(x_{1})}}

, sujeto a las limitaciones:

{displaystyle a_{0}in Gamma (x_{0}),;x_{1}=T(x_{0},a_{0}).}

Esta es la ecuación de Bellman. Se puede simplificar aún más si eliminamos los subíndices de tiempo e ingresamos el valor del siguiente estado:

{displaystyle V(x)=max _{ain Gamma (x)}{F(x,a)+beta V(T(x,a))}.}

La ecuación Bellman se clasifica como una ecuación funcional, porque resolverlo significa encontrar la función desconocida ${displaystyle V}$ , que es el función de valor. Recordemos que la función de valor describe el mejor valor posible del objetivo, como función del estado ${displaystyle x}$ . Al calcular la función de valor, también encontraremos la función ${displaystyle a(x)}$ que describe la acción óptima como función del estado; esto se llama función normativa.

En un problema estocástico

En el entorno determinista, se pueden utilizar otras técnicas además de la programación dinámica para abordar el problema de control óptimo anterior. Sin embargo, la Ecuación Bellman es a menudo el método más conveniente para resolver estocástico problemas de control óptimos.

Para un ejemplo específico de la economía, considere un consumidor con una dotación de riqueza inicial ${displaystyle {color {Red}a_{0}}}$ período de sesiones ${displaystyle 0}$ . Tienen una función de utilidad instantánea ${displaystyle u(c)}$ Donde ${displaystyle c}$ denota consumo y descuentos la utilidad del próximo período a una tasa $<math alttext="{displaystyle 0<beta 0c)β β c)1{displaystyle 0 . <img alt="{displaystyle 0<beta$ . Supongamos que lo que no se consume en el período ${displaystyle t}$ lleva al siguiente período con tasa de interés ${displaystyle r}$ . Entonces el problema de maximización de la utilidad del consumidor es elegir un plan de consumo ${displaystyle {{color {OliveGreen}c_{t}}}}$ que resuelve

{displaystyle max sum _{t=0}^{infty }beta ^{t}u({color {OliveGreen}c_{t}})}

sujeto a

{displaystyle {color {Red}a_{t+1}}=(1+r)({color {Red}a_{t}}-{color {OliveGreen}c_{t}}),;{color {OliveGreen}c_{t}}geq 0,}

{displaystyle lim _{trightarrow infty }{color {Red}a_{t}}geq 0.}

La primera restricción es la acumulación de capital/ley de movimiento especificada por el problema, mientras que la segunda restricción es una condición de transversalidad de que el consumidor no tiene deuda al final de su vida. La ecuación de Bellman es

{displaystyle V(a)=max _{0leq cleq a}{u(c)+beta V((1+r)(a-c))},}

Alternativamente, se puede tratar el problema de secuencia usando directamente, por ejemplo, las ecuaciones Hamiltonianas.

Ahora, si la tasa de interés varía de período a período, el consumidor se enfrenta a un problema de optimización estocástica. Dejar el interés r seguir un proceso de Markov con función de transición de probabilidad ${displaystyle Q(r,dmu _{r})}$ Donde ${displaystyle dmu _{r}}$ denota la medida de probabilidad que rige la distribución de la tasa de interés el próximo período si la tasa de interés actual es ${displaystyle r}$ . En este modelo el consumidor decide su consumo de período actual después de que se anuncia la tasa de interés del período actual.

En lugar de simplemente elegir una sola secuencia ${displaystyle {{color {OliveGreen}c_{t}}}}$ , el consumidor ahora debe elegir una secuencia ${displaystyle {{color {OliveGreen}c_{t}}}}$ para cada posible realización de un ${displaystyle {r_{t}}}$ de tal manera que su utilidad esperada de por vida se maximice:

{displaystyle max _{left{c_{t}right}_{t=0}^{infty }}mathbb {E} {bigg (}sum _{t=0}^{infty }beta ^{t}u({color {OliveGreen}c_{t}}){bigg)}.}

Las expectativas ${displaystyle mathbb {E} }$ se adopta con respecto a la medida de probabilidad apropiada dada por Q sobre las secuencias de r's. Porque... r se rige por un proceso de Markov, la programación dinámica simplifica significativamente el problema. Entonces la ecuación Bellman es simplemente:

{displaystyle V(a,r)=max _{0leq cleq a}{u(c)+beta int V((1+r)(a-c),r')Q(r,dmu _{r})}.}

Bajo algún supuesto razonable, la función de política óptima resultante g()a,rEs mensurable.

Para un problema general de optimización secuencial estocástica con choques markovianos y donde el agente se enfrenta a su decisión ex-post, la ecuación de Bellman toma una forma muy similar

{displaystyle V(x,z)=max _{cin Gamma (x,z)}{F(x,c,z)+beta int V(T(x,c),z')dmu _{z}(z')}.}

Métodos de solución

El método de los coeficientes indeterminados, también conocido como 'ciegos y verificar', se puede utilizar para resolver algunas ecuaciones de Bellman autónomas y de caballos infinitos.
La ecuación de Bellman se puede resolver por inducción atrasada, ya sea analíticamente en algunos casos especiales, o numéricamente en un ordenador. La inducción numérica atrasada es aplicable a una amplia variedad de problemas, pero puede ser infeasible cuando hay muchas variables estatales, debido a la maldición de la dimensionalidad. La programación dinámica aproximada ha sido introducida por D. P. Bertsekas y J. N. Tsitsiklis con el uso de redes neuronales artificiales (perceptros multicapas) para aproximar la función Bellman. Esta es una estrategia eficaz de mitigación para reducir el impacto de la dimensionalidad reemplazando la memorización de la asignación completa de funciones para todo el dominio espacial con la memorización de los únicos parámetros de red neuronales. En particular, para sistemas de tiempo continuo, se introdujo un enfoque de programación dinámica aproximado que combina las iteraciones normativas con las redes neuronales. En tiempo discreto, se introdujo un enfoque para resolver la ecuación HJB que combina las iteraciones de valor y las redes neuronales.
Al calcular las condiciones de primer orden asociadas con la ecuación de Bellman, y luego utilizando el teorema de sobre para eliminar los derivados de la función de valor, es posible obtener un sistema de ecuaciones de diferencia o ecuaciones diferenciales llamadas "Euler ecuaciones". Las técnicas estándar para la solución de diferencia o ecuaciones diferenciales pueden utilizarse para calcular la dinámica de las variables estatales y las variables de control del problema de optimización.

Aplicaciones en economía

La primera aplicación conocida de una ecuación de Bellman en economía se debe a Martin Beckmann y Richard Muth. Martin Beckmann también escribió extensamente sobre la teoría del consumo utilizando la ecuación de Bellman en 1959. Su trabajo influyó en Edmund S. Phelps, entre otros.

Una famosa aplicación económica de una ecuación de Bellman es el artículo seminal de Robert C. Merton de 1973 sobre el modelo de precios de activos de capital intertemporal. (Ver también el problema de cartera de Merton). La solución al modelo teórico de Merton, en el que los inversores eligieron entre los ingresos actuales y futuros ingresos o ganancias de capital, es una forma de ecuación de Bellman. Debido a que las aplicaciones económicas de la programación dinámica generalmente resultan en una ecuación de Bellman que es una ecuación de diferencia, los economistas se refieren a la programación dinámica como un "método recursivo" y un subcampo de economía recursiva ahora se reconoce dentro de la economía.

Nancy Stokey, Robert E. Lucas y Edward Prescott describen la programación dinámica estocástica y no estocástica con considerable detalle y desarrollan teoremas para la existencia de soluciones a problemas que cumplen ciertas condiciones. También describen muchos ejemplos de modelización de problemas teóricos en economía utilizando métodos recursivos. Este libro condujo al empleo de la programación dinámica para resolver una amplia gama de problemas teóricos en economía, incluido el crecimiento económico óptimo, la extracción de recursos, los problemas principal-agente, las finanzas públicas, la inversión empresarial, la fijación de precios de activos, la oferta de factores y la organización industrial. Lars Ljungqvist y Thomas Sargent aplican la programación dinámica para estudiar una variedad de cuestiones teóricas en política monetaria, política fiscal, impuestos, crecimiento económico, teoría de búsqueda y economía laboral. Avinash Dixit y Robert Pindyck demostraron el valor del método para pensar en el presupuesto de capital. Anderson adaptó la técnica a la valoración de empresas, incluidas las empresas privadas.

El uso de programación dinámica para resolver problemas concretos se complica por dificultades informativas, como la elección de la tasa de descuento no observable. También hay problemas computacionales, el principal es la maldición de la dimensionalidad que surge de la gran cantidad de acciones posibles y variables de estado potenciales que deben considerarse antes de poder seleccionar una estrategia óptima. Para una discusión extensa sobre cuestiones computacionales, ver Miranda y Fackler, y Meyn 2007.

Ejemplo

En los procesos de decisión de Markov, una ecuación de Bellman es una repetición de recompensas esperadas. Por ejemplo, la recompensa esperada por estar en un estado particular s y siguiendo algunas políticas fijas ${displaystyle pi }$ tiene la ecuación de Bellman:

{displaystyle V^{pi }(s)=R(s,pi (s))+gamma sum _{s'}P(s'|s,pi (s))V^{pi }(s'). }

Esta ecuación describe la recompensa esperada por tomar la acción prescrita por alguna política ${displaystyle pi }$ .

La ecuación para la política óptima se conoce como ecuación de optimización de Bellman:

{displaystyle V^{pi *}(s)=max _{a}left{{R(s,a)+gamma sum _{s'}P(s'|s,a)V^{pi *}(s')}right}. }

Donde ${displaystyle {pi *}}$ es la política óptima y ${displaystyle V^{pi *}}$ se refiere a la función de valor de la política óptima. La ecuación anterior describe la recompensa por tomar la acción dando el retorno esperado más alto.

Contenido relacionado

Más resultados...