[5M1-GS-2b] Machine learning

10:00 AM - 10:15 AM JST(1:00 AM - 1:15 AM UTC)

[5M1-GS-2b-05] Exhaustive Enumeration of Policies in Markov Decision Processes Using SeqBDDs

〇Kotaro Ishihara¹, Kazuma Fuchimoto², Maomi Ueno¹ (1. The University of Electro-Communications, 2. The National Center for University Entrance Examinations)

Keywords:

Reinforcement Learning,Markov decision process,Sequence binary decision diagrams

マルコフ決定過程(MDP)は，状態の観測，行動の選択，および報酬を伴う逐次的意思決定をモデル化する枠組みである．強化学習は，このMDPに基づく逐次的意思決定問題を解くための機械学習手法である．本研究では，MDPにおけるすべての到達可能な行動列の集合をSequence Binary Decision Diagram(SeqBDD)を用いて圧縮して列挙，シミュレートし行動を選択することを提案する．SeqBDDは，列の集合を効率的に表現および操作できる二分木データ構造である．提案手法は，すべての行動列のシミュレーション結果から行動を選択するため，長期的な視野を持ち，探索漏れを削減するとともにシミュレーションの偏りがない学習を可能にする．本研究では，有限の行動集合を持つMDPにおいて，SeqBDDを用いてhステップ先までの全行動列の集合を列挙し，シミュレーション環境にてその性能を評価した．提案手法は膨大な行動系列を効率的に管理することが可能であり，従来の多くの深層強化学習モデルを改善した．