ベイズ強化学習

**ベイズ強化学習**（**Bayesian Reinforcement Learning**, **BRL**）とは、強化学習の領域において、ベイズ推定の手法を応用することで、学習プロセスにおける不確実性を明示的に扱い、かつ事前知識を効果的に活用することを目指すアプローチである。多くの伝統的な強化学習手法が環境のモデルや価値関数について一点の推定値を学習するのに対し、BRLではこれらの未知の量に関して確率分布（事後分布）を維持し、観測データに基づいて更新していく。この確率的なアプローチは、強化学習における根本的な課題の一つである探索と利用のジレンマへの対処や、事前情報を学習アルゴリズムへ統合するための、原理に基づいたメカニズムを提供する。

## ベイズバンディット
多腕バンディット問題において、エージェントにとって未知なのは各腕を選択した際の報酬の確率である。ベイズ的アプローチでは、これらの確率を未知のパラメータベクトル（例えば、各腕の平均報酬を表すパラメータなど）によって特徴づけ、このパラメータに対して事前分布を仮定する。そして、エージェントが腕を選択し報酬を観測するたびに、ベイズの定理を用いて事前分布を事後分布へと更新していく。

例えば、各腕の報酬がベルヌーイ分布に従う場合を考える。このとき、各腕の成功確率パラメータの事前分布としてベータ分布を用いると、ベータ分布とベルヌーイ分布の共役性から、観測後の事後分布もまたベータ分布となり、パラメータの更新が容易に行える。

性能評価の際には、パラメータが固定されている場合の「頻度論的リグレット」と、パラメータの事前分布も考慮に入れた「ベイジアンリグレット（ベイズリスク）」が区別される。

### 古典的結果
頻度論的リグレットに関しては、ステップ数 T に対して対数オーダーO(\ln T)を持つ、漸近的にタイトな下界が示されている。一方で、ベイジアンリグレットの下界は、腕の数 K とステップ数 T を用いてO(\sqrt{K T}) と表される。

ギッテンスは、十分統計量が存在する多腕バンディット問題（例えば前述のベータ-ベルヌーイモデル）において、各腕に対して独立に計算できる「ギッテンス指数」という指標を導入した。そして、常にその時点で最も高いギッテンス指数を持つ腕を選択する戦略が、期待割引報酬を最大化するという意味で最適であることを証明した。この文脈で、バンディット過程（腕をプレイし続けるか、あるいはその腕の情報を凍結するかを選択するMDPと見なせる）や、そのようなバンディット過程の集まりである代替バンディット過程群（SFABP）といった概念が用いられる。

### ベイズUCB
**ベイズUCB（Bayes Upper Confidence Bound）**は、UCBアルゴリズムの基本的なアイデアをベイズ的な設定に拡張したものである。このアルゴリズムでは、各腕の期待報酬に関する事後分布を保持する。そして、各ステップにおいて、その事後分布における期待報酬の上側信頼区間が最大となる腕を選択する。これは、「楽観主義」の原則に基づいた探索戦略の一形態と解釈できる。ベルヌーイ腕と一様事前分布という特定の条件下では、ベイズUCBは頻度論的リグレットの下界に整合する性能を達成することが理論的に示されている。

### トンプソンサンプリング
**トンプソンサンプリング（Thompson Sampling, TS）**、または事後サンプリングとも呼ばれる手法は、非常に単純でありながら経験的に高い性能を示すことが知られているベイズ的ヒューリスティックである。アルゴリズムの動作は以下の通りである。

* モデルパラメータ\thetaに関する事後分布P_\text{post}(\theta)を維持
* 各時間ステップt
** 現在の事後分布P_\text{post}(\theta)からパラメータ\hat{\theta}を一つランダムにサンプリング
** サンプリングされた\hat{\theta}の下で最適となる腕a_tを選択し実行
** 選択した腕a_tから得られた報酬r_tを観測し、その情報を用いてP_\text{post}(\theta)をP_\text{post}(\theta|r_t)へと更新

TSは、経験的に優れた性能を示すことが多くの研究で報告されており、理論的な性能保証もいくつか確立されている。また、情報理論的な観点からは、ベイジアンリグレットに関するバウンドも導出されている。TSの大きな魅力の一つは、その単純さにもかかわらず、文脈付きバンディット問題や、腕の間に相関関係が存在するような、より複雑な構造を持つバンディット問題へも自然に拡張可能であるという点である。

## モデルベースベイズ強化学習
モデルベースベイズ強化学習では、MDPのモデルパラメータ、すなわち遷移確率や報酬関数の分布などに関する事後分布を明示的に保持し、この事後分布に基づいて行動選択を行う。このアプローチの起源は、制御理論の分野におけるデュアル制御の初期の研究に見ることができる。

### BAMDP
モデルパラメータに対する不確実性は、信念によって表現される。

特に、状態空間と行動空間が離散的であり、かつ事前分布が共役な場合、しばしば「**ベイズ適応型MDP（Bayes-Adaptive MDP, BAMDP）**」という枠組みが用いられる。

BAMDPにおいては、「**ハイパー状態**」という概念が中心的な役割を果たす。これは、環境の状態sと、遷移モデルに関する現在の事後分布のパラメータ\varphiの組 (s,\varphi)で定義される。報酬が未知の場合には、報酬モデルに関するパラメータもこのハイパー状態に含まれることになる。

エージェントがハイパー状態(s,\varphi)で行動aを選択し、次の状態s'を観測すると、ハイパー状態は次のように遷移する。

* 状態はs'へと遷移
* 事後分布のパラメータは、観測された遷移(s,a,s')の情報を用いて新たな事後分布のパラメータ\varphi'へと更新される。

BAMDPにおける状態遷移確率は、現在の事後分布パラメータ\varphiの下での期待遷移確率と、\varphiが観測に基づいて\varphi'へと決定論的に更新されるという事実を組み合わせたものとして定義される。

このBAMDPは、非常に大きな（しばしば無限の）状態空間を持つMDPとして捉えることができる。その最適価値関数V^*(s,\varphi) は、ベルマン方程式を満たす。

「チェイン問題」は、モデルベースBRLのアルゴリズムの経験的な性能評価を行う際に、頻繁に用いられる代表的なベンチマーク問題の一つである。

BAMDPにおける最適方策\mu^*(s,\varphi) は、「**ベイズ最適方策**」と呼ばれる。この方策は、その定義から、探索（より情報量の多い事後分布をもたらすような行動）と利用（高い即時報酬をもたらすような行動）を本質的にバランスさせる性質を持つ。しかしながら、一般的にベイズ最適方策を厳密に計算することは、計算量の観点から非常に困難である。

### BAMDPにおける近似計画法
ベイズ最適方策の計算が困難であるため、その近似解を求めるための様々な計画アルゴリズムが提案されている。

#### オフライン価値近似
これらの手法は、エージェントが実際に行動を開始する前に、あらかじめ方策を計算しておくアプローチである。

##### 有限状態コントローラ
代表的な手法として、**有限状態コントローラ (FSC:  Finite-State Controllers)** を用いる方法がある。これは、方策をコンパクトなグラフ構造で表現するものである。特定のFSCに対する期待価値は計算可能であり、勾配降下法などの最適化手法を用いて、所定のサイズのFSCの中から最良のものを見つけ出すことを目指す。

##### BEETLE
**BEETLE (Bayesian Exploration Exploitation Tradeoff in LEarning)** は、まずハイパー状態をいくつかサンプリングし、それらに対応する連続状態POMDP（この場合の信念は物理状態 s とモデルパラメータの事後分布 φ の組 (s,φ) で表される）を考える。そして、このPOMDPを、α関数（φ に関する多項式として表現される）を用いた点ベースの手法で解くことにより、近似的な価値関数を得る。

#### オンライン近視眼的価値近似
これらの手法は、計画と実行を1ステップごと、あるいは短い間隔で逐次的に繰り返すオンライン的なアプローチである。

##### ベイズ動的計画法
**ベイズ動的計画法（Bayesian dynamic programming）**は、バンディット問題におけるトンプソンサンプリングの考え方を強化学習へ拡張したものであり、以下のような手順を繰り返す。

* 現在のモデルパラメータの事後分布b(\theta) から、完全なMDPのモデル\hat{M}を一つサンプリング。
* サンプリングされたモデル\hat{M}を（例えば、価値反復法を用いて）解き、その最適行動価値関数Q^*_{\hat M}を求める。
* Q^*_{\hat M}に基づいて行動を選択し実行する。
* 新たに得られた経験に基づいて事後分布b(\theta)を更新する

##### 情報価値 (VOI) ヒューリスティック
このアプローチでは、行動選択の際に、期待報酬に加えて、1ステップ先の限定的な情報価値（VPI）を考慮に入れる。具体的には、各行動 a に対して\mathbb{E}[Q(s,a)] + \text{VPI}(s,a)を計算し、この値が最大となる行動を選択する。

#### オンライン木探索近似
これらの手法は、現在のハイパー状態を探索木のルートノードとし、そこから前方へ向かって探索木を構築することで、各行動の価値を評価する。

##### 前方探索
**前方探索**は、固定された深さ d まで、到達可能な全てのハイパー状態を列挙して探索木を構築する。探索木の葉ノードでは、何らかのデフォルト方策やデフォルト価値関数を用いて価値を評価し、動的計画法的なバックアップ計算によってルートノードにおける各行動の期待リターンを推定する。ただし、この単純な前方探索は、状態空間の大きさが |S| である場合、計算量が O(|S|^d) となり、探索深度 d が大きくなると計算量が爆発的に増加するという問題がある。

##### ベイジアンスパースサンプリング
**ベイジアンスパースサンプリング**は、この計算量増大の問題に対処するため、スパースサンプリングのアイデアをBAMDPへ適用したものである。探索木を構築する際に、全ての行動や次の（ハイパー）状態を考慮するのではなく、事後分布に基づいて確率的に行動と次の（ハイパー）状態をサンプリングする。

##### HMDP
**HMDP**と呼ばれるアプローチでは、探索木の葉ノードの価値評価にQ学習を用い、木の中間ノードでのバックアップ計算には線形計画法を利用する。

##### 分枝限定法
**分枝限定法**は、探索木の各ノードにおいて、そのノードから得られる価値の上界と下界を維持し、明らかに最適解に繋がり得ない枝（ブランチ）を刈り込むことで、探索の効率を向上させる手法である。

##### BOP
**BOP (Bayesian Optimistic Planning)** は、分枝限定法の一種であり、ノードの価値に関する楽観的な上界に基づいて、次に展開するノードを選択する。

##### BAMCP
**BAMCP (Bayes-Adaptive Monte-Carlo Planning)** は、UCT（Upper Confidence bounds for Trees）アルゴリズムをベイズ適応型に拡張したものである。探索木のルートノードでMDPモデルを一つサンプリングし、その探索木の構築フェーズにおいては、そのサンプリングされたモデルを用いてシミュレーション（ロールアウト）を行う。ロールアウトの結果から得られた情報を用いて、探索木上のノードのQ値をモデルフリー的に更新する。

#### PAC保証を達成するための探索ボーナス付き手法
このクラスのアルゴリズムは、「不確実性に直面した楽観主義（Optimism in the Face of Uncertainty）」と呼ばれる原則に基づき、PAC（Probably Approximately Correct）保証やそれに類する理論的な性能保証を提供することを目指す。

##### BFS3
**BFS3 (Bayesian Forward Search Sparse Sampling)** は、ハイパー状態 (s,φ) 上のスパース探索木を構築し、各ノードの価値の上界と下界を用いてロールアウトの方向を決定する。

##### BOSS
**BOSS (Best of Sampled Sets)** は、まず現在の事後分布から K 個のMDPモデルをサンプリングする。次に、これらのモデルを組み合わせた一種の「ハイパーモデル」を構築する。このハイパーモデルにおける行動は、元の行動とサンプリングされたモデルのインデックスの組に対応する。このハイパーモデルを解き、得られた方策に従って行動を選択する。

##### BEB
**BEB (Bayesian Exploration Bonus)** は、報酬関数に探索ボーナス項（例えば、状態行動対 (s,a) の訪問回数 N(s,a) を用いて β / (1 + N(s,a)) のように定義される）を加え、この変更されたMDPを解く。このアプローチは、BAMDPにおけるベイズ最適性を目標とする（PAC-BAMDP）。

##### VBRB
**VBRB (Variance-Based Reward Bonus)** は、探索ボーナスを、モデルパラメータの事後分布の分散に基づいて定義する。これは、真の未知のMDPにおける最適性を目標とする（PAC-MDP）。

##### BOLT
**BOLT (Bayesian Optimistic Local Transitions)** は、探索ボーナスを報酬ではなく遷移確率に加えることで、遷移確率を楽観的に評価するアプローチである。

## モデルフリーベイズ強化学習
モデルフリーベイズ強化学習では、MDPの環境モデルを陽に学習する代わりに、価値関数や方策に関する事後分布を直接的に扱おうとする。

### ガウス過程TD学習（GPTD）
**ガウス過程TD学習（Gaussian Process Temporal Difference, GPTD）**は、価値関数をモデル化するためにガウス過程（GP）を用いるアプローチである。

その核となる考え方は、価値関数V(s)をガウス過程として扱い、観測される即時報酬R(s)を、ベルマン方程式を通じて価値関数 に関連付けられたノイズを含むサンプルと見なすことにある。

具体的には、ある状態 s から得られる割引収益G(s)は、その期待値である価値関数V(s)=\mathbb{E}[G(s)]と、平均ゼロのノイズ項\epsilon(s)の和G(s)=V(s)+\epsilon(s)として分解できる。ベルマン方程式 G(s)=R(a)+\gamma G(s')にこの分解を代入し整理すると、R(s) = V(s) - \gamma V(s')+N(s,s')という関係式が得られる。ここで、N(s,s') = \epsilon(s) -\gamma\epsilon(s')は新たなノイズ項である。

一連の遷移の軌跡が与えられると、上記の関係式は線形統計モデル R_T = HV_{T+1} + N_T、エピソード的な問題設定では R_T = HV_T + N_Tの形に書き直せる。ここで、R_Tは観測された報酬のベクトル、V_Tは対応する状態の価値のベクトル、HはTD構造を反映する行列、N_Tはノイズのベクトルである。

価値関数にGP事前分布を仮定し、各状態でのノイズ\epsilon(s)が独立同分布なガウスノイズであると仮定すると、合成されたノイズ項N_Tもまた、構造化された共分散\Sigma=\sigma^2HH^Tを持つガウス分布に従う。この結果、観測された報酬系列R_Tが与えられたときの価値関数 の事後分布P(V|R_T) もガウス分布となり、その平均と共分散を解析的に計算できる。

MC-GPTDと呼ばれるこの枠組みには、パラメトリック版（価値関数をV(s) = \phi(s)^T W のように基底関数の線形結合で表現し、重みベクトルW の事後分布を推定する）とノンパラメトリック版（価値関数V(s)の事後分布を直接推定する）の両方が存在する。ノンパラメトリックGPTDは、オンラインでのスパース化手法を用いることで、計算効率とメモリ効率を改善できる。

**GPSARSA**は、GPTDを行動価値関数Q(s,a) の学習へと拡張したものである。状態行動空間Z=S \times A  上でGPを定義し、カーネル関数としては、状態に関するカーネルk_S(s,s')  と行動に関するカーネルk_A (a,a')の積カーネル k(z,z') = k_S(s,s')k_A(a,a')などが用いられる。

### ベイジアン方策勾配法 (BPG)
**ベイジアン方策勾配法（Bayesian Policy Gradient, BPG）**は、パラメータ化された方策\pi(a|s; \theta)の性能指標（期待収益）\eta(\theta)の勾配 \nabla \eta(\theta)に関する事後分布を維持し、それに基づいて方策パラメータ\thetaを更新するアプローチである。

方策勾配定理によれば、期待収益の勾配は \nabla \eta(\theta) = \mathbb{E}_\xi[\rho(\xi) \nabla \ln \text{Pr}(\xi;\theta)]と表現できる。BPGでは、この期待値計算に「**ベイズ求積（Bayesian Quadrature, BQ）**」と呼ばれる手法を適用する。BQは、積分 \int f(x)g(x)dxを評価する際に、被積分関数のうち不確実性が高い部分f(x)をGPでモデル化し（g(x)は既知であると仮定）、積分値自体をガウス確率変数と見なして、f(x)のサンプル点からその事後平均と事後分散を計算する手法である。

BPGアルゴリズムでは、方策勾配の式\nabla \eta(\theta) = \mathbb{E}_\xi[\rho(\xi) \nabla \ln \text{Pr}(\xi;\theta)]をBQの形で捉える。この際、被積分関数をGPでモデル化する部分 f(x)と既知と見なす部分 g(x)に分割する方法として、主に二つのモデルが提案されている。

* f(\xi;\theta) = \rho(\xi)\nabla \ln \text{Pr}(\xi;\theta)をベクトル値GPとして扱い、g(\xi;\theta) = \text{Pr}(\xi;\theta)とする。この場合、カーネル関数として二次フィッシャーカーネルが用いられる。

* f(\xi) = \rho(\xi) をスカラー値GPとして扱い、g(\xi;\theta) = \nabla \text{Pr}(\xi;\theta) \text{Pr}(\xi;\theta)とする。この場合、カーネル関数として線形フィッシャーカーネルが用いられる。

ここで、フィッシャーカーネルk(\xi,\xi')は、軌跡\xiのスコア関数 u(\xi;\theta)=\nabla \ln \text{Pr}(\xi;\theta)と、方策\thetaのフィッシャー情報行列 G(\theta)=\mathbb{E}[u(\xi;\theta)u(\xi;\theta)^T]に依存する形で定義される。

方策の改善は、計算された勾配の事後平均の方向に方策パラメータを更新することで行われる。さらに、フィッシャー情報行列G(\theta)を用いた自然勾配の利用や、勾配の事後共分散を不確実性の指標としてステップサイズを適応的に調整することも可能である。

### ベイジアン・アクター・クリティック (BAC)
**ベイジアン・アクター・クリティック（Bayesian Actor-Critic, BAC）**は、アクター・クリティック構造における方策勾配の推定に対して、前述のベイズ求積（BQ）の枠組みを適用するアプローチである。

アクター・クリティック形式の方策勾配は、\nabla \eta(\theta) = \int \int d(s;\theta) \nabla \pi (a|s;\theta)Q(s,a;\theta)dsdaと書ける。ここで、d(s;\theta)は状態sの割引訪問頻度、Q(s,a;\theta)は行動価値関数である。

BACでは、以下の戦略を取る。まず、クリティック、すなわち行動価値関数Q(s,a;\theta)はGPでモデル化され、その事後分布はGPTD（具体的にはGPSARSAと同様の枠組み）を用いて逐次的に更新される。次に、アクターの方策勾配\nabla \eta(\theta)は、被積分関数が f(z;\theta) = Q(z;\theta) と g(z;\theta) = d(s;\theta)\nabla\pi(a|s;\theta)であるような積分と見なされ、BQによって推定される。

行動価値関数Qの事前分布としてフィッシャーカーネルを用いることで、方策勾配\nabla \eta(\theta)の事後モーメントを計算する際に現れる積分が解析的に計算可能となる。この計算において重要な役割を果たすのは、スコア関数とフィッシャー情報行列である。

## リスク考慮型ベイズ強化学習
これまでの議論では、主に期待収益の最大化を目的としてきた。しかし、多くの実応用では、期待収益だけでなく、方策がもたらす結果の「リスク」も考慮することが重要となる。ここでいうリスクとは、収益の分散、特定の損失額を超える確率（Value-at-Risk, VaR）、あるいは期待ショートフォール（Conditional Value-at-Risk, CVaR）といった、期待収益以外の統計量を考慮した性能基準を指す。特にBRLの文脈では、MDPのパラメータに関する不確実性（パラメータ不確実性）に起因するリスクに焦点が当てられることが多い。

固定された方策\piと、遷移確率に関するディリクレ事後分布が与えられた場合に、その方策の価値関数 V^\piの事後的な平均 \mathbb{E}_\text{post}[V^\pi]と事後的な二次モーメント\mathbb{E}_\text{post}[V^\pi(V^\pi)^T]に対する二次近似式が導出されている。これにより、価値関数の推定値の信頼区間などを評価することが可能になる。

### パーセンタイル基準
この基準では、モデルの事後分布からサンプリングされたモデルP'において、方策\piによる期待収益が閾値y以上となる確率が、少なくとも1-\varepsilonであるような、最大のyを見つけること（あるいは、そのようなyを達成する方策\piを見つけること）を目的とする。この問題は一般にNP困難であるが、ディリクレ事前分布の場合には、V^\piの二次近似を用いることで、近似的に最適な方策を求めることができる。

### マックスミン基準
これは、パーセンタイル基準において\varepsilon \to 0とした極限に対応する。すなわち、事後的にあり得る最も悲観的な（最悪の）モデルの下での性能を最大化することを目指す。実際には、事後分布からサンプリングされたモデルやシグマ点法によって生成された代表的なモデルからなる有限集合 \hat{\mathcal{P}}_\text{post}を考え、\max_\pi \min_{P \in \hat{\mathcal{P}}_\text{post}} \mathbb{E}_P[\text{Return}(\pi,P_0,P)]という問題を最小最大動的計画法を用いて解くことで近似される。

### パーセンタイル測度基準
個々のパーセンタイル値に着目するのではなく、パーセンタイル全体の測度\psiを用いてリスクを総合的に評価するアプローチである。例えば、制約条件 P_\text{post}(\mathbb{E}[\text{Return}] \ge y(x)) \ge xを満たすような関数 y(x)のうち、\max \int y(x)d\psiを最大化するような方策と y(x)を求める。特に「k-of-N測度」と呼ばれる測度は注目に値する。これは、N個サンプリングされたモデルのうち、性能が悪い方からk番目のモデルに対する期待収益を評価するものであり、CVaRやマックスミン基準を近似することができる。このk-of-N測度に基づく最適化問題は、対応する二人ゼロサム不完全情報ゲームにおけるミニマックス後悔戦略を計算することで効率的に解くことができると報告されている。

## その他拡張
ベイズ強化学習の基本的な枠組みは、様々な問題設定や目的に応じて拡張されている。

* **PACベイズモデル選択:** このアプローチは、事前分布の選択が不適切であった場合にもロバストな性能保証を与えることを目的とする。事前分布のデータへの整合性を評価することで、完全に経験的な推定値とベイズ的な事後推定値のどちらを採用すべきかのモデル選択を支援する。
* **ベイジアン逆強化学習 (BIRL):** 専門家の行動軌跡データから、その専門家の行動を最もよく説明する報酬関数を学習することを目的とする。報酬関数空間に事前分布を導入し、専門家の方策との整合性を尤度として定式化する。そして、報酬関数の事後平均やMAP（最大事後確率）推定値などを求める。
* **ベイジアンマルチエージェントRL:** BRLの考え方を、複数のエージェントが存在するマルチエージェントシステムへと拡張する試みである。この場合、自身だけでなく、他のエージェントの方策や能力、あるいはエージェント間の協調構造などに関する事後分布も考慮に入れる必要がある。
* **ベイジアンマルチタスクRL (MTRL):** 複数の関連するタスク間で情報を共有することにより、個々のタスクにおける学習効率を向上させることを目指す。階層ベイズモデル（HBM）などを用いて、タスク間で共通する可能性のある要素（例えば、価値関数の形状やダイナミクス、報酬関数の構造など）の分布をモデル化し、知識移転を促進する。

## 参考文献