Bellmanova rovnice

Bellmanova rovnice pojmenovaná podle svého autora Richarda Bellmana, je nutná podmínka optimality matematické optimalizační metody známé jako dynamické programování. Určuje „hodnotu“ rozhodovacího problému v určitém časovém okamžiku podle výplaty závislé na nějakých počátečních rozhodnutích a „hodnoty“ zbývajícího rozhodovacího problému, který vyplývá z těchto počátečních rozhodnutí. Tím se dynamický optimalizační problém rozloží na posloupnost jednodušších podproblémů, jak popisuje „Bellmanův princip optimality“.

Bellmanova rovnice byla nejdříve aplikována na inženýrskou teorii řízení a různé obory užité matematiky, poté se stala důležitým nástrojem v ekonomické teorii; základní koncepty dynamického programování jsou však popsány již v pracích Theory of Games and Economic Behavior Johna von Neumanna a Oskara Morgensterna a Sequential analysis Abrahama Walda.

Téměř jakýkoli problém, který lze vyřešit pomocí teorie optimálního řízení může také být vyřešený analýzou určité Bellmanovy rovnice. Termín 'Bellmanova rovnice' se obvykle používá pro rovnici dynamického programování popisující optimalizační problém v diskrétním čase. Analogickou roli pro optimalizační problémy ve spojitém čase hraje parciální diferenciální rovnice, která se obvykle nazývá Hamiltonova–Jacobiho–Bellmanova rovnice.

Analytické koncepty v dynamickém programování

Pro pochopení Bellmanovy rovnice je třeba znát několik základních pojmů. Prvním z nich je, že každý optimalizační problém má určitý cíl, jímž může být minimalizace doby trvání cesty, minimalizace ceny, maximalizace zisku, maximalizace užitku, atd. Matematické funkce, která popisuje tento cíl, se nazývá účelová funkce (anglicky objective function).

Dynamické programování rozkládá několikaetapové rozhodovací procesy na řadu postupných rozhodnutí. Proto vyžaduje naustálé sledování, jak se situace vyvíjí v čase. Informace o aktuální situaci, které jsou nutné pro optimální rozhodnutí, se nazývají „stav“. Například pro rozhodnutí, jaké množství určitého statku (majetku) spotřebovat a jaké vynaložit v příslušné časové etapě, je potřeba znát (mimo jiné) počáteční množství majetku. Proto majetek $(W)$ bude jedna ze stavových proměných, ale pravděpodobně budou existovat i další stavové proměnné.

Proměnné zvolené při rozhodnutí v každé časové etapě se obvykle nazývají řídicí proměnné. Je-li například dán výchozí majetek určité osoby, může se tato osoba rozhodovat, jak velkou jeho část v aktuální etapě spotřebovat. Aktuální volba hodnoty řídicí proměnné může být ekvivalentní s výběrem dalšího stavu; obecně však může být další stav ovlivněn i jinými faktory než aktuální hodnotou řídicí proměnné. Například v nejjednodušším případě dnešní majetek (stav) a spotřeba (hodnota řídicí proměnné) může jednoznačně určovat zítřejší majetek (nový stav), i když typicky budou zítřejší majetek ovlivňovat i jiné faktory.

Přístup dynamického programování popisuje optimální plán hledáním pravidla, které říká, jaké mají být hodnoty řídicích proměnných v každé etapě pro libovolnou hodnotu stavu. Například jestliže spotřeba (c) závisí pouze na majetku (W), hledáme pravidlo $c(W)$, které dává spotřebu jako funkci majetku. Takové pravidlo, které určuje hodnotu řídicí proměnné jako funkce stavů, se nazývá řídicí funkce (anglicky policy function, viz Bellman, 1957, Ch. III.2).

Podle definice je optimální rozhodovací pravidlo takové, které zajišťuje nejlepší možnou hodnotu účelové funkce. Pokud například někdo zvolí jako cíl maximalizaci spotřeby při daném majetku, aby maximalizoval spokojenost (za předpokladu, že spokojenost H lze reprezentovat matematickou funkcí, jako je užitková funkce, a že spokojenost je něco definovaný by majetek), pak každá úroveň majetku bude spojena s nějakou nejvyšší možnou úrovní spokojenosti, $H(W)$. Nejlepší možná hodnota účelové funkce, zapsaná jako funkce stavu, se nazývá hodnotová funkce (anglicky value function).

Richard Bellman ukázal, že dynamický optimalizační problém v diskrétním čase lze vyjádřit v rekurzivním tvaru známém jako zpětná indukce, který vyjadřuje vztah mezi hodnotou optimálního řešení úlohy v jedné etapě a její hodnotou v následující etapě. Vztah mezi těmito dvěma hodnotami hodnotové funkce se nazývá „Bellmanova rovnice“. Optimální strategie v poslední časové etapě je u tohoto přístupu zadaná předem jako funkce hodnoty stavové proměnné v této etapě; výsledná optimální hodnota účelové funkce je tedy vyjádřena pomocí této hodnoty stavové proměnné. Optimalizace pro následující etapu znamená maximalizaci součtu aktuální hodnoty účelové funkce a optimální hodnoty budoucí účelové funkce, což dává kontingenci optimální strategie pro tuto etapu v závislosti na hodnotě stavové proměnné jakožto rozhodnutí v následujících etapách. S touto logikou pokračujeme rekurzivně zpět v čase až k odvození rozhodovacího pravidla pro první etapu jako funkce počáteční hodnoty stavové proměnné optimalizací sumy účelové funkce pro první etapu a hodnoty hodnotové funkce pro druhou etapu, která určuje hodnotu pro všechny budoucí etapy. Tedy rozhodnutí pro každou etapu se provede explicitním uznáním, že všechna budoucí rozhodnutí budou učiněna optimálně.

Odvození

Dynamický rozhodovací problém

Stav v čase $t$ budeme značit $x_{t}$. Počáteční stav pro rozhodnutí učiněné v čase 0 je tedy $x_{0}$. Množina akcí možných v libovolném čase závisí na okamžitém stavu; což můžeme psát jako $a_{t}\in \Gamma (x_{t})$, kde akce $a_{t}$ reprezentuje jednu nebo více řídicích proměnných. Také předpokládáme, že se provedením akce $a$ stav změní z $x$ do nového stavu $T(x,a)$, a že současná výplata z provedení akce $a$ ve stavu $x$ je $F(x,a)$. Navíc předpokládáme netrpělivost reprezentovanou diskontním faktorem $0<\beta <1$.

Za těchto předpokladů má rozhodovací problém s nekonečným časovým horizontem následující tvar:

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

při platnosti omezení

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

$V(x_{0})$ označuje optimální hodnotu, kterou lze získat maximalizací této účelové funkce při platnosti uvedených omezení. Tato funkce je hodnotová funkce. Je funkcí počáteční stavové proměnné $x_{0}$, protože nejlepší hodnota, kterou lze získat, závisí na počáteční situaci.

Bellmanův princip optimality

Metoda dynamického programování rozkládá rozhodovací problém na menší podproblémy. Richard Bellman zformuloval princip optimality, který popisuje jak rozklad provést:

Princip optimality: Optimální strategie má tu vlastnost, že ať je počáteční stav a počáteční rozhodnutí jakékoli, zbývající rozhodnutí musí tvořit optimální strategii pro stav, který je výsledkem prvního rozhodnutí. (Viz Bellman, 1957, Chap. III.3.)

O problému, který lze takto rozdělit na podproblémy, říkáme v matematické informatice, že má optimální podstrukturu. V kontextu dynamické teorie her je tento princip obdobou konceptu dokonalé rovnováhy podhry, i když to, z čeho se skládá optimální strategie je v tomto případě podmíněné výběrem optimální (z pohledu protivníků) strategie protivníků.

V souladu s principem optimality budeme uvažovat první rozhodnutí odděleně, bez uvažování všech budoucích rozhodnutí (která začínají etapou 1 ve výchozím stavu $x_{1}$). Budoucí rozhodnutí jsou shrnuta v hranatých závorkách. Předchozí problém je ekvivalentní s:

$\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 t\geq 1\right]\right\}$

při platnosti omezení

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

Zde volíme $a_{0}$, protože víme, že naše rozhodnutí povede do stavu 1, tj. $x_{1}=T(x_{0},a_{0})$. Tento nový stav pak bude ovlivňovat rozhodovací problém od času 1 dále. Celý budoucí rozhodovací problém se objevuje v hranatých závorkách vpravo.

Bellmanova rovnice

Zdá se, že oddělením aktuálního rozhodnutí od budoucích rozhodnutí se problém jenom stal ošklivějším. Pokud si však všimneme, že výraz v hranatých závorkách vpravo je hodnota rozhodovacího problému v čase 1, začínající ze stavu $x_{1}=T(x_{0},a_{0})$.

Proto můžeme rovnici přepsat jako rekurzivní definici hodnotové funkce:

$V(x_{0})=\max _{a_{0}}\{F(x_{0},a_{0})+\beta V(x_{1})\}$, při platnosti omezení: $a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).$

Výsledný tvar nazýváme Bellmanova rovnice. Rovnici můžeme dále zjednodušit vypuštěním časových indexů a použitím hodnoty dalšího stavu:

$V(x)=\max _{a\in \Gamma (x)}\{F(x,a)+\beta V(T(x,a))\}.$

Bellmanova rovnice je funkcionální rovnicí, protože jejím řešením je funkce V, která je hodnotová funkce. Pamatujte, že hodnotová funkce popisuje nejlepší možnou hodnotu účelové funkce jako funkci stavu x. Při výpočtu hodnotové funkce zjistíme také funkci a(x), která popisuje optimální akci jako funkci stavu; tato funkce se nazývá řídicí funkce.

Stochastické problémy

Související informace naleznete také v článku Markovův rozhodovací proces.

V deterministickém prostředí lze pro řešení výše uvedeného problému optimálního řízení použít i jiné techniky než dynamické programování. V případě stochastických problémů optimálního řízení je však Bellmanova rovnice často nejpohodlnější metodou jejich řešení.

Pro konkrétní příklad z ekonomie uvažujme spotřebitele žijícího nekonečnou dobu s počátečním majetkem ${\color {Red}a_{0}}$ v čase $0$. Spotřebitel má okamžitou užitkovou funkci $u(c)$, kde $c$ označuje spotřebu a diskontování užitku v další periodě má velikost $0<\beta <1$. Předpokládejme, že co není spotřebováno v čase $t$ přenáší se do další etapy s úrokovou sazbou $r$. Pak problém maximalizace užitku spotřebitele je vybrat takový plán spotřeby $\{{\color {OliveGreen}c_{t}}\}$, který řeší

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

pro

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

a

$\lim _{t\rightarrow \infty }{\color {Red}a_{t}}\geq 0.$

Prvním omezením je zákon akumulace kapitálu pohybu zadaný problémem, druhým omezením je podmínka transverzality, že spotřebitel nepřenáší dluh na konci svého života. Bellmanova rovnice je

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

Případně můžeme řešit problém posloupnosti přímo například pomocí Hamiltonových rovnic.

Jestliže se nyní v jednotlivých etapách úroková sazba mění, musí spotřebitel řešit stochastický optimalizační problém. Pokud budeme změny sazby r považovat za Markovův proces s funkcí přechodu pravděpodobnosti $Q(r,d\mu _{r})$, kde $d\mu _{r}$ označuje pravděpodobnostní míru řídící výši úrokové sazby na další etapu, jestliže současná úroková sazba je $r$. Časování modelu spočívá v tom, že spotřebitel rozhoduje o své spotřebě v příští etapě po ohlášení úrokové sazby pro tuto etapu.

Místo výběru jediné posloupnosti $\{{\color {OliveGreen}c_{t}}\}$ musí spotřebitel nyní zvolit posloupnost $\{{\color {OliveGreen}c_{t}}\}$ pro každou možnou realizaci $\{r_{t}\}$ takovým způsobem, aby maximalizoval očekávaný užitek pro dobu svého života:

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

Očekávání $\mathbb {E}$ se bere vzhledem k vhodné pravděpodobnostní míře dané Q na posloupnosti r. Protože r je řízeno Markovovým procesem, dynamické programování problém výrazně zjednodušuje. Bellmanova rovnice pak má jednoduchý tvar

$V(a,r)=\max _{0\leq c\leq a}\{u(c)+\beta \int V((1+r)(a-c),r')Q(r,d\mu _{r})\}.$

Za určitého rozumného předpokladu je výsledná optimální řídicí funkce g(a,r) měřitelná.

Pro obecný stochastický sekvenční optimalizační problém s Markovskými změnami, v němž je agent konfrontován se svými rozhodnutími ex-post, přejde Bellmanova rovnice na velmi podobný tvar

$V(x,z)=\max _{c\in \Gamma (x,z)}F(x,c,z)+\beta \int V(T(x,c),z')d\mu _{z}(z').$

Metody řešení

• Metodu neurčitých koeficientů známou také jako 'odhadni a ověř' lze použít pro řešení některých autonomních Bellmanových rovnic s nekonečným horizontem.
• Bellmanovu rovnici lze vyřešit zpětnou indukcí, buď analyticky v několika speciálních případech, nebo numericky na počítači. Numerickou zpětnou indukci lze použít ve velkém množství problémů, ale může být nepoužitelná, když existuje mnoho stavových proměnných, kvůli prokletí dimenzionality. Přibližné dynamické programování zavedli D. P. Bertsekas a J. N. Tsitsiklis s použitím neuronové sítě (vícevrstvých perceptronů) pro aproximaci Bellmanovy funkce. Jde o efektivní strategii pro omezení vlivu dimenzionality nahrazením pamatování kompletního zobrazení na celém definičním oboru pamatováním parametrů jediné neuronové sítě.
• Výpočtem podmínek prvního řádu přiřazených k Bellmanově rovnici a použitím obálkové věty pro odstranění derivací hodnotové funkce je možné získat soustavu diferenčních nebo diferenciálních rovnic zvanou Eulerova-Lagrangeova rovnice. Pro výpočet dynamiky stavových proměnných a řídicích proměnných optimalizačního problému lze pak použít standardní techniky pro řešení diferenčních nebo diferenciálních rovnic.

Aplikace v ekonomii

První známá aplikace Bellmanovy rovnice v ekonomii se přičítá Martin Beckmann a Richard Muth. Martin Beckmann v roce 1959 také široce popsal teorii spotřeby pomocí Bellmanovy rovnice. Jeho dílo mimo jiné ovlivnilo Edmund S. Phelps.

Oslavovanou ekonomickou aplikací Bellmanovy rovnice je podnětný článek Robert C. Mertona z roku 1973 o intertemporálním modelu oceňování kapitálových aktiv. (Viz také Mertonův problém portfolia). Řešení Mertonova teoretického modelu, ve kterém investoři volí mezi příjmem současným a budoucím a kapitálovými zisky, má tvar Bellmanovy rovnice. Protože aplikace dynamického programování v ekenomii obvykle vedou k Bellmanově rovnici, která má tvar diferenční rovnice, ekonomové zpravidla místo názvu dynamické programování používají název „rekurzivní metoda“ a v rámci ekonomie existuje obor rekurzivní ekonomie.

Nancy Stokey, Robert E. Lucas a Edward C. Prescott popsali velmi detailně stochastické a nestochastické dynamické programování a zformulovali věty pro existenci řešení problémů, které splňují určité podmínky. Popsali také mnoho příkladů modelování teoretických problémů v ekonomii pomocí rekurzivních metod. Díky jejich knize se dynamické programování používá pro řešení širokého rozsahu teoretických problémů v ekonomii, včetně optimálního ekonomického růstu, získávání prostředků, Problému vedoucí-agant, veřejné finance, obchodní investice, ocenění majetku, faktor zásob a podniková ekonomika. Lars Ljungqvist a Thomas Sargent aplikovali dynamické programování na studium mnoha teoretických otázek v monetární politice, fiskální politice, zdaňování, hospodářský růst, teorii hledání a pracovní ekonomika. Avinash Dixit a Robert Pindyck ukázali hodnotu metody pro oblast investičních rozpočtů. Anderson upravil techniku pro obchodní valuaci včetně soukromých firem.

Používání dynamického programování pro řešení konkrétních problémů komplikují informační potíže, jako například problém nezjistitelného diskontního faktoru. Existují také výpočetní problémy, z nichž hlavní je prokletí dimenzionality způsobené obrovským množstvím možných akcí a hodnot stavových proměnných, které musí být uvažovány pro výběr optimální strategie. Výpočetní problémy podrobně diskutuje Miranda a Fackler, a Meyn 2007.

Příklad

V Markovových rozhodovacích procesech je Bellmanova rovnice rekurzivním vztahem pro očekávaný výnos. Například pro očekávaný výnos při použití nějaké pevné strategie $\pi$ ve stavu s má Bellmanova rovnice tvar:

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

Tato rovnice popisuje očekávaný výnos provedení akce předepsané nějakou strategií $\pi$.

Rovnice pro optimální strategii se nazývá Bellmanova rovnice optimality:

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

kde ${\pi *}$ je optimální strategie a $V^{\pi *}$ znamená hodnotovou funkci optimální strategie. Výše uvedená rovnice popisuje výnos z provedení akce, která dává nejvyšší očekávaný výnos.

Odkazy

Související články

• Bellmanova pseudospektrální metoda
• Dynamické programování
• Hamiltonova–Jacobiho–Bellmanova rovnice
• Markovův rozhodovací proces
• Teorie optimálního řízení
• Optimální podstruktura
• Rekurzivní kompetitivní rovnováha
• Stochastické dynamické programování

Reference

V tomto článku byl použit překlad textu z článku Bellman equation na anglické Wikipedii.