A�koliv pou�it� dynamick�ho programov�n� p�in�� v�znamn� pokrok v �e�en� �lohy stochastick�ho ��zen�, analytick� �e�en� obvykle nen� mo�n� z�skat. V ka�d�m �asov�m kroku se toti� pot�k�me se dv�ma obecn� obt�n�mi probl�memy: 1) v�po�et st�edn� hodnoty a 2) minimalizace vzhledem k $u_t$. Oba probl�my obecn� nemaj� analytick� �e�en� a bez dal�� specifikace �lohy je proto t�eba p�ej�t k aproxima�n�m metod�m.

V t�to kapitole se p�edkl�d� popis n�kolika mo�n�ch p��stup� k aproximativn�mu �e�en� �lohy du�ln�ho ��zen�. P��pome�me, �e �lohou du�ln�ho ��zen�  je nalezen� ��d�c� strategie $\pi=\mu_{0:N-1}$, kter� by minimalizovala o�ek�vanou ztr�tu
\begin{equation}
\label{ilos3}
J_\pi=\E_{\theta_0,v_{0:N-1}}\left\{\sum_{t=0}^{N-1}g_t(y_{t+1},\mu_t(H_t))\right\},
\end{equation}
za apriorn� informace $\theta_0$ a podm�nek
\begin{gather}
\label{the2}
H_{t+1}=f_t(H_t,u_t,y_{t+1}),\\
\label{poz4}
y_0=h_0(\theta,v_0),\qquad y_{t+1}=h_t(I_t^{(d)},\theta,u_t,v_{t+1}), \qquad t=0,\ldots,N-1,
\end{gather}
kde $H_t=(I_t^{(d)},T_t)$ je hyperstav syst�mu a $T_t$ dostate�n� statistika pro nezn�m� parametr $\theta$ v �ase $t$.

�lohu �e��me pomoc� dynamick�ho programov�n�, tedy postupnou minimalizac� o�ek�van� ztr�ty od konce ��d�c�ho horizontu
\begin{equation}
\label{los3}
J_t(H_t)=\min_{u_t \in U_t}\E_{y_{t+1}}\left\{g_t(y_{t+1},u_t)+J_{t+1}(H_{t+1})|H_t,u_t\right\}, \qquad t=0,\ldots,N-1,
\end{equation}
kde $T_{t+1}$ a $y_{t+1}$ se po��t� dle \eqref{the2} a \eqref{poz4}.

\section{Certainty equivalent control}
P�i pou�it� metody Certainty equivalent control (CEC) se v rovnici pro o�ek�vanou ztr�tu nahrad� n�hodn� veli�ina $y_{t+1}$ st�edn� hodnotou $\hat{y}_{t+1}$. Ta se vypo��t� z \eqref{poz4} pomoc� zn�m�ch rozd�len� na $v_t$ a posta�uj�c� statistiky $T_t$. O�ek�van� ztr�ta \eqref{los} tak p�ejde v
\begin{gather}
\label{CE}
J_t(H_t)=\min_{u_t \in U_t}\left\{g_t(\hat{y}_t,u_t)+J_{t+1}(\hat{H}_{t+1})|H_t,u_t\right\}, \qquad t=0,\ldots,N-1,
\end{gather}

Podrobn�j�� pojedn�n� s diskuz� aspekt� pou�it� CEC lze nal�zt v \cite{bertsekas1995dynamic}.

\section{Metoda separace}
P�i pou�it� metody separace je proces ��zen� rozd�len do dvou f�z�: 1) indentifikace nezn�m�ho parametru a 2) ��zen� za pou�it� odhadu $\hat{\theta}$ z prvn� f�ze.

Prvn� f�ze slou�� k nez�visl�mu sb�ru dat, kter� jsou n�sledn� pou�ita k odhadu nezn�m�ho parametru. K odhadu m��eme pou��t nap��klad rovnici \eqref{the2}. V druh� f�zi pak po zbytek ��d�c�ho horizontu pou�ijeme  pro n�vrh ��d�c� strategie odhad $\hat{\theta}$ z prvn� f�ze.

\section{Du�ln� ��zen�}
Hledan� ��zen� by m�lo nejen minimalizovat aktu�ln� ztr�tu, ale rovn� z�skat o syst�mu co nejv�ce informac� pro minimalizaci budouc�ch ztr�t. Tento postup se naz�v� du�ln� ��zen� [ref]. ODKAZ NA FILDEBAUMA, POPIS PRINCIPU... (napr JEDNOKROKOVA OPTIMALIZACE S BUZENIM - FILATOV)

\section{Metoda Monte Carlo}
Metoda Monte Carlo \cite{hammersley1964monte} je statistick� simula�n� metoda. Jej� princip spo��v� ve vzorkov�n� n�jak� n�hodn� veli�iny za ��elem odhadu jej� hledan� charakteristiky, nap�. st�edn� hodnoty. V t�to pr�ci je metoda Monte Carlo pou�ita k v�po�tu o�ek�van� ztr�ty \eqref{los3}. 

P�� b�n�m pou�it� dynamick�ho programov�n� m�me p�i v�po�tu $J_t(H_t)$ k dispozici p�edpis pro n�sleduj�c� o�ek�vanou ztr�tu $J_{t+1}(H_{t+1})$. Metoda monte Carlo n�m v�ak d� k dispozici pouze odhad o�ek�van� ztr�ty a pou�it� t�chto aproximac� v dal��m v�po�tu by chybu v�po�tu  navy�ovalo. Nam�sto toho se pro dal�� v�po�et uchov�vaj� $\mu_t(H_t)$ a o�ek�van� ztr�ta v �ase $t$ se pak po��t� jako pr�m�r p�es $n$ realizac� n�hodn�ch veli�iny p�es kter� je prov�d�na st�edn� hodnota $(\theta_{t:N-1},v_{t:N})$, tedy
\begin{equation}
\label{mon}
\frac{1}{n}\sum_{i=1}^n\left(\sum_{j=t}^{N-1}g_j(y_{j+1}^i,\mu_j(H_j^i)\right),
\end{equation}
kde $y_{j+1}^i$ se po��t� podle \eqref{poz4} jako
\begin{equation}
y_{j+1}^i=h_j( I_j^i,\theta_j^i,\mu(H_j^i),v_{j+1}^i), \qquad j=t,\ldots,N-1, \qquad i=1\ldots,n,
\end{equation}
a index $i$ ozna�uje $i$-tou realizaci dan� veli�iny. Realizace $\theta_{t:N-1}$ se generuj� pod�l trajektorie \eqref{poz4}. To znamen�, �e dan�  $\theta_{k+1}$ se generuje a� ve chv�li, kdy je zn�m� $I_k$, $u_k$, posta�uj�c� statistika $T_k$ a $y_{k+1}$ a tedy p�es \eqref{the2} i hustota pravd�podobnosti $f(\theta_{k+1})$.

Tento jednoduch� postup lze vylep�it v�ce�rov�ov�m porovn�n�m kandid�t� na optim�ln� ��zen�. Jedn�m z mo�n�ch vylep�en�ch je dvou�rov�ov� algoritmus poposan� v \cite{nelson2001simple}. V prvn� f�zi tohoto algoritmu se nejprve pro ka�d�ho kandid�ta vygeneruje $n_0$ realizac�. Na jejich z�klad� se vyberou ti, na kter� je nabyto minima s pravd�podobnost� v�t�� ne� je dan� mez $\alpha_0$. Pro tyto se v druh� f�zi vygeneruje dostate�n� po�et realizac� tak, aby bylo mo�n� nejlep�� rozhodnut� zvolit s pravd�podobnost� alespo� rovn� zadan� mezi $\alpha_1$. Takto upraven� algoritmus metody Monte Carlo je robustn�j�� a umo��uje porovn�n� v�t��ho mno�stv� kandid�t�, nebo� po�et realizac� v prvn� f�zi m��e b�t pom�rn� n�zk�, slou�� pouze k odfiltrov�n� zjevn� hor��ch kandid�t� na ��zen�. 

\section{Iterativn� dynamick� programov�n�}
Iterativn� dynamick� programov�n� \cite{luus2000iterative} je jedn� z p��stup� k nalezen� optim�ln� strategie, kter� minimalizuje o�ek�vanou ztr�tu \eqref{ilos2}. Oproti dynamick�mu programov�n� se probl�m �e�� iterativn�. Na za��tku se zvol� n�jak� apriorn� strategie. V ka�d� iteraci se potom vych�z� ze strategie spo�ten� v p�edchoz�m kroku a prost�ednictv�m perturbac� tohoto (suboptim�ln�ho) �e�en� se hled� strategie, pro kterou bude o�k�van� ztr�ta ni���. Tato se pou�ije v n�sleduj�c� iteraci.

\subsection{Diskretizace prostoru}
P�i hled�n� optim�ln� strategie $\mu_t(H_t)$ bychom pro p�esn� vy��slen� o�ek�van� ztr�ty \eqref{mon} na �seku ��d�c�ho horizontu $t\!:\!N$ pot�ebovali jej� analytick� vyj�d�en�. To ale nen� obvykle mo�n�. Je proto nutn� p�ej�t k n�jak� aproximaci, nap��klad 1) p�edpokl�dat n�jak� tvar optim�ln� strategie a p�i v�po�tu ur�it pouze konstanty, kter� v�slednou strategii ur�� jednozna�n�, nebo 2) diskretizovat prostor $(H_t)$ a po��tat $\mu_t(H_t)$ jen v bodech diskretizace a jinde se uch�lit k interpolaci (pop��pad� extrapolaci). 

Jak�m zp�sobem efektivn� diskretizovat prostor nez�visl�ch prom�nn�ch pro aproximativn� v�po�et o�ek�van� ztr�ty \eqref{mon} je p�i pou�it� dynamick�ho programov�n� obt�n� ot�zka. Bude-li bod� v diskretizaci p��li� m�lo, bude v�po�et nespolehliv�, naopak pro p��li� jemnou diskretizaci bude �asov� n�ro�nost v�po�tu rychle stoupat (o �asov� n�ro�nosti SIDP viz d�le). Zde se ukazuje v�hodnost pou�it� iterativn�ho dynamick�ho programov�n�, nebo� sta�� diskretizovat jen tu ��st prostoru kter� bude pot�ebn� v n�sleduj�c� iteraci. Pomoc� strategie spo�ten� v p�edchoz�m kroku a n�hodn�ch realizac� �umu $v_{0:N}$ a nezn�m�ho parametru $\theta_{0:N}$ vygenerujeme trajektorie v $(H)_{0:N}$. V ka�d� �asov� �rovni pak diskretizujeme jen tu ��st prostoru, kter� byla zasa�ena. 

V t�to pr�ci je volena jednoduch� metoda v kter� se spo�te nejmen�� hyperkv�dr kolem zasa�en� tak, �e se vezme nejmen�� hyperkv�dr orientovan� ve sm�ru sou�adn�ch os, do kter�ho se vygenerovan� body vejdou. Prostor se pot� diskretizuje pouze v t�to oblasti. Metodu k ur�en� hyperkv�dru s obecnou orientac� lze naj�t v \cite{bh-eamvb-01}. 

\section{SIDP}
Metoda stochastick�ho iterativn�ho dynamick�ho programov�n� (SIDP) \cite{thompson2005stochastic} spo��v� v sou�asn�m pou�it�  metody Monte Carlo k z�sk�n� aproximace pro o�ek�vanou ztr�tu  a iterativn�ho dynamick�ho programov�n� k nalezen� optim�ln� strategie. Pro ��ely t�to posta�uje z�kladn� verze metody Monte Carlo a je proto v n�sleduj�c� implementaci SIDP pou�ita. P�i pou�it� iterativn�ho dynamick�ho programov�n� se uch�l�me k diskretizovat prostoru hyperstav� a budeme pou��vat interpolaci (pop��pad� extrapolaci) napo�ten�ch hodnot. Poznamenejme, �e d�ky p�edpokladu gaussovsk�ho rozd�len� parametru ${\theta_t}$, diskretizace vzhledem k ${T_t}$ znamen� diskretizaci vzhledem k ${(\hat{\theta}_t,P_t)}$.

\subsection{Algoritmus SIDP}
V tomto od�lu je sch�maticky pops�n algoritmus SIDP. Jeho parametry jsou

\begin{itemize}
\item $n_{pass}, \, n_{iter}$� po�et opakov�n� a iterac� algoritmu
\item $N$ -- ��d�c� horizont
\item $n_g$ -- po�et bod� v diskretizaci ka�d� dimenzi $H_t$, tj. $|H_t|=n_g^{\dim H_t}$
\item $\pi^*=\mu_{0:N-1}(H_{0:N-1})$ -- apriorn� ��d�c� strategie
\item $m$ -- po�et kadnid�t� na zm�nu  ��d�c�ho z�sahu v jedn� iteraci IDP
\item $\beta^{in}$ -- po��te�n� rozsah pro hled�n� optim�ln�ho ��d�c�ho z�sahu
\item $\gamma,\, \lambda$ -- parametry pro redukci $\beta^{in}$
\item $n$ -- po�et realizac� pro odhad metodou Monte Carlo
\end{itemize}

Jak plyne z n�sleduj�c�ho popisu, �asov� slo�itost SIDP vzhledem k jeho parametr�m je $O(n_{pass}n_{iter}N^2mnn_g^{\dim H_N})$ (�asov� n�ro�nost metody Monte Carlo je �m�rn� vzd�lenosti od konce horizontu, proto je �asov� slo�itost �m�rn� druh� mocnin� $N$).

\begin{algorithm}
\begin{algorithmic}
\FOR{$i = 1$ to $n_{pass}$} 
\FOR{$j = 1$ to $n_{iter}$} 
\STATE $\beta_{i,j} := \gamma^{j-1}\lambda^{i-1}\beta^{in}$
\FOR{$k = 1 $ to $|H_t|$}  
\STATE spo�ti trajektorii $H_{0,k}$, pou�ij aktu�ln� $\pi^*$, jej� interpolace a extrapolace a realizace nezn�m�ho parametru $\theta_0,\ldots,\theta_{N-1}$ pod�l t�to trajektorie
\ENDFOR
\FOR{$t = N-1 $ to $0$} 
\STATE vytvo� $\tilde{H}_t$ jako�to rovnom�rnou s� v oblasti bod� $H_t$
\STATE interpoluj (extrapoluj) $\mu_t^*(H_t)$ na $\mu_t^*(\tilde{H}_t)$
\FOR{$k = 1 $ to $|H_t|$}  
\FOR{$m=-\left[\frac{m-1}{2}\right]$ to $\left[\frac{m}{2}\right]$}
\STATE pro $\tilde{H}_{t,k}$ vygeneruj kandid�ta na ��zen� $\mu_t(\tilde{H}_{t,k}) =  \mu_t^*(\tilde{H}_{t,k})+m\beta_{i,j}$ 
\STATE pomoc� metody Monte Carlo spo�ti o�ek�vanou ztr�tu
\ENDFOR
\STATE rozhodnut� s nejni���  o�ek�vanou ztr�tou uchovej jako nov� optim�ln� rozhodnut� pro $\tilde{H}_{t,k}$.
\ENDFOR
\ENDFOR
\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}
