DEFINICNI OBORY
\section{Formulace �lohy stochastick�ho ��zen�}
�st�edn�m pojmem v teorii ��zen� je \emph{syst�m}. Syst�m je ��st sv�ta, kterou chceme poznat �i ��dit. Budeme-li p�edpokl�dat diskr�tn� povahu �asu, stav syst�mu v �asov�m okam�iku $t$ pod�l ��d�c�ho horizontu d�lky $N$ popisuje syst�m rovnic
\begin{equation}
\label{sys}
x_{t+1}=f_k(x_t,u_t,w_t), \qquad t=0,1,\ldots,N-1,
\end{equation}
kde $x_t$ je stav syst�mu v �ase $t$, $u_t$ je vstup v �ase $t$ a $w_t$ n�hodn� veli�ina reprezentuj�c� p��tomnost �umu. V t�to kapitole budeme p�edpokl�dat, �e m��eme stav syst�mu pozorovat. P��padem ne�pln�ho pozorov�n� se zab�v� n�sleduj�c� kapitola. 

V �loze ��zen� m�me v�dy p�edepsanou ztr�tovou (resp. ��elovou) funkci
\begin{equation}
g(x_{1:N},u_{0:N-1}).
\end{equation}

Ozna�me $U(x_t)$ mno�inu p��pustn�ch ��d�c�ch z�sah� pro syst�m ve stavu $x_t$. P��pustnou ��d�c� strategi� $\pi=\mu_{0:N-1}$ budeme rozum�t posloupnost zobrazen�
\begin{equation}
\label{con}
\mu_t(x_t)=u_t \, \qquad t=0,1,\ldots,N-1,
\end{equation}
kde $u_t \in U(x_t)$ je p��pustn� ��d�c� z�sah.

Pro danou ��d�c� strategii ozna�me o�ek�vanou ztr�tu jako
\begin{equation}
\label{los}
J_\pi(x_0)=\E_{w_{0:N-1}}\left\{g(x_{1:N},\mu_{0:N-1}(x_{0:N-1}))\right\}.
\end{equation}

�lohou je potom naj�t takovou $\pi^*$, pro kterou plat�
\begin{equation}
J_{\pi^*}(x_0)=\min_{\pi \in \Pi}J_\pi(x_0),
\end{equation}
kde $\Pi$ zna�� mno�inu v�ech p��pustn�ch ��d�c�ch strategi�.

Celkov� se tedy jedn� o optimaliza�n� �lohu nal�zt takovou posloupnost funkc� \eqref{con}, kter� minimalizuje o�ek�vanou ztr�tovu \eqref{los} za podm�nek \eqref{sys}.

\section{Pou�it� dynamick�ho programov�n� p�i �e�en� �lohy stochastick�ho ��zen� s aditivn� ztr�tou}
�lohu stochastick�ho ��zen� tak, jak byla definov�na v p�edchoz� ��sti, nelze obecn� �e�it. Je tedy pot�eba �lohu n�jak bl�e specifikovat. V tomto sm�ru je mo�n� omezit se na n�jak� speci�ln� tvar ztr�tov� funkce \eqref{los}. Jako vhodn� se ukazuje uva�ovat tzv. aditivn� tvar ztr�tov� funkce, tedy �e existuj� funkce $g_t$ takov�, �e m��eme ps�t
\begin{equation}
\label{adi}
g(x_{1:N},u_{0:N-1})=\sum_{t=1}^{N-1}g_t(x_{t+1},u_t).
\end{equation}

O�ek�vanou ztr�tu \eqref{los} potom m��eme p�epsat do tvaru
\begin{equation}
J_\pi(x_0)=\E_{w_{0:N-1}}\left\{\sum_{t=0}^{N-1}g_t(x_{t+1},\mu_t(x_t))\right\}.
\end{equation}

Takto specifikovan� �loha se d� �e�it pou�it�m dynamick�ho programov�n� \cite{bellman1957dynamic}. Dynamick� programov�n� je p��stup k �e�en� optimaliza�n�ch �loh, na kter� se m��eme d�vat jako na posloupnost rozhodnut�, pro kter� plat� tzv. princip optimality.  Ten ��k�, �e optim�ln� posloupnost rozhodnut� m� tu vlastnost, �e pro libovoln� po��te�n� stav a rozhudnut� mus� b�t v�echna n�sleduj�c� rozhodnut� optim�ln� vzhledem k v�sledk�m rozhodnut� prvn�ho. D�kaz, �e pro ztr�tu tvaru \eqref{adi} plat� princip optimality je snadn� a lze ho nal�zt nap��klad v \cite{bertsekas1995dynamic}.

P�i �e�en� �lohy stochastick�ho ��zen� s aditivn� ztr�tou je tedy mo�n� postupovat, jak je u �loh �e�en�ch pomoc� dynamick�ho programov�n� zvykem. Minim�ln� hodnotu st�edn� ztr�ty od okam�iku $t$ do $N$ v z�vislosti na $x_t$ ozna��me $J_t(x_t)$. M��eme pro ni ps�t
\begin{gather}
J_N(x_N)=0\\
J_t(x_t)=\min_{u_t \in U(x_t)}\E_{w_t}\left\{g_k(x_{t+1},u_t)+J_{t+1}(x_{t+1})\right\} \qquad t=0,\ldots,N-1.
\end{gather}

P�� �e�en� budeme postupovat od konce ��d�c�ho horizontu a postupn� hledat $J_t(x_t)$. Pro v�po�et $x_{t+1}$ se pou�ije rovnice \eqref{sys}. 
Libovolnou ��d�c� strategii $\pi=\{\mu_0,\ldots,\mu_{N-1}\}$, kter� spl�uje syst�m rovnic
\begin{equation}
\label{impl}
J_t(x_t)=\E_{w_t}\left\{g_k(x_t,\mu_t(x_t),w_t)+J_{t+1}(f_t(x_t,\mu_t(x_t),w_t))\right\} \qquad t=0,\ldots,N-1
\end{equation}
pak nazveme optim�ln� posloupnost� rozhodnut�.