root/applications/doprava/texty/novotny_vyzk_LQ/Reinforcement_learning.tex @ 1434

\section{Zpětnovazebné učení}
Zde popíšeme metodu řízení, využívající zpětnovazebného učení.
Nejprve zadefinujeme základní pojmy a nastíníme formalismus, na kterém je tato metoda postavena
a jejíž použití v decentraizovaném řízení dopravy je popsáno v kapitole \ref{sec:reinforcement_learning_usage}.

\subsection{Markovův rozhodvací proces}
Markovův rozhodvací proces je alternativní metoda sloužící
k volbě strategií odhadem zisků z nich plynoucích do budoucna.
Modeluje prostředí jako množinu stavů a akcí, které 
je možné provést a mění stav prostředí s určitou pravděpodobností.
Čas je zde vnímán v diskrétní formě kroků a prostředí jako částečně známé, částečně
ovlivnitelné a do jisté míry měnící se náhodně.\\

Účelem tohoto procesu je najít funkci $\pi(s): S \rightarrow A$
která každému stavu prostředí jednoznačně přiřadí akci maximalizující
zisky do určitého bodu v budoucnosti, teoreticky do nekonečna.
V \cite{3_i_traff_light_c} je Markovův rozhodovací proces definován takto:

\begin{definition}[Markovův rozhodovací proces]\label{de:markov_decision_process}
  Markovův rozhodovací proces je definován jako uspořádaná čtveřice
  $$ (S, A, P, R) $$
  kde jsou
  \begin{itemize}
    \item $S$ - množina stavů prostředí
    \item $A$ - množina možných akcí
    \item $P(i,a,j) := p(s_{t+1} = j | s_t = i \wedge a = a_t)$ - pravděpodobnost, že při aplikování akce $a$
                                                                  za stavu $i$ přejde systém do stavu $j$
    \item $R(i,a,j)$ - okamžitý užitek přechodu systému ze stavu $i$ do stavu $j$ při akci $a$
  \end{itemize}
\end{definition}



\subsection{Dynamické programování}\label{sec:dynamic_programming}

%asi trochu poupravit podle \cite{tlc_using_sarsa}
Dynamické programování je proces sloužící k nalezení optimální
strategie dané $\pi(s)$. K tomu slouží funkce očekávaných kumulativních diskontních zisků
$V^{\pi}(i) : S \rightarrow \mathbb{R}$ 
reprezentující předpokládané dlouhodobé zisky při určité funkci $\pi(s)$. Agent se tedy snaží 
zvolit strategii tak, aby funkci $V^{\pi}$ při daném počátečním stavu $s_0 = i$ maximalizoval.
V publikaci \cite{3_i_traff_light_c} je tato funkce definována násedovně:

\begin{definition}[V-funkce]\label{de:v_function}
 $$
    V^{\pi}(i) = \sum_{k=0}^{\infty} E( \gamma^{k} R(s_k, \pi(s_k), s_{k+1}))
 $$
při $s_0 = i$ kde jsou
\begin{itemize}
 \item $\gamma \in <0,1> $ diskontní faktor určující snižování významnosti odhadu s narůstajícím časem
 \item $E$ operátor odhadu %střední hodnota přes všechny možnosti cesty stav/akce
\end{itemize}
\end{definition}

Tento zápis je spíše formální, proto se tato funkce v \cite{3_i_traff_light_c} definuje pomocí
pomocí $Q$-funkce $Q^{\pi}(i,a)$, funkce odhadující zisk při aplikování akce $a$ při stavu $a$.

\begin{definition}[Q-function]\label{de:q_function}
 $$
    Q^{\pi}(i, a) = \sum_{j \in S} P(i,a,j) ( R(i,a,j) + \gamma V^{\pi}(j) )
 $$

kde jsou
 $$ V^{\pi}(i) = \max_a Q^{\pi}(i,a) \;,$$
 $$ \pi(i) = \arg \max_a Q^{\pi}(i,a) $$
\end{definition}

Postupným iterativním přepočítáváním $V$, $Q$ a $\pi$ dostaneme Bellmanovu rovnici optimality definovanou v \cite{dynamic_programming}
jako:

\begin{definition}[Bellmanova rovnice optimality]\label{de:bellman_equation_of_optimality}
 $$
    Q(i, a)^{*} = \sum_{j \in S} P(i,a,j) ( R(i,a,j) + \gamma V^{*}(j) )
 $$
\end{definition}

kde funkce $Q$ a $V$ nezávisí na strategii $\pi$.
Bellmanova rovnice optimality říká, že pokud jsou $Q$ a $V$ optimální, 
nemění se s dalšími kroky iterace. V praxi se stanoví nějaká dostatečně malá konstanta $\epsilon$, a 
pokud se v dalším kroku $Q$ a $V$ nezmění o vícejak $\epsilon$, považujeme je za optimální.
Navíc bylo dokázáno, že vždy existuje právě jedna dvojice těchto funkcí, která je optimální
a vždy ji lze tedy iterací určit.\\

Algoritmus pro určení funkce $\pi$ tedy iterativně přes všechny stavy, akce a časové
kroky upravuje funkce $V$, $Q$ a $\pi$ podle rovnic \ref{de:q_function}, a v publikaci \cite{3_i_traff_light_c}
je v krocích popsán takto:

\begin{enumerate}
 \item Inicializace počátečních hodnot funkcí $V$ a $Q$
 \item Opakovat kroky 3-5 do dosažení podmínek optimality
 \item Upravit hodnotu $Q$-funkce podle rovnice
   $$ Q(i, a) = \sum_{j \in S} P(i,a,j) ( R(i,a,j) + \gamma V(j) ) $$
 \item dopočítat hodnotu funkce $V$ jako
  $$ V(i) = \max_a Q(i,a) $$
 \item nastavit hodnotu funkce $\pi$ na akci maximálního zisku jako
  $$ \pi(i) = \arg \max_a Q(i,a) $$ 
\end{enumerate}

\subsection{Zpětnovazebné učení (Reinforcement learning)}
V praxi jsou z počátku hodnoty funkcí $P$ a $R$ popsané v \ref{de:markov_decision_process}
neznámé a je potřeba je určit pozorováním. Prakticky se tedy agent musí naučit jak prostředí
reaguje na provedení každé akce v určitém stavu. Podle \cite{3_i_traff_light_c} se tedy
na začátku procesu nastaví všechny hodnoty na nulu a po každé provedené akci se pozoruje
jak prostředí reaguje, tedy hodnota funkce $P(i, a, j)$, a jaký okamžitý zisk z toho plyne, tedy
$R(i, a, j)$. K určení těchto hodnot se používají různé algoritmy.
 
\subsubsection{Q-učení (Q-learning)}
Q-učení je bezmodelová metoda popsaná v publikacích \cite{q_learning} a \cite{learning_to_predict}. 
K určení požadovaných hodnot, jak název napovídá, používá
úpravu funkce $Q$ definované v \ref{de:q_function} 
v každém časovém kroce $t$ podle rovnice:

$$
  Q_t(i,a) = \left\{
     \begin{array}{lr}
       (1 - \alpha_t) Q_{t-1}(i,a) + \alpha_t ( r_t + \gamma V_{t-1}(i) ) & : i = i_t \wedge a = a_t \\
       Q_{t-1}(i,a) & : jinak
     \end{array}
   \right. \;,
$$

kde $ \alpha_t \in <0,1> $ je učící faktor v časovém kroce $t$ a $r_t$ je okamžitý
zisk akce $a$. Funkce $P$ a $R$ popisující prostředí se zde tedy nevyskytují a 
$Q$-funkce se zde upravuje přímo z naměřených hodnot za použití snižujícího se
učícího koeficientu $\alpha$.


\subsubsection{Učení na základě modelu (Model-based learning)}\label{sec:model_based_learning}
V této metodě, popsané v \cite{3_i_traff_light_c}, se modeluje
prostředí funkcemi $P(i,a,j)$ a $R(i,a,j)$, které jsou definované v
\ref{de:markov_decision_process}. Ty jsou z počátku neznámé
a jejich hodnoty se určují metodou maximální věrohodnosti
podle četnosti naměřených údajů. Agent popsaný v \cite{3_i_traff_light_c}
používal následující veličiny:

\begin{itemize}
 \item $C_{i}(a)$ - počet, kolikrát agent zvolil akci $a$ ve stavu $i$
 \item $C_{i,j}(a)$ - počet, kolikrát prostředí přešlo ze stavu $i$ do stavu $j$ při aplikace akce $a$
 \item $R_{i,j}(a)$ - součet okamžitých zisků při použití akce $a$ ve stavu $i$ a následném přechodu do stavu $j$
\end{itemize}

Model maximální věrohodnosti (MLM) je v \cite{3_i_traff_light_c} definován jako:

\begin{definition}[MLM]\label{de:mlm} 
 $$ \hat{P} (i,a,j) = \frac{C_{i,j}(a)}{C_i(a)} $$
 $$ \hat{R} (i,a,j) = \frac{R_{i,j}(a)}{C_{i,j}(a)} $$
\end{definition}

V každém časovém kroce je po aplikaci akce $a$ model přepočítán. Poté
je znovu použito dynamické programování popsané v sekci \ref{sec:dynamic_programming}.