====== 3. Markovské rozhodovací procesy ======

Vaším úkolem je implementovat metody //value iteration// a //policy iteration// k nalezení optimální strategie (policy) pro zadaný MDP.


===== Specifikace =====
V modulu ''mdp_agent.py'' implementujte dvě třídy:

  * ''ValueIterationAgent'', která bude hledat strategii metodou //value iteration//, a 
  * ''PolicyIterationAgent'', která bude hledat strategii metodou //policy iteration//.

Rozhraní obou tříd bude shodné, obě musí implementovat následující metody:

^ metoda ^ vstupní parametry ^ výstupní parametry ^vysvětlení ^
| ''%%__%%init%%__%%'' | ''env: MDPProblem'', ''gamma: float'', ''epsilon: float'' | //žádné// | Inicializace agenta.|
| ''find_policy'' | //žádné// | ''Policy'' | Vrátí optimální strategii, tedy slovník dvojic (stav, akce). |

  * Třída se bude inicializovat následujícími **parametry**: 
    * ''env'' je prostředí, tj. objekt typu ''kuimaze2.MDPProblem''
    * ''gamma'' je tzv. "discount factor" (zlevnění) z rozmezi ''(0,1)''
    * ''epsilon'' je maximalní povolená chyba pro hodnoty jednotlivých stavů (využije se ve value iteration)
  * **Výstupem** metody ''find_policy()'' musí být **strategie (policy)** reprezentovaná jako **slovník**, kde klíčem je vždy stav (instance třídy ''kuimaze2.State'') a hodnotou je optimální akce pro daný stav (instance třídy ''kuimaze2.Action''). Strategie musí obsahovat akci pro všechny volné stavy, včetně terminálních. U terminálních stavů na konkrétní zvolené akci nezáleží.
  * **Timeout:** na jednotlivé běhy value/policy iteration pro danou instanci problému máte časový limit 30s. (Ale měli byste potřebovat jen zlomek tohoto času.)
  * Algoritmy implementované ve třídách ''ValueIterationAgent'' a ''PolicyIterationAgent'' musí odpovídat zadání. Například není možné v ''PolicyIterationAgent.find_policy()'' prostě zavolat ''ValueIteration.find_policy()'' nebo v ní (znovu) implementovat algoritmus //value iteration// (nebo opačně). V takovém případě může být celá úloha ohodnocena 0 body!
  * V implementaci algoritmů můžete používat jen [[..:kuimaze:20_mdpproblem|veřejné rozhraní třídy ''MDPProblem'']]. Pokud byste měli pocit, že potřebujete využívat metody jiných tříd než ''MDPProblem'' nebo že potřebujete využít neveřejné proměnné a metody (jejichž jméno začíná na ''_''), proberte to se svým cvičícím.


===== Jak na to? =====
  * Doporučujeme vytvořit si pro úlohu nový pracovní adresář. [[..:kuimaze:00_install|Zprovozněte si]] v něm aktualizovanou verzi balíčku ''kuimaze2''.
  * Seznamnte se s prostředím [[..:kuimaze:20_mdpproblem|MDPProblem]]. 
  * V balíčku ''kuimaze2'' najdete také skript ''example_mdp.py'', který také ukazuje, jak se s prostředím dá pracovat. Lze jej využít jako výchozí kód pro implementaci obou tříd.
  * Je dost možné, že obě třídy budou mít nějaké společné části. V takovém případě doporučujeme (jak je naznačeno v ''example_mdp.py'') extrahovat sdílené části do společného předka obou tříd:<code python>
class MDPAgent:
    # Parts common to both methods/agents
    ...
    
class ValueIterationAgent(MDPAgent):
    # Parts specific for value iteration
    ...
    
class PolicyIterationAgent(MDPAgent):
    # Parts specific for policy iteration
    ...
</code>

===== Odevzdání =====
  * Termín odevzdání úlohy najdete v [[https://cw.felk.cvut.cz/brute|BRUTE]], úloha ''08-MDPs''.
  * Odevzdejte modul ''mdp_agent.py'', příp. ZIP archiv s modulem ''mdp_agent.py'' a dalšími vámi vytvořenými moduly, které váš agent potřebuje/importuje. **Tyto soubory musí být v kořeni archívu, archív nesmí obsahovat žádné adresáře!** Neodevzdávejte žádné moduly, které jste dostali od nás!

===== Hodnocení =====
Seznamte se s [[courses:b3b33kui:semestralni_ulohy:3_mdp:hodnoceni|bodovým hodnocením]] úlohy.