root/applications/doprava/texty/novotny_vyzk_LQ/Reinforcement_learning.tex.backup @ 1433

Revision 1429, 6.9 kB (checked in by jabu, 12 years ago)

presunuti minimalizace do kapitoly o LQ rizeni

Line 
1\section{Zpětnovazebné učení}
2
3
4
5\subsection{Markovův rozhodvací proces}
6Markovův rozhodvací proces je alternativní metoda sloužící
7k volbě strategií odhadem zisků z nich plynoucích do budoucna.
8Modeluje prostředí jako množinu stavů a akcí, které
9je 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ě
11ovlivnitelné 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$
14která každému stavu prostředí jednoznačně přiřadí akci maximalizující
15zisky do určitého bodu v budoucnosti, teoreticky do nekonečna.
16V \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
33\subsection{Dynamické programování}\label{sec:dynamic_programming}
34
35%asi trochu poupravit podle \cite{tlc_using_sarsa}
36Dynamické programování je proces sloužící k nalezení optimální
37strategie dané $\pi(s)$. K tomu slouží funkce očekávaných kumulativních diskontních zisků
38$V^{\pi}(i) : \rightarrow \mathbb{R}$
39reprezentující předpokládané dlouhodobé zisky při určité $\pi(s)$. Agent se tedy snaží
40zvolit strategii tak, aby funkci $V^{\pi}$ při daném počátečním stavu $s_0 = i$ maximalizoval.
41V \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 $$
47př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
54Tento zápis je spíše formální, proto se tato funkce v \cite{3_i_traff_light_c} definuje pomocí
55pomocí $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
62kde 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
67Postupným iterativním přepočítáváním $V$, $Q$ a $\pi$ dostaneme Bellmanovu rovnici optimality definovanou v \cite{dynamic_programming}
68jako:
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
76kde funkce $Q$ a $V$ nezávisí na strategii $\pi$.
77Bellmanova rovnice optimality říká, že pokud jsou $Q$ a $V$ optimální,
78nemění se s dalšími kroky iterace. V praxi se stanoví nějaká dostatečně malá konstanta $\epsilon$, a
79pokud se v dalším kroku $Q$ a $V$ nezmění o vícejak $\epsilon$, považujeme je za optimální.
80Navíc bylo dokázáno, že vždy existuje právě jedna dvojice dvojice těchto funkcí, která je optimální
81a vždy ji lze tedy iterací určit.\\
82
83Algoritmus pro určení funkce $\pi$ tedy iterativně přes všechny stavy, akce a časové
84kroky upravuje funkce $V$, $Q$ a $\pi$ podle rovnic \ref{de:q_function}, a v \cite{3_i_traff_light_c}
85je 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
98\subsection{Zpětnovazebné učení (Reinforcement learning)}
99V praxi jsou z počátku hodnoty funkcí $P$ a $R$ popsané v \ref{de:markov_decision_process}
100neznámé a je potřeba je určit pozorováním. Prakticky se tedy agent musí naučit jak prostředí
101reaguje na provedení každé akce v určitém stavu. Podle \cite{3_i_traff_light_c} se tedy
102na začátku procesu nastaví všechny hodnoty na nulu a po každé provedené akci se pozoruje
103jak 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 
106\subsubsection{Q-učení (Q-learning)}
107Q-učení je bezmodelová metoda popsaná v \cite{q_learning} a \cite{learning_to_predict}.
108K určení požadovaných hodnot, jak název napovídá, používá
109úpravu funkce $Q$ definované v \ref{de:q_function}
110v 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
121kde $ \alpha_t \in <0,1> $ je učící faktor v časovém kroce $t$ a $r_t$ je okamžitý
122zisk 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
124učícího koeficientu $\alpha$.
125
126
127\subsubsection{Učení na základě modelu (Model-based learning)}\label{sec:model_based_learning}
128V této metodě, popsané v \cite{3_i_traff_light_c}, se modeluje
129prostř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é
131a jejich hodnoty se určují metodou maximální věrohodnosti
132podle četnosti naměřených údajů. Agent popsaný v \cite{3_i_traff_light_c}
133používal následující veličiny:
134
135\begin{itemize}
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$
139\end{itemize}
140
141Model maximální věrohodnosti (MLM) je v \cite{3_i_traff_light_c} definován jako:
142
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}
147
148V každém časovém kroce je po aplikaci akce $a$ model přepočítán. Poté
149je znovu použito dynamické programování popsané v sekci \ref{sec:dynamic_programming}.
150
151
152
153
154
155
156
157
Note: See TracBrowser for help on using the browser.