- Kaelbling et al. (1996) Reinforcement Learning: A Survey
- 50ページ未満でコンパクトなサーベイ。この本はこのサーベイの現代版を目指している。
- Bertsekas and Tsitsiklis (1996) Neuro-Dynamic Programming
- 理論的な詳細について細かい本。例えば本書では割引報酬和の期待値を指標として最適化をする話しかないが、それ以外の指標についての記述もある。
- Sutton and Berto (1998) Reinforcement Learning: An Introduction
- 界隈で一番有名な本。第二版が執筆中である。
- Bertsekas (2007) Dynamic Programming and Optimal Control, volume 1., 2.
- 動的計画法/最適制御に関する包括的な教科書。強化学習の章もある。
- Bertsekas (2008) Approximate dynamic programming (online chapter)
- 上記のBertsekas (2007)の下巻第6章。本文中ではBertsekas (2010)となっている。
- Govsavi (2003) Simulation-Based Optimization: Parametric Optimization Techniques and Reinforcement Learning
- 平均コスト問題に焦点をあてている本。平均コスト問題についてはこちらにもまとめた。
- Cao (2007) Stochastic Learning and Optimization: A Sensitivity-Based Approach
- 方策勾配法に焦点をあてている本。とくに sensitivity-based approach と呼ばれるものを理論の中心としている。方策空間の中で二つの点（二つの方策）に関する性能を比べることが出来るという設定のもとで、それによって良い方策を直接探すアプローチのように見える（例えば良い方策に逐次的に更新して行く方策反復が考えられる）。方策をパラメトライズして滑らかに変えれば方策勾配法になる。
- Powell (2007) Approximate Dynamic Programming: Solving the curses of dimensionality
- オペレーションズ・リサーチの観点から説明している本。
- Chang (2007) Simulation-based Algorithms for Markov Decision Processes
- 適応サンプリングに焦点を当てている本。
- そもそも適応サンプリングがどんなものかはこちらの資料が参考になる: Thompson (2011) Adaptive sampling
- Frank et al. (2008) Reinforcement Learning in the Presence of Rare Events ICML
estimating the failure probability of a large power gridと書いてあるが電力の話はしてない。 [TODO: 提案手法の内容を簡単に説明する] 実データへの応用として、非常に低い確率であるはあるが、経路が遮断されることを考慮に入れた通信ネットワークのプランニングへと応用をしている。
-
Polyak and Juditsky (1992) Acceleration of stochastic approximation by averaging
- いわゆる Polyak Averaging
- ステップ幅の文脈で出てくるが、特にステップ幅の話ではない。過去の更新されたパラメータを記録しておいて平均することで新しいパラメータの推定値とする話。
- こちらのスライドがわかりやすい: https://www.cs.ox.ac.uk/people/nando.defreitas/machinelearning/lecture5.pdf
-
Tadic (2004) On the Almost Sure Rate of Convergence of Linear Stochastic Approximation Algorithms
- Van Roy (2006) Performance loss bounds for approximate value iteration with state aggregation
- 関数近似器を使ったときのTD(0)はTD(1)と比べてサンプル無限大で近似誤差が劣ってしまうが、（状態集約をしたときの）制御性能では劣っていないという文脈で引用されている論文。
- Sutton et al. (2008) Dyna-Style Planning with Linear Function Approximation and Prioritized Sweeping
- Parr et al al. (2008) An Analysis of Linear Models, Linear Value-Function Approximation, and Feature Selection for Reinforcement Learning
- Bertsekas et al. (2004) Improved Temporal Difference Methods with Linear Function Approximation
- λ-LSPEとLSTD(λ)の比較の文脈で引用される。9.5節ではLSTDによって推定されるパラメータが真値へ収束するより速く，LSPEによって推定されるパラメータがLSTDによって推定されるパラメータへと収束する旨が主張されており、LSPEがLSTDに比類する根拠とされている。
- Lin (1992) Self-Improving Reactive Agents Based On Reinforcement Learning, Planning and Teaching
- 経験再生を提案している論文
- Gyorfi et al. A Distribution-Free Theory of Nonparametric Regression 2002 - p.192のTheorem11.3を強化学習の文脈に直してそのまま登場させている．
- Munos&Szpezari 2008 Finite-Time Bounds for Fitted Value Iteration - 適合価値反復の有限サンプルにおける性能のバウンドを導いているという文脈で登場
- Antos et al. 2007 Learning Near-Optimal Policies with Bellman-Residual Minimization Based Fitted Policy Iteration and a Single Sample Path COLT2006
- 近似方策反復法の有限サンプルにおける性能のバウンドを導いているという文脈で登場
- Antos et al. 2008 Fitted Q-iteration in continuous action-space MDPs NIPS2008
- 適合actor-criticの有限サンプルにおける性能のバウンドを導いているという文脈で登場
This algorithm, which we could also call a fitted actor-critic algorithm
- Audibert et al. (2009) Exploration-exploitation trade-off using variance estimates in multi-armed bandits
- UCBにおける定数Rの代わりに、推定した分散を使うアルゴリズムの分析をした話。 [TODO: Resultsについてひと言書く]
- Ortner (2008) Online regret bounds for Markov decision processes with deterministic transitions
- Kearns and Singht (2002) Near-Optimal Reinforcement Learning in Polynomial Time, Machine Learning.
- E3アルゴリズムを提案。行動空間・状態空間のサイズ、及び時間T (mixing time or horizon time) の多項式オーダーの行動数と計算時間で探索が終わるアルゴリズム、という理解。
- Brafman and Tennenholtz (2002) R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning, JMLR
- R-MAXアルゴリズムを提案。E3アルゴリズムが洗練されている。
- Auer et al. (2010) Near-optimal Regret Bounds for Reinforcement Learning JMLR
- UCRL2アルゴリズムの提案
- Bartlett and Tewari (2009) REGAL: A Regularization based Algorithm for Reinforcement
Learning in Weakly Communicating MDPs UAI
- transient stateをもつMDPに対してのリグレットのバウンドを考えている話（？）
- Brafman and Tennenholtz R-max – A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning JMLR
- Kakade (2003) On the Sample Complexity of
Reinforcement Learning PhD thesis
- （改良版の）R-MAXがPAC-MDPであることを示し、下界も示した。
- Szita and Szepesvari (2010) Model-based reinforcement learning with nearly tight exploration complexity bounds ICML
- MorMax
- Strehl et al. (2006) PAC Model-Free Reinforcement Learning ICML
- 遅延Q学習
- Strehl and Littman (2008) Online Linear Regression and Its Application to
Model-Based Reinforcement Learning NIPS
- 大規模なMDPを解く問題を考えている。
- Bhatnagar et al. (2009) Natural Actor–Critic Algorithms Automatica
- Singh et al. (2000) Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms
- CriticにテーブルSARSA(0)を用いて、GLIEという条件を満たす方策を更新していくと、漸近的に最適方策と一致するという結果を示した論文。
- Chow and Tsitsiklis (1989) The Complexity of Dynamic Programming Journal of Complexity
- オフラインのプランニングの計算量の文脈で引用されている論文。
- Rust (1996) Using Randomization to Break the Curse of Dimensionality Econometrica
- オンラインのプランニングの文脈で引用されている論文。オフラインだと状態次元数に対し指数的に最悪計算量が増えるがオンラインだと違うらしい。
- Szepesvari (2001) Efficient Approximate Planning in Continuous
Space Markovian Decision Problems
- オンラインのプランニングの文脈で引用されている論文。
- Even-Dar et al. 2005 Experts in a Markov Decision Process
online learning in MDPs with arbitrary reward processesの例として引用されている。
- Nu et al. 2009 Markov Decision Processes with Arbitrary Reward Processes
online learning in MDPs with arbitrary reward processesの例として引用されている。
- Neu et al. 2010 The Online Loop-free Stochastic Shortest-Path Problem
online learning in MDPs with arbitrary reward processesの例として引用されている。
- Simao et al. (2008) An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application
- トラックの車両管理 (fleet management) への応用