====== 3. Markovské rozhodovací procesy ======
Vaším úkolem je implementovat metody //value iteration// a //policy iteration// pro řešení zadaného MDP.

  * Úloha bude opět probíhat v prostředí KUIMaze: {{section>courses:b3b33kui:kuimaze:00_instalace#download&noheader&firstsectiononly}}
  * [[courses:b3b33kui:semestralni_ulohy:3_mdp:hodnoceni|Hodnocení úlohy]].
  * Termín odevzdání úlohy je uveden v [[https://cw.felk.cvut.cz/brute|BRUTE]]. 

===== Specifikace =====
V modulu ''mdp_agent.py'' implementujte funkce

  - ''find_policy_via_value_iteration(problem, discount_factor, epsilon)'' a 
  - ''find_policy_via_policy_iteration(problem, discount_factor)''. 

Funkce mají následující **parametry**: 
  * ''problem'' je prostředí, tj. objekt typu ''kuimaze.MDPMaze''
  * ''discount_factor'' je z rozmezi ''(0,1)''
  * ''epsilon'' je maximalní povolená chyba pro Value jednotlivých stavů (pouze pro value iteration)

Očekávaný **výstup**: obě funkce by měly vracet **strategii (policy)** reprezentovanou jako slovník, kde klíčem je buď instance třídy ''State'' nebo tuple (x,y)  a hodnotou je optimální akce pro daný stav. Stačí uvažovat dosažitelné stavy a pro terminální stavy nechť je výstup ''None''. 

Modul ''mdp_agent.py'' odevzdejte do [[https://cw.felk.cvut.cz/brute|BRUTE]]. 

**Timeout:** na jednotlivé běhy value/policy iteration pro danou instanci problému máte časový limit 30s.

<note important>Odevzdané řešení musí odpovídat algoritmům ze zadání. Například není možné místo algoritmu //policy iteration// odevzdat kód pro //value iteration//. V takovém případě může být celá úloha ohodnocena nula body.</note>

===== Jak na to? =====
  * Začněte [[courses:b3b33kui:kuimaze:2_mdpmaze|příkladem použití a popisem základních metod]] prostředí ''MDPMaze''. 
  * Zkuste porozumět kódu v souboru ''mdp_sandbox.py'', který ukazuje základní práci s MDPMaze, a můžete ho použít jako start k další implementaci.