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

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

presunuti minimalizace do kapitoly o LQ rizeni

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