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
980
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
論文読み会 SNLP2024 Instruction-tuned Language Models are Better Knowledge Learners. In: ACL 2024
s_mizuki_nlp
1
350
LiDARとカメラのセンサーフュージョンによる点群からのノイズ除去
kentaitakura
0
130
授業評価アンケートのテキストマイニング
langstat
1
360
Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solve
eumesy
PRO
7
1.2k
3次元点群の分類における評価指標について
kentaitakura
0
420
ミニ四駆AI用制御装置の事例紹介
aks3g
0
160
工学としてのSRE再訪 / Revisiting SRE as Engineering
yuukit
19
11k
非ガウス性と非線形性に基づく統計的因果探索
sshimizu2006
0
360
Global Evidence Summit (GES) 参加報告
daimoriwaki
0
150
20240918 交通くまもとーく 未来の鉄道網編(こねくま)
trafficbrain
0
230
Weekly AI Agents News! 10月号 論文のアーカイブ
masatoto
1
250
システムから変える 自分と世界を変えるシステムチェンジの方法論 / Systems Change Approaches
dmattsun
3
860
Featured
See All Featured
Code Review Best Practice
trishagee
64
17k
GraphQLとの向き合い方2022年版
quramy
43
13k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
4
370
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
226
22k
Practical Orchestrator
shlominoach
186
10k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
280
13k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
191
16k
Large-scale JavaScript Application Architecture
addyosmani
510
110k
The Language of Interfaces
destraynor
154
24k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
126
18k
The MySQL Ecosystem @ GitHub 2015
samlambert
250
12k
The World Runs on Bad Software
bkeepers
PRO
65
11k
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を推定する