この記事では、強化学習におけるモンテカルロ法について紹介します。
前回の記事では、完全なモデルと無限の計算リソースという非現実的な前提を必要とする、 マルコフ決定過程（MDP）を解くための動的計画法アプローチについて説明しました。 この記事では、最適なポリシーを近似するための別のアプローチである モンテカルロ法 を紹介します。 動的計画法とは異なり、モンテカルロ法ではモデルを必要とせず、ブートストラッピングも使用しません。
モンテカルロ推定
動的計画法が完全なモデルを必要とする理由は、次の状態の価値を最大化する次の行動を選択するために、 状態価値の推定値を利用するためです。これを行う代わりに、エピソードにおいてエージェントが達成した収益の平均を取ることで、 環境との相互作用のみから状態行動価値を推定することができます。 そして、各時間ステップで推定された状態行動価値を最大化する貪欲なポリシーを採用することができます。
このようにエピソードをシミュレーションするアプローチは、完全なモデルの前提を回避するだけでなく、 無限の計算リソースの前提も取り除きます。すべての状態価値を更新せずに、訪問される確率の高い重要な状態に焦点を当てます。 しかし、この方法にはすべての可能性を探索することが困難であるという基本的な課題があります。 開始時のポリシーが特定の行動を選択する際に決定論的である場合、エージェントは他の選択肢を探索できず、 最適でないポリシーに固着してしまう可能性があります。
この問題は、探索と活用のトレードオフとして知られており、環境とのシミュレーションされた相互作用から状態行動価値を近似するすべてのアプローチに共通する問題です。 この問題に対処する単純な方法は、"探索的開始"を仮定することです。これは、エージェントが任意の状態行動ペアから開始でき、 エピソード数が無限に近づくにつれてすべての状態を訪問することを保証します。
探索的開始の仮定は時として有用ですが、このような非現実的な仮定に依存することは多くの場合合理的ではありません。 そのため、通常は探索を可能にする確率的ポリシーを利用する2つの実践的なアプローチ、 オンポリシー法 と オフポリシー法 に頼ります。
オンポリシーモンテカルロ法
オンポリシー制御法は、-貪欲ポリシーを利用します。これは非貪欲行動に非ゼロ確率 を、そして貪欲行動に残りのを割り当てます。 そのため、最も高い状態行動価値推定値を持つ貪欲行動が大部分で選択される一方で、 他のすべての行動が探索される機会も残されます。ここでは、エピソードからの収益の平均を取るポリシー評価と、 貪欲行動に可能な限り大きな確率を割り当てるポリシー改善を利用することで、 最良の-ソフトポリシー（を割り当てるポリシー）に近づくことを目指します。
が依然として成り立つため、-ソフトポリシーの中で最良のものに到達できることが保証されています。
言い換えれば、ポリシー改善フェーズで非貪欲行動のいずれかを選択するの確率を必ず割り当てることで、
ポリシー評価フェーズ中に他の選択肢を探索する機会を常に持つことができます。
ここでは、最適なポリシーと同義である最良の-ソフト（-貪欲）ポリシーに必ず到達することが保証されています。
以下はFrozenLakeEnvironmentのためのオンポリシー制御法のコード実装例です：
def on_policy_mc_control(env, num_episodes, epsilon):
Q = np.zeros([16, 4])
n_s_a = np.zeros([16, 4])
stats = 0.0
for episode in range(num_episodes):
state, _ = env.reset()
done = False
results_list = [] # 状態と行動を保存
result_sum = 0.0
# ポリシー評価
while not done:
# Epsilon貪欲ポリシー (if elseを用いた実装)
if np.random.rand() > epsilon:
action = np.argmax(Q[coord_to_num(state), :])
else:
action = env.action_space.sample()
new_state, reward, done, _, _ = env.step(action)
results_list.append((coord_to_num(state), action))
result_sum += reward
state = new_state
# ポリシー改善 (Qをアップデートする実装)
for (state, action) in results_list:
n_s_a[state, action] += 1.0
alpha = 1.0 / n_s_a[state, action]
Q[state, action] += alpha * (result_sum - Q[state, action]) ## 実行中の平均
stats += result_sum
if episode % 500 == 0 and episode != 0:
print(f"episode: {episode}, success: {stats/episode}, epsilon: {epsilon}")
print(f"episode: {episode}, success: {stats/episode}, epsilon: {epsilon}")
env.close()
return Q
num_episodes = 100000
epsilon = 0.4
Q = on_policy_mc_control(env, num_episodes, epsilon)この関数は状態行動価値の近似を更新し、それによって-貪欲ポリシーを更新します。 プロセスをシンプルにするため、ポリシー改善中に真の平均ではなく、実行中の平均を取ります。 状態行動価値から、以下のように-貪欲ポリシーを得ることができます。
def epsilon_greedy_policy_from_Q(Q, epsilon):
done = False
policy = np.ones((16, 4), dtype=float) / 4
state, _ = env.reset()
while not done:
action = np.argmax(Q[coord_to_num(state), :])
policy[coord_to_num(state)] = np.ones((4,), dtype=float) * epsilon / 4
policy[coord_to_num(state), action] = 1 - epsilon + epsilon / 4
state, reward, done, _, _ = env.step(action)
return policy
policy = epsilon_greedy_policy_from_Q(Q, epsilon)オンポリシー制御法は、報酬の推定に経験を利用し、探索のために非貪欲行動に非ゼロ確率を割り当てながら、 DPアプローチと同じスキームを使用するため、比較的理解しやすいものです。 実践では、探索を減らし活用を増やすためにの値を徐々に減少させることができ、 これはアニーリングと呼ばれます。
オフポリシーモンテカルロ法
オンポリシーとは、ポリシー評価とポリシー改善の間で同じポリシーを使用することを意味します。同じポリシーを使用するため、 必然的に-貪欲ポリシーに落ち着くことになり、これは完全に最適ではないかもしれません。 例えば、上記のコードは穴に落ちることに対して依然としてを割り当てるポリシーとなります。 オフポリシー制御法は、確率的な行動ポリシーで探索を可能にしながら、改善後には決定論的な目標ポリシーになるように、 重要度サンプリングを用いて二つのフェーズで異なるポリシーを使用することを目指します。
重要度サンプリング比 に従って報酬に重みを付けることで、オフポリシー学習を実現できます。 この比は、目標ポリシーと行動ポリシーの下で同じ一連の状態と行動を観察する相対確率に対応します。 開始状態が与えられた場合、以下が重要度サンプリング比となります：
その後、この比率で報酬をスケーリングし、単純平均または重み付き平均を取ることができ、 これらはそれぞれ 通常重要度サンプリング と 重み付き重要度サンプリング と呼ばれます。 スケーリングされた報酬が無限の分散を持つ場合、通常重要度サンプリングは無限の分散を持つ可能性がありますが、 重み付き重要度サンプリングはそうではないため、実践では重み付き重要度サンプリングが広く好まれます。 重みを計算し、重みの累積和を保持することで、エピソードの末尾から重み付きサンプリングを段階的に実装できます。
状態行動価値は、をに置き換えることで、適切な重み付き重要度サンプリングを適用するように更新できます。 以下は、行動ポリシーとして-貪欲ポリシーを、目標ポリシーとして決定論的な貪欲ポリシーを使用する、 重み付き重要度サンプリングを用いたオフポリシー法のコード実装例です。
def off_policy_mc_control(env, num_episodes, epsilon):
Q = np.zeros([16, 4])
C = np.zeros([16, 4]) # 重みつき重要度サンプリングの累積和
stats = 0.0
for episode in range(num_episodes):
state, _ = env.reset()
done = False
result_list = []
result_sum = 0
# Epsilon貪欲ポリシーを用いたポリシー評価
while not done:
# 行動ポリシー
if np.random.rand() > epsilon:
action = np.argmax(Q[coord_to_num(state), :])
else:
action = env.action_space.sample()
new_state, reward, done, _, _ = env.step(action)
result_list.append((coord_to_num(state), action))
result_sum += reward
state = new_state
# 重みつき重要度サンプリングによるポリシー改善
W = 1.0 # 重要度サンプリング比
# エピソードを末尾から遡る
for t in range(len(result_list)-1, -1, -1):
state, action = result_list[t]
C[state, action] += W # 累積和の更新
if C[state, action] > 0:
Q[state, action] += (W / C[state, action]) * (result_sum - Q[state, action])
# 重要度サンプリング比を用いた重みの更新
best_action = np.argmax(Q[state, :])
if action != best_action:
break # 目標ポリシーは貪欲でない行動の場合ゼロ
# 行動ポリシーの確率：ランダムな行動の場合epsilon/num_actions, 貪欲な行動の場合(1-epsilon)+epsilon/4
behavior_prob = epsilon/4 if action != np.argmax(Q[state, :]) else 1-epsilon+epsilon/4
W *= 1/behavior_prob # 重みの更新
stats += result_sum
if episode % 500 == 0 and episode != 0:
print(f"episode: {episode}, success: {stats/episode}, epsilon: {epsilon}")
print(f"episode: {episode}, success: {stats/episode}, epsilon: {epsilon}")
env.close()
return Q
Q = off_policy_mc_control(env, num_episodes, epsilon)オフポリシーモンテカルロ制御法は、非貪欲行動の後のエピソードの末尾からしか学習できない（if action != best_action: break）ため、
オンポリシー法よりもはるかに遅く収束する傾向があります。実際、上記のアルゴリズムは、同じエピソード数でオンポリシー法が達成する報酬の10分の1しか達成できません。
結論
この記事では、以前に説明したDPアプローチとは異なり、モデルフリーでブートストラッピングを使用しないモンテカルロ制御法について説明しました。 また、十分な探索を維持するためのオンポリシーとオフポリシーの制御法についても説明しました。 次の記事では、モンテカルロ法のように経験から学び、DPアプローチのようにブートストラッピングを利用するアプローチについて説明します。
リソース
- cwkx. 2022. Reinforcement Learning 5: Monte Carlo methods. YouTube.
- Sutton, S. R. & Barto, G. A. 2015. Reinforcement Learning: An Introduction. Stanford.