Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
[GunosyDM研究会]これからの強化学習 2.2, 2.3 / future-RL-2-2...
Search
ysekky
May 12, 2017
Research
0
3.4k
[GunosyDM研究会]これからの強化学習 2.2, 2.3 / future-RL-2-2-2-3
ysekky
May 12, 2017
Tweet
Share
More Decks by ysekky
See All by ysekky
スタートアップの開発サイクルに学ぶ 研究活動の進め方 / research practices inspired by startup business strategy
ysekky
0
1.9k
[論文紹介] A Method to Anonymize Business Metrics to Publishing Implicit Feedback Datasets (Recsys2020) / recsys20-reading-gunosy-datapub
ysekky
3
2.5k
JSAI2020 OS-12 広告とAI オープニング / JSAI2020-OS-12-ads-and-ai-opening
ysekky
0
1.9k
JSAI2020インダストリアルセッション - Gunosyにおける研究開発 / jsai2020-gunosy-rd-examples
ysekky
1
730
ウェブサービス事業者における研究開発インターン[株式会社Gunosy] - テキストアナリティクスシンポジウム2019 / research-intern-case-study-at-gunosy
ysekky
0
2.6k
Gunosyにおけるニュース記事推薦/ news-recommendation-in-gunosy-webdbf2019
ysekky
1
1.4k
DEIM2019技術報告セッション - Gunosyの研究開発 / deim-2019-sponsor-session-gunosy-research
ysekky
0
970
Analysis of Bias in Gathering Information Between User Attributes in News Application (ABCCS 2018)
ysekky
1
2.2k
世代による政治ニュース記事の閲覧傾向の違いの分析 - JSAI2018 / Analysis of differences in viewing behavior of politics news by age
ysekky
0
3.8k
Other Decks in Research
See All in Research
The Fellowship of Trust in AI
tomzimmermann
0
130
工学としてのSRE再訪 / Revisiting SRE as Engineering
yuukit
19
11k
テキストマイニングことはじめー基本的な考え方からメディアディスコース研究への応用まで
langstat
1
110
機械学習でヒトの行動を変える
hiromu1996
1
200
Weekly AI Agents News! 9月号 プロダクト/ニュースのアーカイブ
masatoto
1
110
[依頼講演] 適応的実験計画法に基づく効率的無線システム設計
k_sato
0
100
さんかくのテスト.pdf
sankaku0724
0
270
クラウドソーシングによる学習データ作成と品質管理(セキュリティキャンプ2024全国大会D2講義資料)
takumi1001
0
250
Matching 2D Images in 3D: Metric Relative Pose from Metric Correspondences
sgk
1
300
いしかわ暮らしセミナー~移住にまつわるお金の話~
matyuda
0
140
CVPR2024論文紹介:Segmentation
hinako0123
0
140
研究の進め方 ランダムネスとの付き合い方について
joisino
PRO
54
19k
Featured
See All Featured
Become a Pro
speakerdeck
PRO
24
5k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
41
2.1k
Measuring & Analyzing Core Web Vitals
bluesmoon
1
40
Stop Working from a Prison Cell
hatefulcrawdad
267
20k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
32
1.8k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
167
49k
Visualization
eitanlees
144
15k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
26
2.1k
Building Your Own Lightsaber
phodgson
102
6.1k
How To Stay Up To Date on Web Technology
chriscoyier
788
250k
Practical Orchestrator
shlominoach
186
10k
Side Projects
sachag
452
42k
Transcript
これからの強化学習 2章 強化学習の発展的理論 2.2, 2.3 Yoshifumi Seki@Gunosy Inc Gunosyデータマイニング研究会 #120
2017.05.10
2.2 強化学習アルゴリズムの理論的解析と ベイズ統計による強化学習のモデル化 • 探索と利用のトレードオフをどのように評価するか? • リグレット: 最悪性能を理論的に解析する • ベイズ事前分布の形式で環境の事前知識が得られれば、トレードオフが扱える
2.2.1 多腕バンディッド問題 • 探索と利用のトレードオフが生じる最も単純な問題 • 報酬和の最大化だけでなく、リグレットが学習性能の評価指標として用いられてい る ◦ 最適解を最初から実行していた時と比較して、どれだけ損失があったか •
ε-greedy • 一定確率εで、ランダムな選択をする ◦ それ以外はこれまでで一番期待値が高い選択をする • リグレットの上界はTに対してO(T)になる • εを1/tに対して適応的に減衰させると、長期的にはO(logT)になる
UCBアルゴリズム • 上式が最大になる選択をする ◦ n_iはiをえらんだ回数 ◦ 期待値の信頼区間の幅の半分を表している • 不確かなときは楽観的に •
リグレット上界はO(logT) ◦ 適応的ε-greedyに対して係数が非常に小さい
Thompsonサンプリング • 報酬がベルヌーイ分布に従う場合のベイズ推論アルゴリズム ◦ 事前分布として一様分布をおく ◦ 各腕からサンプリング ◦ 最大の腕を選択 ◦
各腕のパラメータを更新 • リグレットがUCB1と同様 • 問題によっては、UCB1よりも良い性能を出す
2.2.2 強化学習における探索コスト最小化 • より一般的な強化学習の問題として、MDP上でのトレードオフを考える • 探索コストの最小化に関する研究を紹介 ◦ 価値関数が[0, 1]に収まる場合を考える
楽観的初期値法 • 各状態の行動価値の初期値を高めに設定しておく ◦ 理論的上限か、それ以上 • 探索が不十分な領域に探索が行われる ◦ 探索が進むと正確な価値へ収束していく •
最適解の学習に失敗する可能性をゼロにできない ◦ 改良の試みもあるが、理論的な上界を与えるには至っていない
サンプル複雑性: モデルベース手法 • 真に最適な方策よりε以上劣るような法則を取ることを間違いと考える • その間違いの回数をサンプル複雑性と呼ぶ • PAC-MDP ◦ サンプル複雑性が確率
1−δで抑えられること
PAC-MDPであるアルゴリズム: Rmax • m回経験するまでは、楽観的な価値が与えられる • m回経験した(s, a)ペアは、遷移確率、報酬関数を推定して、最適な行動を選択す る • mを非常に大きくしなければならないので、実用とするには無理がある
モデルベース区間推定 • 各状態-行動ペアに対する報酬と遷移確率に関する信頼区間を求め、その信頼区 間の中で最大の勝ちとなるような行動を解く ◦ 価値反復法の単純な拡張で解くことができる • 証明されているサンプル複雑性はRmaxとほぼ変わらないが、実際にはかなりの違 いがある
サンプル複雑性: モデルフリー法 • モデルを保持した上で、近似したMDPを複数解とかなくてはならず、非効率 • Delayed Q-Learning ◦ m回の経験が集まるまでは更新しない ◦
m回分のデータをつかって、行動価値観数を更新する
リグレット上界 • サンプル複雑性は、学習までにかかる時間の上限を与えるが、報酬和にどの程度 影響するかについては、直接見積もれない • UCRL2 ◦ モデルベースで信頼区間を推定し、最も楽観的なものを選択する ◦ 信頼区間の幅をUCB1と同様にTに応じて広げていく
◦ O(D|S|sqrt(|A|T))の上界になる ▪ DはMDPの半径 ▪ MDPで最も遠い2状態間の距離
2.2.3 ベイズ主義的アプローチ • 問題が完全に未知であるという仮定は現実的ではない ◦ 通った道は戻れるし、 T字路など似た構造がなんども登場層 • ベイズ主義的アプローチ:「不確かさ」を確率論のモデルを利用して取り扱う •
環境がk次元のパラメータベクトルに寄って決まるMDP P_θとして記述される ◦ ありうる環境の集合の中でどれがありそうかを確率分布で記述したものをベイズ環境モデルと呼ぶ ◦ ベイズ環境モデルで表された環境に対する強化学習をベイジアン強化学習と呼ぶ
2.3 逆強化学習 2.3.1 報酬設計問題 • 報酬を定義することを報酬設計問題と呼ぶ ◦ 目標状態や終端状態にだけ定義された報酬によって学習することは難しい ◦ 行動系列が一部しか観測できないときに、どの行動が報酬書くときに寄与シたのかわからない
• 逆強化学習 => 最適な行動系列や、環境モデルを所与として、報酬関数を求める 問題
2.3.2 Ngの逆強化学習法: 有限状態空間を対象 • 以上の線形計画問題を解く • λを大きくするほど、単純な報酬関数が得られる
2.3.3 Abbeelの逆強化学習法 • エキスパート: 各状態で最適な行動をとるエージェント ◦ エキスパートと同じような行動軌跡が得られる報酬関数 Rを推定する