決定的な遷移をもつマルコフ決定過程の強多項式時間アルゴリズム

黒川 健太

（指導教員：牧野 和久 准教授／数理情報第2研究室）

研究概要

マルコフ決定過程とはマルコフ過程にアクションと報酬を追加したものであり，最大報酬が得られるアクションを強多項式時間で求めるアルゴリズムがある．本研究では，そのアルゴリズムの理論値と実測値との比較のために数値実験を行った．

理論値と実測値の計算量の比較

卒論の感想

どのようにしたら良いのか戸惑った時が度々ありましたが，研究室の多くの人たちの支えによって完成させることが出来ました．心より感謝いたします。