[1429] | 1 | \section{Zpětnovazebné učení} |
---|
[1419] | 2 | |
---|
| 3 | |
---|
[1429] | 4 | |
---|
| 5 | \subsection{Markovův rozhodvací proces} |
---|
[1419] | 6 | Markovův rozhodvací proces je alternativní metoda sloužící |
---|
| 7 | k volbě strategií odhadem zisků z nich plynoucích do budoucna. |
---|
| 8 | Modeluje prostředí jako množinu stavů a akcí, které |
---|
| 9 | je možné provést a mění stav prostředí s určitou pravděpodobností. |
---|
| 10 | Čas je zde vnímán v diskrétní formě kroků a prostředí jako částečně známé, částečně |
---|
| 11 | ovlivnitelné a do jisté míry měnící se náhodně.\\ |
---|
| 12 | |
---|
| 13 | Účelem tohoto procesu je najít funkci $\pi(s): S \rightarrow A$ |
---|
| 14 | která každému stavu prostředí jednoznačně přiřadí akci maximalizující |
---|
| 15 | zisky do určitého bodu v budoucnosti, teoreticky do nekonečna. |
---|
| 16 | V \cite{3_i_traff_light_c} je Markovův rozhodovací proces definován takto: |
---|
| 17 | |
---|
| 18 | \begin{definition}[Markovův rozhodovací proces]\label{de:markov_decision_process} |
---|
| 19 | Markovův rozhodovací proces je definován jako uspořádaná čtveřice |
---|
| 20 | $$ (S, A, P, R) $$ |
---|
| 21 | kde jsou |
---|
| 22 | \begin{itemize} |
---|
| 23 | \item $S$ - množina stavů prostředí |
---|
| 24 | \item $A$ - množina možných akcí |
---|
| 25 | \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$ |
---|
| 26 | za stavu $i$ přejde systém do stavu $j$ |
---|
| 27 | \item $R(i,a,j)$ - okamžitý užitek přechodu systému ze stavu $i$ do stavu $j$ při akci $a$ |
---|
| 28 | \end{itemize} |
---|
| 29 | \end{definition} |
---|
| 30 | |
---|
| 31 | |
---|
| 32 | |
---|
[1429] | 33 | \subsection{Dynamické programování}\label{sec:dynamic_programming} |
---|
[1419] | 34 | |
---|
| 35 | %asi trochu poupravit podle \cite{tlc_using_sarsa} |
---|
| 36 | Dynamické programování je proces sloužící k nalezení optimální |
---|
| 37 | strategie dané $\pi(s)$. K tomu slouží funkce očekávaných kumulativních diskontních zisků |
---|
| 38 | $V^{\pi}(i) : \rightarrow \mathbb{R}$ |
---|
| 39 | reprezentující předpokládané dlouhodobé zisky při určité $\pi(s)$. Agent se tedy snaží |
---|
| 40 | zvolit strategii tak, aby funkci $V^{\pi}$ při daném počátečním stavu $s_0 = i$ maximalizoval. |
---|
| 41 | V \cite{3_i_traff_light_c} je tato funkce definována násedovně: |
---|
| 42 | |
---|
| 43 | \begin{definition}[V-funkce]\label{de:v_function} |
---|
| 44 | $$ |
---|
| 45 | V^{\pi}(i) = \sum_{k=0}^{\infty} E( \gamma^{k} R(s_k, \pi(s_k), s_{k+1})) |
---|
| 46 | $$ |
---|
| 47 | při $s_0 = i$ kde jsou |
---|
| 48 | \begin{itemize} |
---|
| 49 | \item $\gamma \in <0,1> $ diskontní faktor určující snižování významnosti odhadu s narůstajícím časem |
---|
| 50 | \item $E$ operator odhadu %střední hodnota přes všechny možnosti cesty stav/akce |
---|
| 51 | \end{itemize} |
---|
| 52 | \end{definition} |
---|
| 53 | |
---|
| 54 | Tento zápis je spíše formální, proto se tato funkce v \cite{3_i_traff_light_c} definuje pomocí |
---|
| 55 | pomocí $Q$-funkce $Q^{\pi}(i,a)$, funkce odhadující zisk při aplikování akce $a$ při stavu $a$. |
---|
| 56 | |
---|
| 57 | \begin{definition}[Q-function]\label{de:q_function} |
---|
| 58 | $$ |
---|
| 59 | Q(i, a)^{\pi} = \sum_{j \in S} P(i,a,j) ( R(i,a,j) + \gamma V^{\pi}(j) ) |
---|
| 60 | $$ |
---|
| 61 | |
---|
| 62 | kde jsou |
---|
| 63 | $$ V^{\pi}(i) = \max_a Q^{\pi}(i,a) $$, |
---|
| 64 | $$ \pi(i) = \arg \max_a Q^{\pi}(i,a) $$ |
---|
| 65 | \end{definition} |
---|
| 66 | |
---|
| 67 | Postupným iterativním přepočítáváním $V$, $Q$ a $\pi$ dostaneme Bellmanovu rovnici optimality definovanou v \cite{dynamic_programming} |
---|
| 68 | jako: |
---|
| 69 | |
---|
| 70 | \begin{definition}[Bellmanova rovnice optimality]\label{de:bellman_equation_of_optimality} |
---|
| 71 | $$ |
---|
| 72 | Q(i, a)^{*} = \sum_{j \in S} P(i,a,j) ( R(i,a,j) + \gamma V^{*}(j) ) |
---|
| 73 | $$ |
---|
| 74 | \end{definition} |
---|
| 75 | |
---|
| 76 | kde funkce $Q$ a $V$ nezávisí na strategii $\pi$. |
---|
| 77 | Bellmanova rovnice optimality říká, že pokud jsou $Q$ a $V$ optimální, |
---|
| 78 | nemění se s dalšími kroky iterace. V praxi se stanoví nějaká dostatečně malá konstanta $\epsilon$, a |
---|
| 79 | pokud se v dalším kroku $Q$ a $V$ nezmění o vícejak $\epsilon$, považujeme je za optimální. |
---|
| 80 | Navíc bylo dokázáno, že vždy existuje právě jedna dvojice dvojice těchto funkcí, která je optimální |
---|
| 81 | a vždy ji lze tedy iterací určit.\\ |
---|
| 82 | |
---|
| 83 | Algoritmus pro určení funkce $\pi$ tedy iterativně přes všechny stavy, akce a časové |
---|
| 84 | kroky upravuje funkce $V$, $Q$ a $\pi$ podle rovnic \ref{de:q_function}, a v \cite{3_i_traff_light_c} |
---|
| 85 | je v krocích popsán takto: |
---|
| 86 | |
---|
| 87 | \begin{enumerate} |
---|
| 88 | \item Inicializace počátečních hodnot funkcí $V$ a $Q$ |
---|
| 89 | \item Opakovat kroky 3-5 do dosažení podmínek optimality |
---|
| 90 | \item Upravit hodnotu $Q$-funkce podle rovnice |
---|
| 91 | $$ Q(i, a) = \sum_{j \in S} P(i,a,j) ( R(i,a,j) + \gamma V(j) ) $$ |
---|
| 92 | \item dopočítat hodnotu funkce $V$ jako |
---|
| 93 | $$ V(i) = \max_a Q(i,a) $$ |
---|
| 94 | \item nastavit hodnotu funkce $pi$ na akci maximálního zisku jako |
---|
| 95 | $$ \pi(i) = \arg \max_a Q(i,a) $$ |
---|
| 96 | \end{enumerate} |
---|
| 97 | |
---|
[1429] | 98 | \subsection{Zpětnovazebné učení (Reinforcement learning)} |
---|
[1419] | 99 | V praxi jsou z počátku hodnoty funkcí $P$ a $R$ popsané v \ref{de:markov_decision_process} |
---|
| 100 | neznámé a je potřeba je určit pozorováním. Prakticky se tedy agent musí naučit jak prostředí |
---|
| 101 | reaguje na provedení každé akce v určitém stavu. Podle \cite{3_i_traff_light_c} se tedy |
---|
| 102 | na začátku procesu nastaví všechny hodnoty na nulu a po každé provedené akci se pozoruje |
---|
| 103 | jak prostředí reaguje, tedy hodnota funkce $P(i, a, j)$, a jaký okamžitý zisk z toho plyne, tedy |
---|
| 104 | $R(i, a, j)$. K určení těchto hodnot se používají různé algoritmy. |
---|
| 105 | |
---|
[1429] | 106 | \subsubsection{Q-učení (Q-learning)} |
---|
[1419] | 107 | Q-učení je bezmodelová metoda popsaná v \cite{q_learning} a \cite{learning_to_predict}. |
---|
| 108 | K určení požadovaných hodnot, jak název napovídá, používá |
---|
| 109 | úpravu funkce $Q$ definované v \ref{de:q_function} |
---|
| 110 | v každém časovém kroce $t$ podle rovnice: |
---|
| 111 | |
---|
| 112 | $$ |
---|
| 113 | Q_t(i,a) = \left\{ |
---|
| 114 | \begin{array}{lr} |
---|
| 115 | (1 - \alpha_t) Q_{t-1}(i,a) + \alpha_t ( r_t + \gamma V_{t-1}(i) ) & : i = i_t \wedge a = a_t \\ |
---|
| 116 | Q_{t-1}(i,a) & : jinak |
---|
| 117 | \end{array} |
---|
| 118 | \right. |
---|
| 119 | $$ |
---|
| 120 | |
---|
| 121 | kde $ \alpha_t \in <0,1> $ je učící faktor v časovém kroce $t$ a $r_t$ je okamžitý |
---|
| 122 | zisk akce $a$. Funkce $P$ a $R$ popisující prostředí se zde tedy nevyskytují a |
---|
| 123 | $Q$-funkce se zde upravuje přímo z naměřených hodnot za použití snižujícího se |
---|
| 124 | učícího koeficientu $\alpha$. |
---|
| 125 | |
---|
| 126 | |
---|
[1429] | 127 | \subsubsection{Učení na základě modelu (Model-based learning)}\label{sec:model_based_learning} |
---|
[1419] | 128 | V této metodě, popsané v \cite{3_i_traff_light_c}, se modeluje |
---|
| 129 | prostředí funkcemi $P(i,a,j)$ a $R(i,a,j)$, které jsou definované v |
---|
| 130 | \ref{de:markov_decision_process}. Ty jsou z počátku neznámé |
---|
| 131 | a jejich hodnoty se určují metodou maximální věrohodnosti |
---|
| 132 | podle četnosti naměřených údajů. Agent popsaný v \cite{3_i_traff_light_c} |
---|
| 133 | používal následující veličiny: |
---|
| 134 | |
---|
| 135 | \begin{itemize} |
---|
[1429] | 136 | \item $C_{i}(a)$ - počet, kolikrát agent zvolil akci $a$ ve stavu $i$ |
---|
| 137 | \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$ |
---|
| 138 | \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$ |
---|
[1419] | 139 | \end{itemize} |
---|
| 140 | |
---|
[1429] | 141 | Model maximální věrohodnosti (MLM) je v \cite{3_i_traff_light_c} definován jako: |
---|
[1419] | 142 | |
---|
[1429] | 143 | \begin{definition}[MLM]\label{de:mlm} |
---|
| 144 | $$ \hat{P} (i,a,j) = \frac{C_{i,j}(a)}{C_i(a)} $$ |
---|
| 145 | $$ \hat{R} (i,a,j) = \frac{R_{i,j}(a)}{C_{i,j}(a)} $$ |
---|
| 146 | \end{definition} |
---|
[1419] | 147 | |
---|
[1429] | 148 | V každém časovém kroce je po aplikaci akce $a$ model přepočítán. Poté |
---|
| 149 | je znovu použito dynamické programování popsané v sekci \ref{sec:dynamic_programming}. |
---|
[1419] | 150 | |
---|
[1429] | 151 | |
---|
| 152 | |
---|
| 153 | |
---|
| 154 | |
---|
| 155 | |
---|
| 156 | |
---|
| 157 | |
---|