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.5k
[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
2.2k
[論文紹介] A Method to Anonymize Business Metrics to Publishing Implicit Feedback Datasets (Recsys2020) / recsys20-reading-gunosy-datapub
ysekky
3
2.7k
JSAI2020 OS-12 広告とAI オープニング / JSAI2020-OS-12-ads-and-ai-opening
ysekky
0
2.1k
JSAI2020インダストリアルセッション - Gunosyにおける研究開発 / jsai2020-gunosy-rd-examples
ysekky
1
760
ウェブサービス事業者における研究開発インターン[株式会社Gunosy] - テキストアナリティクスシンポジウム2019 / research-intern-case-study-at-gunosy
ysekky
0
2.8k
Gunosyにおけるニュース記事推薦/ news-recommendation-in-gunosy-webdbf2019
ysekky
1
1.5k
DEIM2019技術報告セッション - Gunosyの研究開発 / deim-2019-sponsor-session-gunosy-research
ysekky
0
1.1k
Analysis of Bias in Gathering Information Between User Attributes in News Application (ABCCS 2018)
ysekky
1
2.3k
世代による政治ニュース記事の閲覧傾向の違いの分析 - JSAI2018 / Analysis of differences in viewing behavior of politics news by age
ysekky
0
3.9k
Other Decks in Research
See All in Research
数理最適化に基づく制御
mickey_kubo
5
680
プロシェアリング白書2025_PROSHARING_REPORT_2025
circulation
1
890
「エージェントって何?」から「実際の開発現場で役立つ考え方やベストプラクティス」まで
mickey_kubo
0
120
SSII2025 [TS3] 医工連携における画像情報学研究
ssii
PRO
2
1.2k
ノンパラメトリック分布表現を用いた位置尤度場周辺化によるRTK-GNSSの整数アンビギュイティ推定
aoki_nosse
0
320
集合間Bregmanダイバージェンスと置換不変NNによるその学習
wasyro
0
110
Self-supervised audiovisual representation learning for remote sensing data
satai
3
230
EarthMarker: A Visual Prompting Multimodal Large Language Model for Remote Sensing
satai
3
350
SkySense : A Multi-Modal Remote Sensing Foundation Model Towards Universal Interpretation for Earth Observation Imagery
satai
3
250
データサイエンティストの採用に関するアンケート
datascientistsociety
PRO
0
1k
LLM-as-a-Judge: 文章をLLMで評価する@教育機関DXシンポ
k141303
3
830
90 分で学ぶ P 対 NP 問題
e869120
18
7.6k
Featured
See All Featured
The Straight Up "How To Draw Better" Workshop
denniskardys
234
140k
Being A Developer After 40
akosma
90
590k
Why You Should Never Use an ORM
jnunemaker
PRO
58
9.4k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
30
2.1k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
281
13k
How to Ace a Technical Interview
jacobian
278
23k
Into the Great Unknown - MozCon
thekraken
40
1.9k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
107
19k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
The Cult of Friendly URLs
andyhume
79
6.5k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
2.9k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.8k
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を推定する