14_dagger.tex

\citet{ross2011reduction} predstavljaju metodu učenja pretraživanja
\textsc{DAgger} \engla{dataset aggregation}{DAgger}, koja je po svojim
karakteristikama bolja od algoritma \textsc{Searn}. Demonstriraju uspješnost na
dva zadatka:
\begin{itemize}
  \item upravljanje automobilom u \textsc{3d} trkaćoj igri (\textit{Super Tux
  Kart}) i
  \item igranje igre \textit{Super Mario}.
\end{itemize}
Kao optimalnu politiku za prvi zadatak koriste ljudskog stručnjaka, a za drugi
koriste pretraživanje u širinu \engla{breadth-first-search}{bfs} ograničeno
dubinom. Algoritam ima nekoliko razlika u usporedbi s algoritmom \textsc{Searn}:
\begin{itemize}
  \item učenje je moguće raditi primjer po primjer \engl{online};
  \item za \textit{rollin} se koristi naučena ili referentna politika (na prvom
  primjeru postoji samo referenta), dok \textsc{Searn} koristi mješavinu
  referentne i svih naučenih kroz više prolaza;
  \item kod algoritma \textsc{Searn} mješavina se primjenjuje za svako stanje,
  a kod algoritma \textsc{DAgger} prije svakog primjera odabire se referentna
  ili naučena politika što rezultira time da se na nekim primjerima uči koristeći
  samo referentnu politiku za \textit{rollin}, a na nekima samo naučenu. Unatoč
  tome što je algoritam moguće učiti primjer po primjer preporučuje se više
  prolaza kroz skup za učenje;
  \item \textit{rollout} je eliminiran pretpostavljajući da se za svaku odluku
  može izračunati njen trošak, ali može se koristiti referentna politika ako se
  trošak ne može izračunati (koristeći postupak \textit{rollout});
  \item nije potrebno držati više naučenih politika, nego se koristi samo politika
  naučena do trenutnog primjera.
\end{itemize}
Autori su predstavili, uz eksperimentalnu potvrdu superiornosti nad algoritmom
\textsc{Searn}, i teoretsku analizu kojom pokazuju da je takva redukcija
konzistentna.

\textsc{DAgger} se može opisati, koristeći terminologiju uvedenu u
potpoglavljima \ref{ch:reductions}, \ref{ch:politikailocalopt} i
\ref{ch:rollinrollout}, kao konzistentna (ako je referentna politika optimalna)
redukcija problema združenog predviđanja na problem binarne klasifikacije, gdje
se za \textit{rollin} koristi referentna ili naučena politika (odabir se radi
stohastički prije postupka \textit{rollin}, a ne na svakom stanju kao kod
algoritma \textsc{Searn}), a za \textit{rollout} referenta politika (ako postoji
dekompozicija funkcije gubitka, onda se \textit{rollout} ne bi izvršavao što je
ekvivalentno kao da se koristi referentna politika kod koje funkcija gubitka ima
dekompozciju na niz odluka).