Loading...
強化学習勉強会 #65
教科書: p.50-p.56 by @fullflu
@fullfulu作成資料:
https://github.com/rl-tokyo/szepesvari-book/issues/6
当日のメモ
1.
This bound improves the bound of Thrun
(1992).
The bound can be shown to be tight in an asymptotic sense.
のtightはここでどういう意味か？
Ortnerの記述↓
Ortner 2008より引用
https://meherchilakalapudi.wordpress.com/category/data-structures-1asymptotic-analysis/
例
2. 報酬関数をepsilon精度で解明する
Hoeffdingの不等式:
https://en.wikipedia.org/wiki/Hoeffding%27s_inequality
3.
?
4.
γ
>
0
.
5
\gamma > 0.5
γ
>
0
.
5
はあってる？逆？
引用されている論文へのリンク
https://github.com/rl-tokyo/szepesvari-book/blob/master/references.md
から引用↓
4.2.3 Active learning in Markov Decision Processes
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アルゴリズムが洗練されている。
4.2.4 Online learning in Markov DecisionProcesses
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に対してのリグレットのバウンドを考えている話（？）
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
http://machinelearning.wustl.edu/mlpapers/paper_files/icml2010_SzitaS10.pdf
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
Please turn on JavaScript to use Paper in all of its awesomeness. ^_^
当日のメモ
1.
2. 報酬関数をepsilon精度で解明する
3.
4.
引用されている論文へのリンク
4.2.3 Active learning in Markov Decision Processes
4.2.4 Online learning in Markov DecisionProcesses