今回のブログではマルチエージェントシステムの基礎であるマルコフ決定過程について解説していこうと思います。機械学習は主に教師あり学習、教師なし学習、強化学習の三種類に分類されますが、マルコフ決定過程は三つ目の強化学習における基本的な考え方です。概要、定義、具体例、代表的な学習方法などについて述べていきます。
はじめに
今回のブログではマルチエージェントシステムの基礎であるマルコフ決定過程について解説していこうと思います。機械学習は主に教師あり学習、教師なし学習、強化学習の三種類に分類されますが、マルコフ決定過程は三つ目の強化学習における基本的な考え方です。概要、定義、具体例、代表的な学習方法などについて述べていきます。
概要
マルコフ決定過程は状態遷移が確率的に変動していく確率過程の一種です。
ここで、あるエージェントが行動をとり、その結果報酬を受け取る状況を考えていきます。エージェントはある状態からスタートし、選ぶことのできる行動の中から一つ選び行動します。その結果報酬を受け取り、状態と行動に依存して確率的に次の状態へと移ります。この状態→行動→状態・・・を繰り返していくことがマルコフ決定過程です。
マルコフ決定過程の定義
マルコフ決定過程（MDP）は以下の4つの要素\((S, A, P, R)\) で表されます。
S : 状態の有限集合（エージェントが取りうる状態の集合）
A : 行動の有限集合（エージェントが選択できる行動の集合）
P : \(S \times A \times S \rightarrow [0,1] \) 遷移関数（ある状態 \(s\) の元で行動 (a\) を取ったときに状態 \(s’\) に遷移する確率）
R :\( S \times A \times S \rightarrow \mathbb{R}\) 報酬関数（ある状態 \(s\) から行動 \(a\) を取り状態 \(s’\) に遷移した時、得られる報酬）
この4つの要素によりマルコフ決定過程が規定され、その空間内をエージェントが動いていきます。
具体例
問題設定
ある小売店の在庫管理を考えていきます。毎日、一定の需要があり店舗は需要に応えるべく商品を注文します。この時、店舗は品切れだけでなく在庫保持コストを考えながら意思決定を行っていきます。
- 状態の有限集合
ここで、店舗の在庫は０から１０個まで保管できるとします。したがって状態有限集合は
$$ \mathbf{S} = (0,1,2,\dots,10) $$
です。
- 行動の有限集合
店舗は需要に合わせて注文を行うことができます。これがエージェントの行動です。いま、各状態で０から５個まで注文できるとします。したがって行動有限集合は
$$ \mathbf{A} = (0,1,2,\dots,5) $$
です。
- 遷移確率
店舗は在庫状態をみて、注文をかけますが需要量に応じて時期の在庫量が決定されます。この需要量は確率的に変動するので遷移確率となります。
例
$$ P(2,5,3) = 0.3 $$
この例は在庫が２であるとき、5個発注をかけ、時期の在庫量が３になるときの確率が30%であることを表しています。
- 報酬関数
ここで店舗は在庫保持コスト、在庫切れペナルティを抑えることを考えます。
- 在庫保持コスト
$$ H(s) = h \times s $$
ｈは在庫一個当たりの保持コスト
ｓは各状態の保有在庫数
を表します。
- 在庫切れペナルティ
$$ B(s,D) = b \times max(0,D-s) $$
ｂは不足一個当たりのペナルティ
Dは需要を表し、\(D-s > 0\)の時、不足が発生していることを表します。
として定義すると報酬関数はこれらを組み合わせて
$$ R(s,D) = -(H(s) + B(s,D)) $$
となります。
例
- 在庫一個当たりの保有コスト\(:h=1\)
- 不足一個当たりのペナルティ\(:b=10\)
今、在庫5個であり、注文３個行ったところ注文が5個であった場合、報酬関数は
$$ R = -((1 \times 8) + (10\times0)) = -8 $$
と計算されます。
以上のように店舗は現在の在庫数を見て、注文を行い、確率的に需要が決定され次の在庫数に移っていくことを繰り返します。
終わりに
このように、状態と行動に応じて次の状態が確率的に決まりますが、この過程において行動の決定方法のルールを決め、「より良い」報酬を得ていくことがエージェントの目的になります。
ではそのような報酬を得るためのルールはどのように求められるのでしょうか。次回のブログではエージェントの「学習」について扱っていきます。
