3. Markovské rozhodovací procesy

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

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:

• 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 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.

• Doporučujeme vytvořit si pro úlohu nový pracovní adresář. Zprovozněte si v něm aktualizovanou verzi balíčku kuimaze2.
• Seznamnte se s prostředím 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:

  class MDPAgent:
      # Parts common to both methods/agents
      ...
   
  class ValueIterationAgent(MDPAgent):
      # Parts specific for value iteration
      ...
   
  class PolicyIterationAgent(MDPAgent):
      # Parts specific for policy iteration
      ...

• Termín odevzdání úlohy najdete v 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!

Seznamte se s bodovým hodnocením úlohy.