高次元空間を扱うRL, IRLサーベイメモ (not deep)

# はじめに
高次元の状態空間を扱う強化学習，逆強化学習手法を簡単にまとめました．

# 印象
連続状態空間をそのまま扱うものは少なく，「如何に高次元な離散状態空間を効率的に計算するか」を扱った論文が多かった．
→連続な状態空間，行動空間を扱うIRL手法はdeepなものが多い．[Levine先生資料](http://rail.eecs.berkeley.edu/deeprlcourse-fa17/f17docs/lecture_12_irl.pdf)

連続空間をそのまま扱うIRLは，

- 連続状態空間&連続行動空間
    - Continuous Inverse Optimal Control with Locally Optimal Examples [Levine and Koltun, ICML2012]
- 連続状態空間&連続時間
    - Inverse reinforcement learning in continuous time and space [Kamalapurkar, 2018]

連続空間をそのまま扱うRLは，

- 連続状態空間
    - Value Function Approximation in Reinforcement Learning Using the Fourier Basis [Konidaris+, AAAI2011]
    - Efficient high-dimensional maximum entropy modeling via symmetric partition functions [Vernaza and Bagnell, NIPS2012]
- 連続状態空間&連続行動空間
    - An Expectation Maximization Algorithm for Continuous Markov Decision Processes with Arbitrary Reward [Hoffman+, 2009]
    - Reinforcement Learning in Continuous Action Spaces through Sequential Monte Carlo Methods [Lazaric+, NIPS2007]
    - Reinforcement Learning in Continuous State and Action Spaces [Hasselt, 2012]
- 連続状態空間&連続時間空間&恐らく連続行動空間
    - Reinforcement Learning In Continuous Time and Space [Doya, 2000]


くらいで，恐らく他は高次元の離散空間を効率的に解く手法．


# 目次
順番に特に意味は無いです．


## IRL
- Fast Inverse Reinforcement Learning with Interval Consistent Graph for Driving Behavior Prediction [Shimosaka+, AAAI2017], [pdf](http://www.aaai.org/Conferences/AAAI/2017/PreliminaryPapers/11-Shimosaka-14918.pdf)
- First-Person Activity Forecasting with Online Inverse Reinforcement Learning [Rhinehart and Kitani, ICCV2017], [pdf](https://www.ri.cmu.edu/wp-content/uploads/2017/11/Rhinehart_First-Person_Activity_Forecasting_ICCV_2017_paper.pdf)
- Continuous Inverse Optimal Control with Locally Optimal Examples [Levine and Koltun, ICML2012], [pdf](http://graphics.stanford.edu/projects/cioc/cioc.pdf)
- Approximate MaxEnt Inverse Optimal Control and its Application for Mental Simulation of Human Interactions [Huang+, AAAI2015], [pdf](http://www.cs.cmu.edu/~kkitani/pdf/HFKB-AAAI15.pdf)  
    - Action-Reaction:Forecasting the Dynamics of Human Interaction [Huang and Kitani, ECCV 2014], [pdf](http://www.cs.cmu.edu/~kkitani/pdf/HK-ECCV14.pdf)
- Inverse reinforcement learning in continuous time and space [Kamalapurkar, 2018], [pdf](https://arxiv.org/pdf/1801.07663.pdf)


## RL
- Kernelized Value Function Approximation for Reinforcement Learning [Taylor and Parr, ICML2009], [pdf](https://users.cs.duke.edu/~parr/icml09.pdf)
- Value Function Approximation in Reinforcement Learning Using the Fourier Basis [Konidaris+, AAAI2011], [pdf](https://people.cs.umass.edu/~pthomas/papers/Konidaris2011a.pdf)
- An Expectation Maximization Algorithm for Continuous Markov Decision Processes with Arbitrary Reward [Hoffman+, 2009], [pdf](http://proceedings.mlr.press/v5/hoffman09a/hoffman09a.pdf)
- Efficient high-dimensional maximum entropy modeling via symmetric partition functions [Vernaza and Bagnell, NIPS2012], [pdf](https://papers.nips.cc/paper/4817-efficient-high-dimensional-maximum-entropy-modeling-via-symmetric-partition-functions.pdf)
- Reinforcement Learning In Continuous Time and Space [Doya, 2000], [pdf](https://homes.cs.washington.edu/~todorov/courses/amath579/reading/Continuous.pdf)
- Reinforcement Learning in Continuous State and Action Spaces [Hasselt, 2012], [pdf](https://pdfs.semanticscholar.org/0af8/d10c6a4156a9cc892296008b4cb82de4095f.pdf)
- Reinforcement Learning in Continuous Action Spaces through Sequential Monte Carlo Methods [Lazaric+, NIPS2007], [pdf](https://papers.nips.cc/paper/3318-reinforcement-learning-in-continuous-action-spaces-through-sequential-monte-carlo-methods.pdf)



# IRL

## Fast Inverse Reinforcement Learning with Interval Consistent Graph for Driving Behavior Prediction [Shimosaka+, AAAI2017], [pdf](http://www.aaai.org/Conferences/AAAI/2017/PreliminaryPapers/11-Shimosaka-14918.pdf)

ロボットを対象とした[graph-based MaxEnt IRL](https://rse-lab.cs.washington.edu/papers/graph-based-IOC-ijcai-2015.pdf)を一般的な状態空間へ拡張．
画像は[graph-based MaxEnt IRL](https://rse-lab.cs.washington.edu/papers/graph-based-IOC-ijcai-2015.pdf)のもの．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/3af5ebc8-dbae-1cfb-7567-bd62ff0a626a.png)

- グラフを用いた状態空間の離散化．
- 時間間隔の一貫性を保証することで計算コストを抑える．
- Driving behavior prediction on residential roadsでメッシュグリッド状態空間(MG-IRL)，連続状態空間([C-IRL](http://graphics.stanford.edu/projects/cioc/cioc.pdf))，グラフベース([GB-IRL](https://rse-lab.cs.washington.edu/papers/graph-based-IOC-ijcai-2015.pdf))，モンテカルロサンプリング([FQI-IRL](http://www.cs.cmu.edu/~kkitani/pdf/HFKB-AAAI15.pdf))のIRL手法より誤差が少なく，計算コストが抑えられていることを確認．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/ed86b3a8-1239-9f96-d8b0-5ae177947cd8.png)


## First-Person Activity Forecasting with Online Inverse Reinforcement Learning [Rhinehart and Kitani, ICCV2017], [pdf](https://www.ri.cmu.edu/wp-content/uploads/2017/11/Rhinehart_First-Person_Activity_Forecasting_ICCV_2017_paper.pdf)

一人称視点映像からシーン（部屋）や行動を認識，行き先を推定．
連続空間を扱ってはなさそう．

- シーン，行動はdeepの手法で識別．
- DARKOアルゴリズムを提案．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/ee43e8b5-c79a-11c4-493b-4cceda0447f5.png)


## Continuous Inverse Optimal Control with Locally Optimal Examples [Levine and Koltun, ICML2012], [pdf](http://graphics.stanford.edu/projects/cioc/cioc.pdf)

連続状態空間，連続行動空間を扱う．

- 報酬関数のlocalな最適化を用いる（globalに最適なexpertは必要が無くなる？）．
- 報酬関数が線形（よくある$\theta^Tf$の形か），非線形で与えられる場合の二つのバリエーションで提案．
- 分配関数をラプラス近似することでコスト削減．
- Robot arm control, Planar navigation, simulated drivingで有効性を確認．

### Robot arm control
提案手法は'linear'と'nonlinear'．
比較手法よりも小さなロスに収束．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/f6bfb7bf-382e-b7e3-3469-23fba1bb7f14.png)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/e48fdee7-9790-b895-e7cd-54bd68b49602.png)

アームの関節数を増やして実験．
比較手法は関節数を増やすとロスが収束せず，また計算時間が発散．提案手法は収束．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/02235d3d-b691-3bdc-cf1b-e667e70f68a0.png)

### Planar navigation
局所的に最適な16本の軌跡から報酬関数を計算．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/077c1cfb-3bef-9937-3f75-4c78fb521c9d.png)

global, localに最適な軌跡で報酬関数を計算．
比較手法はlocalに最適な軌跡ではうまく収束しない．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/3526a6ef-3ac6-6f40-5472-3266b69bbb03.png)


### simulated driving

積極的，回避する，前の車に付いていく運転を学習．

[動画](http://techtalks.tv/talks/continuous-inverse-optimal-control-with-locally-optimal-examples/57323/)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/be013b3d-48db-3c68-32ea-6386c2c37e61.png)


## Approximate MaxEnt Inverse Optimal Control and its Application for Mental Simulation of Human Interactions [Huang+, AAAI2015], [pdf](http://www.cs.cmu.edu/~kkitani/pdf/HFKB-AAAI15.pdf)

MaxEnt IOCの近似手法を提案，分配関数の計算コストを削減．

- 状態空間と行動空間をquantized．
- approximate dynamic programming
- Monte Carlo sampling
- サンプル数が少ないとうまくいかないか．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/fd624733-9550-a33f-c862-e1c13ba70e56.png)


## Inverse reinforcement learning in continuous time and space [Kamalapurkar, 2018], [pdf](https://arxiv.org/pdf/1801.07663.pdf)


連続状態空間，連続時間空間を扱う．
数式だらけでほとんど理解できなかった．．．

- 線形な動的システムを仮定．
- inverse Bellman errorを最小化するように学習．

# RL

## Kernelized Value Function Approximation for Reinforcement Learning [Taylor and Parr, ICML2009], [pdf](https://users.cs.duke.edu/~parr/icml09.pdf)

様々なkernel-basedな価値関数を統合．

- Kernelized LSTD (KLSTD)
- Gaussian Process Temporal Difference learning (GPTD)
- Gaussian Pro- cesses in Reinforcement Learning (GPRL)
- Bellman error decompositionで正規化項のパラメータチューニング．
- Bellman error decompositionの効果を制御する$\Sigma_p$を変えて実験，$0.1I$にした方がスムースに．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/ed2d44ea-db38-d7a9-a476-fbbe8f600cbe.png)


## Value Function Approximation in Reinforcement Learning Using the Fourier Basis [Konidaris+, AAAI2011], [pdf](https://people.cs.umass.edu/~pthomas/papers/Konidaris2011a.pdf)

連続状態空間を扱う．

- 価値関数の近似にフーリエ級数（Fourier series）．
- 放射基底関数（radial basis functions），多項式基底（polynomial basis）を使用した価値関数の近似よりも良い結果に．

### The Swing-Up Acrobat

Sarsaアルゴリズムで学習．
近似手法は

- The polynomial Basis
- Radial Basis Functions (RBFs)
- Proto-Value Functions (PVFs)
- Fourier Basis

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/5dbdd125-9641-1432-6bcc-26ab7d3d04e0.png)

### The Discontinuous Room

離散状態空間でも比較．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/b1b9d44c-e12c-652b-53dc-d8e60c687eca.png)

### Mountain Car

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/810bf87a-b560-717f-60b4-e075c4b6dc41.png)

## An Expectation Maximization Algorithm for Continuous Markov Decision Processes with Arbitrary Reward [Hoffman+, 2009], [pdf](http://proceedings.mlr.press/v5/hoffman09a/hoffman09a.pdf)

連続状態空間，連続行動空間を扱う．
EMアルゴリズムで最適制御．

- 報酬がガウス分布の線形和でモデル化できる場合に有効か．

## Efficient high-dimensional maximum entropy modeling via symmetric partition functions [Vernaza and Bagnell, NIPS2012], [pdf](https://papers.nips.cc/paper/4817-efficient-high-dimensional-maximum-entropy-modeling-via-symmetric-partition-functions.pdf)

連続状態空間を扱う．
低次元の空間での動的計画法が可能．

- 分配関数が回転（rotations）について対称になることを利用？

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/26e14200-a664-7516-18b3-4d87a80849b0.png)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/5640259d-372d-fed8-eefc-2ac583eb6de0.png)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/0cb9fa87-9db2-f447-f4fe-f8c682b5f669.png)

## Reinforcement Learning In Continuous Time and Space [Doya, 2000], [pdf](https://homes.cs.washington.edu/~todorov/courses/amath579/reading/Continuous.pdf)

連続状態空間，連続時間空間，恐らく連続行動空間を扱う．
Continuous Actor-CriticとValue-Gradient Based Policyを提案．

- HJB equationに基づき，連続な場合に拡張．
- 価値関数を使って，最適な方策を見つける．
- Discrete Actor-CriticよりもContinuous Actor-Criticの方が，少ないステップで方策獲得．
- Continuous Actor-CriticよりもValue-Gradient Based Policyの方が良さそう．

## Reinforcement Learning in Continuous State and Action Spaces [Hasselt, 2012], [pdf](https://pdfs.semanticscholar.org/0af8/d10c6a4156a9cc892296008b4cb82de4095f.pdf)

連続状態空間，連続行動空間に対する強化学習手法の紹介．
Cacla (continuous actor-critic learning-automaton)がメイン．

- 教科書的な解説．
- Value-approximationな方法とPolicy-approximationな方法．
- 連続状態空間かつ連続行動空間を扱うにはPolicy-approximationな方法 (actor-critic)でないと難しい．
    - Cacla (continuous actor-critic learning-automaton)
    - CMA-ES (Covariance matrix adaptation evolution strategies)：gradient freeな手法，Monte Carlo
    - NAC (natural actor-critic)
- double-pole balancing problemで比較．Caclaが最も良い．

## Reinforcement Learning in Continuous Action Spaces through Sequential Monte Carlo Methods [Lazaric+, NIPS2007], [pdf](https://papers.nips.cc/paper/3318-reinforcement-learning-in-continuous-action-spaces-through-sequential-monte-carlo-methods.pdf)

連続状態空間，連続行動空間を扱う．
actor-criticを拡張したSMC(Sequential Monte Carlo)-learningを提案
1. Action Selection
2. Critic Update（行動価値関数を計算）
3. Actor Update
の3段階

- 取りうる行動の集合（この時点で離散な気も）からサンプリング．
- Monte Carlo Methodで行動をサンプリング．
- 行動価値関数の更新にはOn-Policyのもの（SARSA）を使用．
- importance samplingで行動のサンプリング重み．
- 行動のサンプル数も適宜更新．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/d65b8222-3416-5294-8382-65007cc794f6.png)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/6cf4f89a-cfcc-ab9f-f01b-a6968b7f8ba0.png)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/e697a4f2-cc75-e3e9-09ee-87d2b22ec152.png)