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