強化学習（Reinforcement Learning）のバックアップ(No.7)

「.NET 開発基盤部会 Wiki」は、「Open棟梁Project」,「OSSコンソーシアム .NET開発基盤部会」によって運営されています。

戻る（人工知能（AI）
- 機械学習（machine learning）
- 深層学習（deep learning）
- 強化学習（Reinforcement Learning）
- 生成系AI（Generative AI）

目次 †

↑

概要 †

（Reinforcement learning）

↑

歴史 †

「ロボットの行動計画」を土台とした
ボードゲーム（オセロ・チェス・将棋・囲碁）の例

↑

探索木 †

ボードゲームをコンピューターで解く基本は探索だが、
組み合わせの数が天文学的な数字に事実上すべてを探索しきれない。
知識や経験（ヒューリスティックな知識）を利用して、
自分が有利か不利かを示すスコア（ゲーム盤の状態）を情報を計算し、
コスパ（コスト・パフォーマンス）の観点から効率の良い探索を行うようにすることができる。

↑

ミニマックス探索 †

最悪の場合の利得を考え、これが最大となる戦略を選択する。

ゼロサム2人ゲーム
- ゲーム理論で扱われるゲームの中で最も簡単かつ基礎的なもの。
- 2人のプレーヤーで争われ、一方の利得が他方の損失となる形のゲーム。

混合戦略

「絶対優位」「絶対劣位」「ナッシュ均衡」で戦略が定まらない同時進行ゲームで、
- さまざまな打ち手を混ぜて使う。
- 自分の動きをランダム化する戦略。

例えば、サッカーのペナルティ・キック

キッカーが左サイドを狙った時、キーパーが
・右に動けば成功率は高い
・左に動けば成功率は低い

キッカーが右サイドを狙った時、キーパーが
・右に動けば成功率は高い
・左に動けば成功率は低い

キーパーの動きをランダム化することによりシュート成功率を低めることができる。

ミニマックス定理
ゲーム理論の最も標準形となる“ゼロサム2人ゲーム”の主要定理。

マクシマックス原理にのっとった戦略
- ハイリスク、ハイリターンのイメージ
- 戦略案毎の「最良の結果」に注目し、最良中で最大の利得を与える戦略を選択する

ミニマックス原理にのっとった戦略
- ローリスク、ローリターンのイメージ
- 相手がマクシミン原理を採ることを前提としたもの。
- 戦略案毎の「最良の結果」に注目し、最良中で最小の利得を与える戦略を選択する
- それによって得られる利得を「ミニマックス値」と言う。

マクシミン原理にのっとった戦略
- ローリスク、ローリターンのイメージ
- 相手がミニマックス原理を採ることを前提としたもの。
- 戦略案毎の「最悪の結果」に注目し、最悪中の最大の利得を与える戦略を選択する。
- それによって得られる利得を「マクシミン値」と言う。

ゼロサム2人ゲームで混合戦略を許した場合、

双方のプレーヤーが戦略配分を合理的に行う限り、
（両者がともに合理的な行動、すなわち相手も十分に利口
であると考えて自己の損失を最小限にする手をとるならば）

両者が均衡する最適戦略が必ず存在する
（混合戦略の範囲内で両者のとるべき戦略は定まる）

ミニマックス値とマクシミン値が一致する点を「鞍点」
鞍点を持つならば純粋戦略で均衡点を見出すことができる。
鞍点が存在しない場合も混合戦略の組み合わせと確率をミニマックスで考えると、
両プレーヤーにとっての最適戦略（妥協点）が見つかる。

相手の手番で自分に大きな損害が出る or 自分の手番で相手に大きな利得が出る盤面を得る選択を見つけたら、
その選択（に辿り着く選択）を行わないので、探索を中断し計算回数を減らす（αβ法のα or βカット
- αカット：相手の手番で自分に大きな損害が出る盤面を得るに辿り着く選択以下を探索しない。
- βカット：自分の手番で相手に大きな利得が出る盤面を得る選択以下を探索しない。

↑

モンテカルロ法 †

19路盤でない9路盤でもコンピュータがアマチュア初段に勝つのは難しかった。
探索の計算量ではなく、ゲーム盤のスコアに問題があることが解ってきた。
スコアをプレイアウト（ランダムなブルートフォース、モンテカルロ法）に変更。
- スコア（ゲーム盤の状態）を情報を計算する方法。
- ただし、計算量が多いので19路盤では実行できなかった。

↑

強化学習 †

↑

深層強化学習 †

強化学習はQテーブルなど離散的な状態表現での手法。
連続量の入出力を扱う関数近似器にニューラルネットワークを使う。

↑

手法 †

↑

深層Q学習 †

行動価値関数（Q値、Q関数とも）をQテーブルではなく
CNNなどのニューラルネットワークにより表現。

DQN（Deep Q-Network）が最も基本的な手法

↑

ゲーム攻略 †

具体
- TVゲーム攻略
- 完全情報ゲーム攻略（AlphaGo

工夫
自己対戦による学習

↑

ロボティクス †

プログラミングで難しいタスク
直接的な教示が難しいタスク
単純労働などロボットによる労働代替

具体
- 自動運転
- 産業用ロボット制御

工夫
- 人間からの教示
- 物理シミュレーション（Sim2Real

↑

シミュレーション最適化 †

空調の制御
株式の自動取引
広告配信最適化
インターネット
例えば、PV（≒報酬）を向上させるサイトマップ設計（≒行動）

↑

改良されたアルゴリズム †

↑

ダブルDQN †

行動価値関数を過剰に評価する弱点を克服するため、
行動選択と関数の評価を別のネットワークで行う。

Target-Q-network：行動価値関数の評価
Q-network：最適な行動の選択

↑

デュエリング・ネットワーク †

強化学習のネットワーク構造を改良したモデル
状態行動価値Qではなく状態価値VとQからVを引いたアドバンテージVを学習

↑

ノイジー・ネットワーク †

ネットワークの重みにノイズを加えることで、広範囲の探索を実現
ε-greedy法では出来なかった広い空間の探索が出来るようになった。

↑

Rainbow †

DQN 以降に登場したいろいろな改良手法を全部乗せしたアルゴリズム

Double Q-learning
Prioritized Experience Replay
1. Proportional Prioritization
2. Rank-Based prioritization
Dueling networks
Multi-step learning
Distributional RL
Noisy Nets

↑

DeepMind? †

IBMのチェス専用スパコンDeep Blue（1989-2009）主任設計者の許峰雄は
チェスでの人類の敗北（1996）がより複雑な囲碁でも起きると予言（2007）し、
Google DeepMind?の開発したAlphaGoで現実となった（2015）。

↑

AlphaGo? †

DQNを用いた碁プログラム
- 基盤の状況認識にCNN（画像ではなく、盤面をベクトルとして表現）を使用
- 次の手の選択に、エンコード結果を利用したモンテカルロ木探索を使用

セルフプレイ
- 偏見に捕われず学習を進めた方が良い場合がある
- 過去の名人戦の棋譜を学習するのではなく0から学習する

AlphaGo?のアルゴリズム
AlphaGo?のアルゴリズムはAlphaGo? Master以前とAlphaGo? Zero以降で大きく異なる。

初期のアルゴリズムの基本アイデア

モンテカルロ木探索、評価関数、方策関数
（例１）単純なケース
・評価関数 = 自分の色の石の数
・方策関数 = 2手先読みして評価関数の値が上がるような手だけを残して探索する
（例２）単純なケース
・途中までは（例１）と同じ方針で枝刈りしながら探索
・途中で探索を打ち切り、そこから先はランダムに打てる手を打つ。
・これをｎ回実行して、勝利する回数が一番多かった手を選択する

問題と対策
・評価関数、方策関数がうまく作れない → ニューラルネットワークの使用
・なかなか学習が始まらない → Ph１教師あり学習、Ph２教師なし学習（強化学習）

AlphaGo? Zero以降のアイデア
- 人間を超越してしまうと、教師とするものがなくなる。
- 教師あり学習のフェーズを完全に取り払い、初めから強化学習を行った。

AlphaGo?のバージョン
DeepMind?社の囲碁ソフトウェアであるAlphaGo?のバージョン

AlphaGo? Fan
- 初代バージョン。GPU176台を使用。
- 2015/10、コンピュータ囲碁として初めてプロ棋士に互先での勝利（5戦5勝）。

AlphaGo? Lee
- 2代目バージョン。TPU48台を使用。
- 2016/3、李世ドルと戦い、4勝1敗と勝ち越した。

AlphaGo? Master
- 3代目バージョン。TPU4台を使用。
- 名称はオンライン上でのアカウント名（当初はMagister/Magist）に由来
- 2016/12/29 - 2017/1/4、プロ囲碁棋士にオンライン対局で60連勝。
- 2017/5、人類最強の棋士である柯潔に3戦全勝。

AlphaGo? Zero
- 2017/10/19、4代目バージョン。TPU4台を使用。
- 棋譜やビッグデータを必要とせず自己対局によって強化される。
- 全くの初心者の状態から3日間の学習でAlphago Leeのレベルに到達
- 21日目にMasterと肩を並べ40日間の学習後、
  ・AlphaGo? Leeには100戦全勝
  ・AlphaGo? Masterには89勝11敗

AlphaZero?
- 2017/12、AlphaGo? Zeroの汎用バージョン
- トップチェスプログラム（Stockfish）、トップ将棋プログラム（elmo）を破る。

↑

A3C †

（Asynchronous Advantage Actor-Critic）

DeepMind?のVolodymyr Mnih(ムニ)のチームが提案した強化学習の学習法の一つ

特徴

同一の環境で
複数のエージェントが
非同期に学習すること

A3Cの名前の由来

Asynchronous	複数のエージェントによる非同期な並列学習
Advantage	複数ステップ先を考慮して更新する手法
Actor	方策によって行動を選択
Critic	状態価値関数に応じて方策を修正

※ Actor Critic

非同期な並列学習
- 複数エージェントが並列にrollout(ゲームプレイ) を実行し、勾配計算を行う。
- その勾配情報をもって、global networkのパラメタ・サーバを更新する。
- 各エージェントは定期的にlocal networkの重みをglobal networkの重みと同期する。