Parameterized Action Space を用いた強化学習手法と適用事例の紹介

この記事は DeNA 23 新卒 Advent Calendar の16日目の記事です．



https://qiita.com/advent-calendar/2022/dena-23-shinsotsu

こんにちは！[ザビカエル](https://twitter.com/xavifrog)です．大学院で主に自然言語処理や強化学習といった分野を生息地とし，交渉対話システムをテーマに研究しています．

本記事では強化学習で用いられる特殊な行動空間[^行動空間]であるParameterized Action Space と，2022年12月時点で公開されている適用事例の一部をご紹介いたします．強化学習を触ったことがある方をメインターゲットとしますが，機械学習を触ったことがない方でも理解できるように努めたつもりです(特に後半の事例紹介)．厳密性を欠いている部分があると思いますので，必要に応じて元論文を参照いただければと存じます．

強化学習初心者の方は以下のような先人による入門資料などをご覧いただいてから読み進めるとわかりやすいかもしれません．

https://www.slideshare.net/TatsuyaMatsushima/2020deep-learning-237319784

# 深層強化学習
強化学習はAI(Agent)がシュミレータや現実世界といった"環境"とのインタラクションを行うことでデータ(経験)を収集し，事前に定義された評価関数(報酬関数)によって求められる評価値(期待収益)を最大化するように学習を行う手法[^オフライン強化学習]で，その中でも特徴抽出などにDeep Learningを用いたものが深層強化学習と呼ばれます． 具体的な適用例には将棋AIや自動運転技術あり，実問題への応用が日々進んでいる分野です．
機械学習の一般的な手法である教師あり学習と比較すると，強化学習はデータを自前で収集するため，大量のデータを事前に用意する必要ありません．ですが，シュミレータや報酬関数の設計でドメイン知識が要求される他，シュミレータ上では良好な動作をするのに実運用では望ましい動作ができない問題(ドメインシフト)に悩まされるなど，銀の弾丸というわけでもありません．個人的な感覚として，一般的な機械学習よりもプロダクトへの導入ハードルは高く，場面を選ぶイメージがあります.


なお，DeNAでは逆転オセロニアというプロダクトに強化学習を導入した事例を公開しています．また，[HandyRL](https://github.com/DeNA/HandyRL)という並列強化学習ライブラリの公開も行っています．

https://engineering.dena.com/blog/2021/09/reinforcement-ga-othellonia/

https://engineering.dena.com/blog/2021/12/distributed-reinforcement-learning-with-handyrl/

https://techcon2022.dena.dev/spring/session/matchup-ai-reaches-top-level/

一人の強化学習学徒としては入社後に裏側を見せていただく機会があればいいなーという気持ちです．
閑話休題．


さて，深層強化学習は様々な観点で分類されます．

- モデルベースとモデルフリー
- 連続行動空間と離散行動空間
- 価値ベースと方策ベース
- オンポリシーとオフポリシー
- Actor-Critic型と非Actor-Critic型

本記事ではParameterized Action Spaceの理解に必要な部分のみの説明に留め，上記のカテゴライズや各手法の詳細説明は先人が体系的にまとめてくださっている記事[^ここで育ちました]などに任せます.

https://qiita.com/shionhonda/items/ec05aade07b5bea78081



## 離散行動空間と連続行動空間
このセクションでは強化学習で定義される行動空間の違いについて，具体的な手法とタスクのイメージを踏まえてご説明します． 

### 離散行動空間(Discrete Action Space)
最初に離散行動空間について説明します．離散行動空間はAgentが取りうる行動の全てが事前に有限個定義され，そこから選ぶ行動空間です．例えば将棋のコマはあらかじめ動ける場所が決まっており，いずれかを選ぶ形であるので離散行動空間です．この時，各行動は独立しており，仮に大小関係が存在していたとしてもAgent側は直接は考慮しません．

離散行動空間に対応した手法で代表的なのが[Deep Q-Network(DQN)](https://arxiv.org/abs/1312.5602)です．DQNはある状態が入力されると，各行動ごとに将来的に得られる収益(行動価値)を見積り，その中で最も得られる収益が高いと見積もったものを次の行動とします(価値ベース手法)．実際に例で考えてみましょう． 下図は上から落ちてくる剣を回避するゲームで，下の段3マスがAgentの行動範囲です．Agentは"左移動"，"動かない"，"右移動"という行動を選択でき，Agentが一回行動を行なった後に剣が一段落ちてくるとします．もし行動後に剣が刺さったら報酬0かつゲームオーバー，生き残れば報酬1で継続します．説明の簡易化のため，2回行動した時点でエピソードを終了するものとします．

![DQN.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/323a31ee-ce5e-1e49-36cf-5e6b1d1972e6.jpeg)


行動価値を完璧に見積もれると仮定すると，まず"動かない"はすぐにゲームオーバーになるため行動価値は0です．それに対し，"左移動"は1ターン生き残れますが，その後に生存ルートがないため，2ターン目にゲームオーバーになります．この場合の行動価値は1×割引率(例では0.99)[^割引率]+0×割引率<sup>^2</sup>で求められます．2ターン生き残ることができる"右移動"は1×割引率 + 1×割引率<sup>^2</sup>です．つまり上図時点のAgentは"右移動"の行動価値を最も高く見積もるように学習を進める必要があります．
DQNは Atari 2600というレトロゲーム環境群の一部で人間よりも優れたスコアを達成しました．深層強化学習発展の起点となった手法であり，そのインパクトから2015年に世界で最も権威のある論文誌の一つである[Natureに掲載](https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf)されています．

### 連続行動空間(Continuous Action Space)
次に連続行動空間について説明します．連続行動空間はAgentが取る行動が連続値である行動空間です．レバーやスロットルを用いるような，アナログ的に量の調整をするタスクに対して適用されます．

連続行動空間のための手法で代表的なものの一つが[Deep Deterministic Policy Gradient(DDPG)](https://arxiv.org/abs/1509.02971)です．DDPGは次の連続行動を決定するActorと，状態及び決定された行動から行動価値を求めるCritic(Q-Network)の二つから構成されます(Actor-Critic型の価値ベース手法)．行動価値の見積もりを正確にするためのCriticの学習と，その時点のCriticが出力する行動価値を最大化するActorの学習を交互に行うことで最適方策に近づけます．

下図はAgentがジャンプによって落とし穴を回避し，その先にあるお寿司の獲得を目指す環境を図示したものです．落とし穴に落ちてしまった場合はゲームオーバーなので，Agentはジャンプする角度とジャンプ力を調整して落とし穴を飛び越える必要があります．
![DDPG.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/2a3c4e9a-6d1e-9df4-6cfc-619ae05973a5.jpeg)

上図のタスクを離散行動空間で扱うことも可能ですが，どの粒度で離散化するかという問題や大小関係の喪失によって学習に手間がかかります．今回は簡単な環境なので対応できそうですが，現実で動かすロボットの学習などでは組み合わせ爆発により学習が困難です．このように特定の範囲内で細かく値の調整がしたい場合は連続行動空間が用いられます．


## サッカーで考える
上記のように行動空間の選択は適材適所です．では，昨今話題のサッカーをするAgentを強化学習で作る場合はどちらを採用するのが良いでしょうか？ なお，対象はキーパー以外とします．
何が必要かを考えると，以下になると思います．

- 走る
- ボールを蹴る

かなり大雑把で選手間の接触を考慮していませんが，最低限これができればサッカーが成立するはずです．

### 離散行動を採用した場合
離散行動は角度や強さといったパラメータの調整ができないため，あらかじめ定義しておく必要があります．今回は角度は45度ごと，蹴る強さや速度は全力を1として，0.25ごとに定義するとしてみましょう．まず，走る場合を考えてみます．


- 走る(8×4 通り)
  - 0度の方向に1.0の速度で走る
  - 0度の方向に0.75の速度で走る
  - 0度の方向に0.50の速度で走る
  - 0度の方向に0.25の速度で走る
  - 45度の方向に1.0の速度で走る
  - ...
  - 315度の方向に0.25の速度で走る

走る時は"角度"と"速度"という尺度で考えれば良さそうなので，8×4 = 32の離散行動が必要だとわかります．これに対して，ボールを持っている時は考えることが多いです．例えば仲間にパスを出す場合を考えると，単純に角度で考えるよりも味方のいる座標に向かって蹴るのが望ましいはずです．また，ドリブルとシュートは目的が異なるので区別するとより良くなると思います．なお，シュートは狙う場所を6つに分割(左上, 左下, 中央上, 中央下, 右上, 右下)するとします．

- ドリブル(8×4 通り)
  - 0度の方向に1.0の速さでドリブル
  - ...
  - 315度の方向に0.25の速さでドリブル
- 味方にパスを出す(10×4 通り)
  - 仲間Aに1.0の強さでパス
  - ......
  - 仲間Jに0.25の強さでパス
- シュートを打つ(6×4 通り)
    - 左上を狙って，1.0の強さでシュート
    - ...
    - 右下を狙って，0.25の強さでシュート
   
さて，考えるべき行動が多くなってきました．ここで，これまで定義してきた角度や強さの粒度では大雑把すぎて世界クラスで戦えないことに気がつきました．角度を1度単位，強さや速さを0.01単位に変更してみましょう．

- 走る(360×100 通り)
  - 0度の方向に1.0の速度で走る
  - ...
  - 0度の方向に0.01の速度で走る
  - ...
  - 359度の方向に0.01の速度で走る
- ドリブル(360×100 通り)
  - 0度の方向に1.0の速さでドリブル
  - ...
  - 359度の方向に0.01の速さでドリブル
- 味方にパスを出す(10×100 通り)
  - 仲間Aに1.0の強さでパス
  - ......
  - 仲間Jに0.01の強さでパス
- シュートを打つ(6×100 通り)
    - 左上を狙って，1.0の強さでシュート
    - ...
    - 右下を狙って，0.01の強さでシュート

全てを合わせると79000通りという膨大な行動数になってしまいました．つまり，自分の行動だけでも79000<sup>^time_step</sup>分のパターンが生まれることになります．更に味方や敵の動きが毎回異なることも加味すると，学習には多大なコストがかかることが考えられます．また，モデルの出力次元数が79000になるということなので，モデルサイズが非常に大きくなりメモリを圧迫します．加えて，離散化しているためにそれぞれの行動の大小関係をモデルが直接考えることはできません．これは重大な情報の損失です．


### 連続行動を採用した場合
では連続行動を選ぶ場合はどうなるでしょうか？ 連続行動は角度や強さといった量の調整ができる行動空間なので，離散行動の時に課題だったパラメータを離散化する際の粒度問題は回避されます．

- 走る(A,Bという2つのパラメータ[連続行動])
  - A度の方向にBの速度で走る

これで取りえる行動数が増えるという問題は回避されました．しかし，本当にそれだけでしょうか？
連続行動は量の違いしか考えられないので，"ドリブル"や"味方にパスを出す"，"シュートを打つ"という戦術の区別ができず，同じボールを蹴るという行為にまとめられることになります．

- ボールを蹴る(C,Dという2つのパラメータ[連続行動])
  - C度の方向にDの強さで蹴る

これは調整が困難かつ非常に時間がかかることが予想されます． 味方へのパスやシュートの際にシステムの補助がなく，アナログスティックだけで角度や蹴る強さを調整するサッカーゲームを考えてみてください．一部のゲーマーにはウケるかもしれませんが，大衆には難しすぎて途中でやめる人が続出しそうです．


### 利点/欠点のまとめ
それぞれをまとめると


|  | 利点 | 欠点 |
| --- | --- |---|
| 離散行動 | パスやシュートといった戦術的な概念の区別ができる | 角度や強さといったパラメータを柔軟に変えることができない |
| 連続行動 | 角度や強さを柔軟に変えられる | 戦術的な違いを考慮できない | 



ということになり，どちらを採用しても問題を抱えることがわかります．
さて，今販売されているサッカーのコンシューマーゲームを考えてみてください．その際に使うコントローラーはボタンも，アナログスティックも搭載していますよね？ 概念的な違いと量的な数値をどちらも決めるというのは現実世界でも良くあることで，上手く扱えると応用が効きそうです．
そんな時に有用なのがParameterized Action Spaceという行動空間です．


# Parameterized Action Space
Parameterized Action は離散値と，それに対応したパラメータ(連続値)で構成された行動のことです．サッカーの例で説明すると，"味方Aにパスを出す"か"シュートを打つ"かという戦術選択と，"味方Aにパスを出す"際の蹴る強さや，"シュートを打つ"際の蹴る強さ，角度という量の調整をどちらもやってしまうということです．ボタンしかなかったコントローラーにアナログスティックやトリガーを足すというイメージがわかりやすいかもしれません．Agentは全てのパラメータの推論後に離散行動を決定したり，それぞれを並列に推論することで離散行動と連続行動をどちらも決定します(詳しくは後述)．

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| パス | 蹴る強さ | 
| 走る | 角度, 速度 | 
| シュート | x座標, z座標, 蹴る強さ | 

これによって離散行動と連続行動がそれぞれを補い合い，欠点を克服することができます．
なお，強化学習は理論的な裏付けにマルコフ決定過程(Markov Decision Process; MDP)という確率過程を用いていますが，[Parameterized Action Spaceを提案した論文](https://arxiv.org/abs/1509.01644)ではMDPをParameterized Action Spaceを用いて拡張したParameterized Action Markov Decision Processes(PAMDPs)を提案することで対応しています．


# Parameterized Action Reinforcement learning
深層強化学習手法をParameterized Action Spaceに拡張した手法がいくつか提案されているのでご紹介いたします．なお，紹介する手法は全てモデルフリーです．

## Parametrized Deep Q-Network(P-DQN)

https://arxiv.org/pdf/1810.06394.pdf

最初に紹介する[P-DQN](https://arxiv.org/abs/1810.06394)はDQNとDDPGを組み合わせたような手法であるので，最初にそれらの手法をおさらいしていきます．

DQNは状態から各離散行動の行動価値を求める手法でした．
![DQN.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/323a31ee-ce5e-1e49-36cf-5e6b1d1972e6.jpeg)

それに対し，DDPGはActorで連続行動を決定し，Critic(Q-Network)で行動価値を推論する手法でした．
![DDPG.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/c081977d-7a8b-3b93-cf81-cad612cbc59f.jpeg)


本セクションで紹介するP-DQNは最初にActorで全てのパラメータを推定し，Critic(Q-Network)で各行動に対する行動価値を求めて離散行動を選択する手法です．
![p-dqn_only.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/f7a9a830-b8e3-f650-30f3-6dbd59314dd8.jpeg)
引用元: https://arxiv.org/pdf/1810.06394.pdf

元論文のモデル図だけではイメージが掴みづらいように感じたので別途図を用意しました．先程言及したサッカーで考えます．

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| パス | 蹴る強さ | 
| 走る | 角度, 速度 | 
| シュート | x座標, z座標, 蹴る強さ | 

P-DQNはActor-critic型の手法であるDDPGを拡張した手法のため，モデル構造はActor-critic型の亜種と言えます．まず最初にActorが各行動に付随するパラメータを推論します．
![P-DQN_overview①.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/f52f692c-acaf-b70c-1ec7-4169dec28752.jpeg)


Critic(Q-Network)は状態とActorによって推論されたパラメータを基に各離散行動に対する行動価値を推定します．

![P-DQN_overview②.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/8e04490b-9c5b-efbf-d9d9-b9d4208ac431.jpeg)

最後に最も行動価値の高い離散行動と，それに対応したパラメータを取り出すことで最終的な行動とします．
![P-DQN_overview③.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/ec976453-f3bb-54be-b8a7-c1b22ea9cad3.jpeg)




DDPGは連続行動に対する単一の行動価値を推定していましたが，P-DQNでは各行動に対する行動価値を推定することで離散行動の選択を実現しています．

## Multi-Pass Deep Q-Networks(MP-DQN)

https://arxiv.org/abs/1905.04388

さて，ここで問題が一つあります．それは行動価値の推定時，Critic(Q-Network)が全てのパラメータを参照していることです．サッカーの例で考えると，最終的に採用されたのは"ドリブル"ですが，行動価値の推定時には"パス"と"シュート"のパラメータも参照しています．パラメータはActorによる行動であるので，訓練時には"パス","シュート"のパラメータも行動価値を最大化するように学習されることになりますが，これは"パスをしたら失敗した．シュートのz座標が悪かったからだ"という論理的に間違った学習がされる可能性があるため望ましくありません．かといって，P-DQNはパラメータ決定->行動選択という順序であるので，必要なパラメータだけを推論するということもできません．複数のQ-Networkを用意するのも手ですが，学習コストや特徴空間の共有を失う点が問題になります.
それらに対応するために提案されたのが[MP-DQN](https://arxiv.org/abs/1905.04388)です．MP-DQNではActorで推論した全パラメータを離散行動の数だけ複製し，各離散行動に必要なパラメータ以外をマスク[^one-hot　ベクトルによるマスク]した上でCritic(Q-Network)に入力します．それぞれ求められた行動価値はマスクされなかったパラメータに対応した離散行動に対する行動価値のみ取り出され，同様の処理がされた他の離散行動の行動価値と比較されます． 単純に上記を行うだけでは行動数倍の時間が必要になりますが，バッチ計算で並列化することによって回避します．

![MP-DQN.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/065c59aa-77e2-304a-4d26-342541c2b48d.jpeg)
引用: https://arxiv.org/abs/1905.04388

サッカーの例で考えると以下の通りです．
![MP-DQN.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/3b5d3183-b1e3-def7-83b9-3db61816fb73.jpeg)


## Hybrid Actor-Critic

https://arxiv.org/abs/1903.01344

Actor-Critic型かつ方策勾配法を用いた手法をParameterized Action Spaceに拡張する手法も提案されています． まず，方策勾配法は報酬を基に方策そのものを改善する手法で，REINFORCE(非Acter-Critic)やA3C, PPOなどが該当します．

![A2C.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/77c54139-831a-3f0f-295d-a0c261119110.jpeg)

上図はActor-Critic型かつ方策勾配法を用いた手法で離散行動を扱った場合のモデル図です． Actorは次に取るべき行動はどれを表した確率分布(方策)を求め，Criticは状態価値[^状態価値]を推論します．なお，状態価値はどれくらいActorを更新するかを決定する値であるAdvantageの計算[^advantage]に用いられます．ここで，Actorの学習はAdvantageを定数として扱うこと[^誤差逆伝播しない]，Critcの学習はActorとは独立していることに注目すると，一つのCriticに対し複数のActorが存在していても問題がないことになります．更に，方策勾配法に基づいた手法は事前に設定する確率分布の種類によって離散行動(例. カテゴリカル分布)にも，連続行動(例. 正規分布)にも対応できます．

上記を考えを元に提案されたのがHybrid Actor-Criticです．このアーキテクチャは一つのGlobal Critic，連続行動を担当するContinuous Actor，離散行動を担当するDiscrete Actorで構成されます． 2つのSub-Actorは独立して行動を決定し，Global Criticが求めたAdvantageを共有して学習します．元論文では方策の更新に[PPO](https://arxiv.org/abs/1707.06347)を用いるH-PPOという手法が提案されました．

![hybrid_actor_critic.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/4cd8b0a1-4be8-7493-97a9-d557f0514703.jpeg)
引用元: https://arxiv.org/abs/1903.01344

離散行動と付随するパラメータ(連続行動)を別々に推論するため，相互作用が失われるのではないかと考える方もいらっしゃるかと思いますが，筆者の経験上，価格交渉対話<sub>[\(後述\)](#価格交渉対話)</sub>程度の複雑度であれば問題なく学習できます．また，上記を課題感に，先にパラメータを推定し，それを踏まえて離散行動を決定する方法も提案されています．

![hybrid_actor_critic_concatenate.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/50fef6c8-8171-0fcf-db68-a849d1f8ad21.jpeg)
引用元: https://cgdsss.github.io/pdf/SMC21_0324_MS.pdf

また，構造上，Actorが2つ以上であっても問題なく動作できることに着目し，階層構造を持つ行動空間[^階層構造を持つ行動空間]にも用いることができると述べられています．

![hybrid_actor_critic_advanced.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/709d0ed5-ba9e-9ae0-66a4-cc4881a42f6f.jpeg)
引用元: https://arxiv.org/abs/1903.01344

## Parameterized Action Soft Actor-Critic

https://dl.acm.org/doi/10.1145/3442381.3449862

[Soft Actor-Critic](https://arxiv.org/abs/1801.01290)をParameterized Action Spaceに拡張した手法も提案されています．Soft Actor-Criticは状態とActorによって求めた連続行動[^連続行動の求め方]に対し，Criticが行動価値を求めるという構造になっていました．ここで，離散行動用のActorを連続行動用のActorと並列に動作するように追加し，離散行動方策と連続行動，状態を結合したものから行動価値を推定する(joint Q function) ことでParamterized Action Spaceに対応する手法が提案されています．

![PA_SAC.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/4379a7e2-fa62-8c71-5df3-1d6dde8fb746.jpeg)
引用元: https://dl.acm.org/doi/10.1145/3442381.3449862


# 適用事例
このセクションでは実験用環境や論文で提案されている適用タスクの内容をかいつまんでご紹介いたします．概要のみの説明になっていますので，具体的に使用した手法など，厳密な内容については元論文をご覧いただければと思います．

## 実験用環境
### Platform
![platform_domain.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/aaf0d769-e311-4298-66b9-842e6aab92ec.png)
https://github.com/cycraig/gym-platform

Agentが落とし穴や敵を回避しながら横断することを目的とした環境です．

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| 走る(run) | x軸方向の移動距離 | 
| ハイジャンプ(hop) | x軸方向の移動距離 | 
| ロングジャンプ(leap) | x軸方向の移動距離 | 


### Robot Soccer Goal
![goal_domain.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/e2845f3e-2908-d1f2-a865-4f95667b882d.png)
https://github.com/cycraig/gym-goal

キーバーをかわしてゴールを決めることを目的としたサッカー環境です．

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| ボールを蹴る(kick-to) | 目標地点のx座標, 目標地点のy座標 | 
| ゴールの左にシュート(shoot-goal-left) | 目標地点のy座標 | 
| ゴールの右にシュート(shoot-goal-right) | 目標地点のy座標 | 


### Half Field Offense
![hfo3on3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/6b993b5c-2ebb-7be6-c38d-021c37118a58.png)
https://github.com/cycraig/gym-soccer

複数対複数でのサッカー環境です．連携して相手のディフェンスを突破し，ゴールを決めるのが目的です．

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| 走る(dash)| 走る速度(power), 角度（degrees) | 
| ターン(turn) | 角度（degrees)  | 
| ボールを蹴る(kick)  | 蹴る強さ(power), 角度（degrees) | 


## MOBAゲーム

https://openreview.net/forum?id=Sy_MK3lAZ

MOBA(Multiplayer Online Battle Arena)ゲームへ適用されています．元論文ではKing of Gloryというゲームへの適用を行なっていますが，私が未プレイなため，代わりにプレイ経験があり，日本で広く知られているMOBAゲームである[League of Legends](https://www.leagueoflegends.com/ja-jp/)を例にご説明します．

<iframe width="560" height="315" src="https://www.youtube.com/embed/NDQArNLambI" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

上記の公式紹介動画を見ていただくと様々な要素があるゲームだとお分かりいただけるかと思います．余談ですが，プレイ人口は一億人を超えており，世界大会[^世界大会]なども行われています．個人のスキルに大きく左右されるゲーム性と言えるでしょう．ちなみに私はケイトリンというキャラを使っています．


https://www.leagueoflegends.com/ja-jp/champions/caitlyn/

このキャラの行動をParameterized Action Spaceとして扱った場合どうなるかを考えてみます．大前提として，どの行動をするのかを決めなくてはなりません(移動, 通常攻撃, スキル1~3, 必殺技)．それに加えて，それぞれの行動にはパラメータが必要になります．
このゲームではマウスでクリックした場所にキャラクターが移動する方式になっているので，移動先のx座標, y座標が必要です．また，スキル2(地雷設置)もクリックした場所に地雷を設置する方式のため，同様に座標が必要になります．スキル1(溜め攻撃)，スキル3(足止め攻撃)では座標は必要ありませんが，どの方向に打ち出すか(角度)を決める必要があります． 通常攻撃と必殺技は敵をクリックすることで行いますが，今回は説明の都合上最も近い敵を攻撃するものとします[^離散的なパラメータ]．まとめると以下の通りです．

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| 移動| x座標, y座標 | 
| 通常攻撃 | -  | 
| スキル1(溜め攻撃)  | 角度 | 
| スキル2(地雷設置)  | x座標, y座標 | 
| スキル3(足止め攻撃)  | 角度 | 
| 必殺技  | - | 

これ以外にも共通スキルや商品購入，アイテム使用など，様々な要素がありますが，元論文の行動定義に則り，このレベルに留めます．
元論文以前の研究ではDDPGを用いて全てを連続行動として扱い, argmaxによって行動選択部分を離散化するという形を取っていましたが，P-DQNを用いることでより高速に学習し，かつロバストな方策を得られることが示されています．
![difference_of_pdqn_ddpg.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/0252fc6b-f97b-827e-6190-e10a3c7c2c2a.jpeg)
引用元: https://openreview.net/forum?id=Sy_MK3lAZ

<font color="Red">＊League of Legendsでの例は思考実験であり，実際にAgentを作成したわけではありません．botの使用は利用規約で禁じられています．</font>

## 価格交渉対話
https://ieeexplore.ieee.org/document/9643383

論文誌ver

https://pubmed.ncbi.nlm.nih.gov/35801451/

価格交渉対話は一つのアイテムに対し，2つのAgent(買い手，売り手)が自然言語で値段交渉を行うという問題設定です．それぞれのAgentはそのアイテムの画像，名前や説明文，自らの目標合意価格を与えられた上で，より自分の利益になるような合意を目指すことになります． なお，モジュールベース[^モジュールベース]のシステム構造を取るのが主流であり，自然文は対話行為という形で抽象化されます(例: "greet", "propose").
![example_negotiation.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/244999df-18d9-cad7-e254-6633e0b14a40.jpeg)
引用元: https://aclanthology.org/D18-1256/

それまでの[先行研究](https://aclanthology.org/D18-1256/)では提案する価格をあらかじめ定義した値集合から選ぶ形で行なっていましたが，Parameterized Action Spaceを用いることで価格の定義が必要なくなりました．また，(私の経験上)学習が既存手法よりも容易になっています[^言語と交渉の混合]．

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| 挨拶(greet)  | - | 
| 質問(inquire) | - | 
| ...  | ... | 
| 価格提案(propose)| 提案価格| 
| 反論(counter) | 提案価格  | 





## エネルギースケジューリング

https://ieeexplore.ieee.org/abstract/document/8885255

論文誌ver

https://ieeexplore.ieee.org/document/9801653

データセンターでのエネルギースケジューリングにも適用されています．データセンターでは高速にタスクを処理することが求められますが，連続で処理を続けると熱を持つため冷却しなくてはなりません．この時，空冷システムのファンは回転数をあげた分だけ電気代がかかるため，運営費の増加につながります．データセンターとしては各サーバーにうまくタスクを割り振り，最低限の冷却コストで最高の処理能力を得られれば最も利益をあげられることになります．
つまり，登場人物はタスクスケジューラーと冷却システムです．タスクスケジューラーは各サーバーのCPUコア数，使用率，消費電力，温度などの状態を参照し，手隙のサーバーにタスクを割り振ります．それに対し，冷却システムはタスク処理の際に生じるラックサーバの熱をファンの回転数を上げることで冷却します．Agentはタスクスケジューラーと冷却システムを操作し，オーバーヒートを避け、負荷バランスを保ちながら、Power Usage Effectiveness(PUE）[^PUE]を最小化することを目指します．
![Data_Center_Energy_Efficiency_Using.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/4c311b2e-ebef-d3a5-1790-8bca2f38eb55.jpeg)
引用元: https://ieeexplore.ieee.org/abstract/document/8885255



| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| サーバーAにタスクを渡す | ファンの風量 | 
| サーバーBにタスクを渡す | ファンの風量 | 
| サーバーCにタスクを渡す | ファンの風量 | 
| ... | ... | 

実在するデータセンターであるNational Supercomputing Centre (NSCC) Singapore の構成を模したシュミレーション環境において，既存手法であるサイロ化と比較して15%, ジョイント最適化と比較して10%のエネルギー消費を削減できたとのことです．

## 多層薄膜(ハードウェア素材)設計

https://iopscience.iop.org/article/10.1088/1361-6463/abfddb

ハードウェア素材の設計に適用されています．紹介する論文では多層薄膜という，複数の素材を積み上げることで特定の波長の光を透過させたり，反射させる(分光)ことを目的とした素材の設計について取り組んでいました．多層薄膜ではどの素材を，どれくらいの厚みで積むかによって性能が変化します．

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| 素材1を載せる | 厚み | 
| 素材2を載せる | 厚み | 
| ... | ... |
| 素材Nを載せる | 厚み | 


多層薄膜は層数が少ないほど製造が容易かつ低コストになる他，吸収損失[^吸収損失]が削減されるため望ましいとされています．Agentは最大の層数，厚みという制約の上で，目標の反射率曲線に近づけるように学習します．その際，層数や厚みが大きければペナルティを与えるような正則化を加えることでシンプルな設計になることが推奨されます．実験の結果,仕様を満たしつつ，人間の専門家がツールで設計した場合よりも少ない層数，厚みの素材を作成できたことが報告されました．

![optical_system.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/a1b8f163-0ae3-ee7d-dbb4-885b59a108a8.jpeg)
引用元: https://iopscience.iop.org/article/10.1088/1361-6463/abfddb/pdf

## 信号機制御

https://www.mdpi.com/1424-8220/21/7/2302

近年の強化学習を用いて交通整理をするという研究の流れを受けて，信号機制御をParameterized Action Spaceで表現することが提案されています．Agentは信号パターン(例: 青青青青赤赤赤青青青青青赤赤赤)と，その継続時間を調整することによって，信号待ちをする車両を減らすことを目的とします．

![traffic.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/0858c9f2-01e8-0256-92bc-af9a45a8190a.jpeg)
引用元: https://www.mdpi.com/1424-8220/21/7/2302


| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| 信号パターン1 | 継続時間 | 
| 信号パターン2 | 継続時間 | 
| ... | ... |
| 信号パターンN | 継続時間 | 


シュミレーションを用いた実験を行い，離散行動空間，連続行動空間を用いた場合と比べ，平均待ち行列長を22.20%、平均所要時間[^ATT]を5.78%削減できることを示しました．

## 仮想ネットワーク管理

https://arxiv.org/abs/1910.10695

論文誌ver

https://ieeexplore.ieee.org/document/8932565

ネットワークの仮想化(NFV)にも応用されています．NFVはルーターやスイッチといったネットワーク機器をサーバー上の仮想マシン（VNF）として構築し,それらをオーケストラレーションすることで柔軟なリソースの増減を実現する方式のことです([参考にしたサイト](https://www.infraexpert.com/study/sdn07.html))．新しいユーザーの接続に対し，オーケストラレーションを管理するNFV-MANO(Agent)は既存のVNFインスタンスのリソースを増加させる(垂直スケーリング)か，新しいインスタンスを作成する(水平スケーリング)か，クラウドにオフロードするかを選択して対応する必要があります．評価はレイテンシや運用コスト，サービス品質[^SLA]という観点で行われます．本論文では仮想化技術にコンテナ仮想化を用いているため，Kubernetesがやっているスケーリングの無駄を削減する方法を学習するというイメージが近いかもしれません．

![NFV.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/16f36f59-40dc-44a9-d761-4982d243034c.jpeg)
引用元: https://arxiv.org/abs/1910.10695

| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| サーバー1に割り当てて既存インスタンスを垂直スケーリング | CPU割り当て増減, メモリ割り当て増減 | 
| ... | ... |
| サーバーNに割り当てて既存インスタンスを垂直スケーリング | CPU割り当て増減, メモリ割り当て増減 | 
| サーバー1に新しいインスタンスを作成して割り当て(水平スケーリング) | CPU割り当て量, メモリ割り当て量 | 
| ... | ... |
| サーバーNに新しいインスタンスを作成して割り当て(水平スケーリング) | CPU割り当て量, メモリ割り当て量 | 
| クラウドにオフロード | - |

今回は仮想ネットワークでしたが，サービスを運用するサーバー群のオートスケーリングにも適用できる手法であるので，応用の幅が広いと感じています．

## 検索システム

https://dl.acm.org/doi/10.1145/3442381.3449862

検索システムはクエリの前処理=>候補の収集(マッチング)=>リランキングという流れでWeb上に存在する膨大な文書からユーザーが入力したクエリに適した文書を提示します．マッチング部分では短い応答時間で高品質な候補文書群を作成することが求められ，現在のキーワードベースマッチングでは転置インデックス[^転置インデックス] から複数のルール(マッチルール)で絞り込むことで候補群を作成する方法が頻繁に用いられます．

![search_engine.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748962/54c99125-08c6-ef90-e61b-5e15fb0e5f1e.jpeg)
引用元: https://dl.acm.org/doi/10.1145/3442381.3449862

マッチルールのハイパラメータ(例. "特定のマッチルールから何候補")はエンジニアがヒューリスティックに設定することで候補文書群の品質とレイテンシのトレードオフを調整してきました.しかし，マッチルールの種類やそれに伴うハイパラメータが増加していけばいくほど人手での調整は困難な上．Web上の文書は時間によって変化したり，新たに追加される点から定期的に再設計しなくてはなりません.また，マッチルールは静的なため，途中の状態に基づいて動的にルールを修正することはできず，出現頻度の低い検索パターンへの適応性が低いです．この研究ではマッチングの部分にParameterized Action Space を用いた強化学習を導入することで上記の改善を試みました．


| 離散行動 | パラメータ(連続行動) |
| --- | --- |
| マッチルール1 | 候補から上位何件採用するか | 
| マッチルール2 | 候補から上位何件採用するか | 
| ... | ... |
| マッチルールN | 候補から上位何件採用するか | 
| 検索終了(stop) | - | 

Microsoft社が提供するBing検索から収集したクエリデータセットを用いて学習し、Bing検索の実環境で評価されました．実際の検索タスクでヒューリスティックな手法と比較した結果，提案手法(Parameterized Action Soft Actor-Critic と  Prioritized Experience Replayの改良)が文書の品質をほぼ維持したままインデックスブロックへのアクセスを70%以上削減し、応答時間[^検索の応答時間]を9%削減することができたことが報告されています．


## その他(オープンアクセスでない)

・戦闘機の空戦戦術学習

https://www.sciencedirect.com/science/article/abs/pii/S0952197620303547

・ネットワーク化制御システム設計

https://ken.ieice.org/ken/paper/2020031011vf/


# 終わりに
本記事では離散行動と連続行動をどちらも扱うことが可能な行動空間であるParameterized Action Spaceの概要や提案されている手法，適用事例についてご紹介しました．
誤りを見つけた際はコメントやTwitterのDMで教えていただけますと幸いです．

引用した全てに感謝します．また，機械学習未履修者として壁打ちに付き合ってくれた友人の[@yuni-hutsuka](https://github.com/yuni-hutsuka)に感謝します．
この記事の公開にあたり，DeNA23卒同期の@it_tsumugiさんと社員の[@silvers](https://twitter.com/silver_s)さんにレビューいただきました．ありがとうございました！
なお，この記事に関する全ての責任は@xavifrogにあります．


ここまでお付き合いいただきありがとうございました！
明日以降もアドベントカレンダーは続くので，ぜひチェックしてください！

https://qiita.com/advent-calendar/2022/dena-23-shinsotsu

[^ここで育ちました]: 強化学習専門の研究室出身ではないので半分独学なのですが，その際のとっかかりとして非常に参考にさせていただきました．ここで育ったといっても過言ではないです．
[^割引率]: 無限に行動が続く場合，割引率が1以上だと収益が増え続けることになるため行動価値が発散してしまいます.そのため，割引率は0.99が初期値としてよく用いられます．なお，割引率が小さい場合は短期的な収益，大きい場合は長期的な収益を考慮するように学習されます．
[^世界大会]: 2022年度賞金総額が$2,225,000 USDだそうです．
[^離散的なパラメータ]: Hybrid Actor-Ciritcであれば離散的なパラメータも用意できるため，誰に攻撃するかまでをモデル化することも可能です．
[^モジュールベース]: Parser(自然文=>対話行為), Manager(対話行為=>次の対話行為), Generator(対話行為=>自然文)の3モジュール.
[^言語と交渉の混合]: 先行研究ではそれまでの対話行為や提案価格の系列を入力とし，[対話行為, 提案価格(離散値), 文末タグ(EOS)]の系列を出力するseq2seq形式でManagerをモデル化していました．十分なデータがないseq2seqの学習は難しい問題であり，更にREINFORCEによる追加学習も行なっていたために学習の調整が困難でした．
[^PUE]: PUE = データセンター全体の消費電力量（kWh）/IT機器の消費電力量（kWh）.PUEの値が小さいほどデーターセンターの効率が良いとされています．
[^吸収損失]: 光が素材に吸収され，熱に変換されることによって生じる損失
[^ATT]: 全車両の総移動時間/車両台数
[^SLA]: 利用者との間で結ばれるサービスの品質保証(service level agreement; SLA)を満たす必要があります.
[^転置インデックス]: 文書内に存在する単語をkey, 文書自体をvalueとした索引構造．入力されたキーワードに対して素早く候補文書群を提示します．
[^検索の応答時間]: モデルの推論時間込み

[^状態価値]: DQNやDDPGで推定していた行動価値と異なり，状態を元に将来的に得られる報酬を見積もる方法です．サッカーで例えると，行動価値は"今シュートを打ったら価値になるか"で，状態価値は"今の状態(自分，味方，敵の位置など)が自分に有利か"になります．
[^オフライン強化学習]: 環境とのインタラクションなしで方策を学習するオフライン強化学習や，エキスパートデータの方策を模倣することで報酬設計を伴わずに方策を学習する模倣学習といった方法も存在します．
[^行動空間]: Agentが取ることができる全ての行動の集合のこと．将棋を例に考えると，歩の行動空間は{"上に１マス移動"}, 王の行動空間は{"右上に１マス移動", "右に１マス移動", "右下に１マス移動", "下に１マス移動", "左下に１マス移動", "左に１マス移動", "左上に１マス移動", "上に１マス移動"}となります．
[^one-hot　ベクトルによるマスク]: one-hotベクトルによるマスクによって実現します．
[^階層構造を持つ行動空間]: 商品をピッキングする人型ロボットの例で考えます．ロボットは倉庫から特定の商品を取り出し，複数あるトラックの内の一つに運び込む必要があります．その時の評価は所要時間とアイテムの傷で判断するとします．
まず最初にAgentは複数ある棚の内のどこからピッキングするのか(離散行動)を決定する必要があります．続いて，複数ある経路のどれを使うか(離散行動)を決定します．それが決まったら体のどの部位をどう動かすか(連続行動)を決めることになるでしょう．更には商品が天地無用などの配送オプションがある場合は運び方(離散行動)を選ぶ必要があるかもしれません．このように，複雑で大きな問題を小さな部分問題の集合に置き換え，各部分問題のそれぞれに方策を用意し，それぞれを強化学習で最適化する方法を階層強化学習と言います．階層構造を持つ行動空間とは階層強化学習を考える際の行動空間です．

[^誤差逆伝播しない]: Criticのモデルまで誤差逆伝播しないということです．

[^advantage]: 時間tでのAdvantage = 時間tの行動により得られた報酬 + 時間t+1の状態価値×割引率 - 時間tの状態価値

[^連続行動の求め方]: 連続行動で確率的方策を用いる場合，モデルは確率分布のパラメータ(正規分布では平均, 標準偏差[２乗して分散にする])を出力とする(reparameterization trick).