バンディット問題の理論とアルゴリズム

バンディット問題の概要

人生は選択の繰り返しとなる。何度も同じような状況に遭遇し、過去の経験に基づいて、ある道を選択する。もしもあのときあの道を選択していたら、と後悔することもあるが、そのときはその道を選択していたら、本当にもっとよい現在があったかどうかは確かでない。

どうしたら”後悔のない(without regret)”選択ができるかは難しい問題だが、一つ言えることは「探索」と「知識利用」のバランスが重要であるということとなる。選択可能な道の中には、よいかどうか知らない道もあるし、逆にある程度よいことを既に知っている道もある。今までの知識を利用して知っている道を選んでいたら悪くはない現在があるかもしれないが、知らない道を選んでいたらもっとよい現在があったかもしれないという後悔が残る。

逆にもっとよい道を探そうと知らない道を選択した結果、その道が知っている道より良くないとわかり、やはり知っている道を選んでおけばよかったという後悔が残る可能性もある。最適な選択をするためには、もっとよい道を探す「探索」と今までの経験を生かす「知識利用」のバランスを取る必要があり、まさにこれがバンディッド問題の本質となる。

現代はネット社会になり、各個人の好みにあった新着ニュースや商品広告の配信が容易になった。ここで、システムの設計者は各ユーザーに対して、最もクリック率が高いニュースや広告を配信することを目指すが、真のクリック率は道であるため実際にはそれらの推定値を代わりに用いることになる。

その際に、現在の推定クリック率が低くても配信回数が少ないものは、真のクリック率が高い可能性があるため、配信回数が多いものに比べてより積極的に配信しユーザーの反応を観察する(探索を行う)必要がある。一方、全体のクリック数を増やすためには推定クリック率が高いニュースや広告を多く配信する(知識利用を行う)必要がある。多腕バンディット問題は、このような探索と知識利用のバランスを最適化する問題として定式化され、それらを一般化した問題を含めてバンディット問題と総称される。

バンディット問題は新薬の治療に応用できることから、古くから研究があったが、近年になって上述のようにインターネット関連の応用と非常に相性が良いことから爆発的に研究が増加している。最近ではトンプソン抽出といった優れた探索戦略(方策)の発見に伴い。基本的な設定における最適戦略については概ね解決しつつあるため、現実問題により即したさまざまな設定に対しての研究が多くなされている。

しかし、それでも既存研究の存在する設定が現実問題にそのまま当てはまることは必ずしも多くはない。そのため、個別の設定に対するショアうさいな解析よりも、その設定における方策がどのような根拠で構成されているかを理解することが、現実問題への適用や新たな定式化に対する研究においてしばしば重要となる。

バンディット問題は、機械学習の分野における強化学習の一種で、複数の選択肢（アーム）のうち、どのアームを選ぶかを決定する問題となる。各アームは、ある確率分布に従って報酬を生成するが、その確率分布はエージェントには未知であり、エージェントは、何度かアームを引いて報酬を受け取りながら、どのアームが最も報酬が高いかを見つける。このようなバンディット問題は以下のような様々な仮定のもとで問題を解くことになる。①エージェントは、独立に各アームを選択する、②各アームは、ある確率分布に従って報酬を生成する、③アームの報酬は、エージェントには観測可能だが、確率分布は未知となる、④エージェントは、何度かアームを引いて報酬を受け取る。

またバンディット問題では、エージェントはどのアームを選択するかを決定するため、以下に示すようなアルゴリズムを使って報酬が最大となるアームを選択するための戦略を学習する。①ε-greedy法(一定の確率εでランダムにアームを選択し、残りの確率1-εで最も報酬が高いアームを選択する)、②UCBアルゴリズム(最も不確かなアームを優先的に選択することで、報酬の上限を増やすことを目指す)、③トンプソン抽出法(アームの確率分布の事後分布から、次に選択するアームをサンプリングする)。

本ブログではこれらバンディットに関して、以下に詳細の内容について示している。

実装

• バンディット問題の概要と適用事例及び実装例

バンディット問題(Bandit problem)は、強化学習の一種であり、意思決定を行うエージェントが未知の環境において、どの行動を選択するかを学習する問題となる。この問題は、複数の行動の中から最適な行動を選択するための手法を見つけることを目的としている。

ここではこのバンディット問題に関して、ε-グリーディ法、UCBアルゴリズム、トンプソンサンプリング、softmax 選択、置換則法、Exp3アルゴリズム等の主要なアルゴリズムの概要と実装および、適用事例としてオンライン広告配信、医薬品の創薬、株式投資、クリニカルトライアルの最適化等とそれらの実装手順について述べている。

• マルチアームドバンディット問題の概要と適用アルゴリズム及び実装例について

マルチアームドバンディット問題（Multi-Armed Bandit Problem）は、意思決定の問題の一種で、複数の選択肢（アーム）の中から最も報酬の高い選択肢を見つける問題で、この問題は、リアルタイムの意思決定や探索と活用のトレードオフを扱うアプリケーションに用いられるものとなる。

• ε-グリーディ法（ε-greedy）の概要とアルゴリズム及び実装例について

ε-グリーディ法（ε-greedy）は、強化学習などの探索と活用（exploitationとexploration）のトレードオフを取り扱うためのシンプルで効果的な戦略であり、このアルゴリズムは、最適な行動を選択する確率と、ランダムな行動を選択する確率を調整する方法となる。

• ボルツマン分布とソフトマックスアルゴリズム及びバンディット問題

ボルツマン分布（Boltzmann distribution）は、統計力学や物理学において重要な確率分布の一つであり、この分布は、系の状態がどのようにエネルギーに分布するかを記述するものとなる。ボルツマン分布は、機械学習や最適化アルゴリズムにおいて重要な役割を果たす確率分布の一つであり、特に、確率的なアプローチやモンテカルロ法に基づく手法で以下のような広い範囲で利用されている。ソフトマックスアルゴリズムは、前述のボルツマン分布の一般化と見なすことができ、前述のようにボルツマン分布が適用されいた機械学習のアプローチにソフトマックスアルゴリズムを適用することがてできる。ここでは、バンディット問題への適用について以下に詳しく述べる。

• UCB（Upper Confidence Bound）アルゴリズムの概要と実装例

UCB（Upper Confidence Bound）アルゴリズムは、多腕バンディット問題（Multi-Armed Bandit Problem）において、異なるアクション（または腕）の間で最適な選択を行うためのアルゴリズムであり、アクションの価値の不確実性を考慮し、探索と利用のトレードオフを適切に調整することで、最適なアクションの選択を目指す手法となる。

• Thompson Samplingアルゴリズムの概要と実装例

Thompson Sampling（トンプソン・サンプリング）は、強化学習や多腕バンディット問題などの確率的意思決定問題に使用されるアルゴリズムであり、このアルゴリズムは、複数の選択肢（アクションまたはアームと呼ばれることが多い）の中から最適なものを選択する際に、不確実性を考慮するために設計されたものとなる。特に、各アクションの報酬が確率的に変動する場合に有用となる。

• カウントベースのマルチアームドバンディット問題アプローチについて

カウントベースのマルチアームドバンディット問題（Count-Based Multi-Armed Bandit Problem）は、異なるアクション（アーム）から報酬を獲得するという状況で、各アームの報酬分布が未知であると仮定する問題であり、強化学習の一種で、主な目標は、アームの選択によって得られる報酬を最大化するような方策（政策）を見つけることとなる。

• Boltzmann Explorationの概要とアルゴリズム及び実装例について

Boltzmann Explorationは、強化学習において探索と活用のバランスを取るための手法の一つであり、通常、”ε-グリーディ法（ε-greedy）の概要とアルゴリズム及び実装例について“で述べているε-グリーディ法がランダムに行動を選択する確率を一定に保つのに対し、Boltzmann Explorationは行動価値に基づいて選択確率を計算し、これを使って行動を選択している。

• contextual bandit問題の概要とアルゴリズム/実装例について

Contextual banditは、強化学習の一種であり、複数の選択肢の中から最適な選択をする問題を解決するための枠組みとなる。この問題は、現在の状況(コンテキスト)に基づいて最適な選択をする必要がある場合に適用されるものとなる。Contextual bandit問題は以下の要素から構成される。ここではこのContextual banditに関して様々なアルゴリズムとpythonによる実装例について述べている。

• EXP3 (Exponential-weight algorithm for Exploration and Exploitation)アルゴリズムの概要と実装例について

EXP3（Exponential-weight algorithm for Exploration and Exploitation）は、多腕バンディット問題（Multi-Armed Bandit Problem）におけるアルゴリズムの一つであり、複数の選択肢（アーム）からなるスロットマシンを操作し、各アームの報酬を最大化するという問題設定のアプローチとなる。EXP3はこのような状況で、探索（Exploration）と活用（Exploitation）のトレードオフをうまくバランスさせながら、最適なアームを見つけることを目指すものとなる。

• バンディット問題に利用可能なライブラリ

バンディット問題でのライブラリは少なく、Rで提供されているものが主となる。

1. • Bandit: Rでバンディット問題を解くためのライブラリで、多数のアルゴリズムをサポートしている。ε-greedyやUCB1、Thompson Samplingなどのアルゴリズムが実装されている。
   • arm: Rで多腕バンディット問題を解くためのライブラリで、多数のアルゴリズムをサポートしている。最適なアルゴリズムの選択や、アルゴリズムのパラメータ調整にも対応している。
   • MAB: googleが提供しているRでバンディット問題を解くためのライブラリ。

理論

• 機械学習プロフェッショナルシリーズ 「バンディット問題の理論とアルゴリズム」 読書メモ
• バンディッド問題の概要と歴史と強化学習/オンライン学習との関係

バンデッド問題(bandit problem)とは、選択肢の集合から一つの要素を選択し、その選択肢に対する報酬を得るがほかの選択肢の報酬情報は得られない、というプロセスを繰り返す設定において、報酬和の最大値を目指す逐次決定問題となる。バンディット(盗賊)という名前は、一つのアームがついた古典的なスロットマシンをプレイヤーにお金を使わせる(お金を奪う)ことにちなんで1腕バンディット(one-armed bandit)と呼ぶことに由来している。

バンディット問題は大きく分けて、各アームからの報酬が何らかの確率分布に従って生成される確率的バンディット(stochastic bandit)と、プレイヤーの方策を知っている敵対者が報酬を決める場合を想定する敵対的バンディット(adversarial bandit)の2つに分類できる。

バンディット問題のように過去の観測に応じて次にサンプルを取得する対象を選択する問題は適応割り当て(adaptive allocation)あるいは逐次割り当て(sequential allocation)といった名前で古くから研究がなされている。

• 確率的バンディッド問題の基礎

確率的バンディット問題において考えることになる主要な問題は「ある広告の現在のクリック率\(\bar{\mu}\)が5%以下であるとき、その真のクリック率マイクロが実はμ=10%である可能性はどれくらいか?」という形のものとなる。これは統計の言葉で一般的に書くと「真のクリック率がマイクロであるとき、その標本平均があるx∈[0,1]に対して、\(\hat{\mu}\leq x\)となる確率(尤度)はどれくらいか」という問題となる。

• 確率的バンディッド問題の方策 -理論的限界とε-貪欲法

今回は確率的バンディットにおける最も基本的な設定について述べ、達成可能な理論限界とε-貪欲法について述べる。

• 確率的バンディッド問題の方策 尤度に基づく方策(UCBとMED方策)

前回述べたようにε-貪欲法はどのようにεをとっても真の分布のパラメータ{μi}i次第ではO(logT)のリグレットを達成できないものであった。O(logT)のリグレットを常に達成する(あるいはより競技には、その係数部まで定理2の理論限界を達成する)方策の構成にはいくつか種類があるが、そのうち最も基本的なものがUCB方策といった尤度比較に基づく方策となる。

UCB方策で重要なのは期待値最大でないアームの誤選択率が1/t程度となるように制御することであり、真の期待値についての信頼区間を計算すること自体は必ずしも本質的ではない。そこで、この誤選択率を直接制御することを目指す方策の体型としてMED方策があり、それらのうち最も直感的な理解が容易なものがDMED方策(Deterministic Minimum Empirical Divergence policy)となる。

• 確率的バンディッド問題の方策 確率一致法とトンプソン抽出

KL-UCCB方策は真の期待値の有意水準1/t信頼区間の上限をチェルノフ・ヘフディングの不等式により求めるものと解釈できたが、チェルノフ・ヘフディングの不等式はサンプル数nに対して確率を\(O(\sqrt{n})\)倍ほど過大評価しており、それにより本来は期待値最大である可能伊勢が非常に小さいアームに対して余分な探索を行う場合がある。さらに、この有意水準1/tというのは漸近的な理論限界の議論から導かれた値であり、これをO(1/t)なる別の値に置き換えても漸近最適性が証明できてしまう一方で、その有限時刻での性能は大きく変動する。

これらの漸近論を介した理論限界に頼らずに良い性能を達成する為のヒューリスティクスの一種として、確率一致法(probability matching method)と呼ばれるものがある。これは「それぞれのアームが期待値最大である”確率”」を何らかの方法で定式化し、引くアームをその確率に従ってランダムに選ぶものとなる。例えばソフトマックス方策(softmax policy)は、各アームiが期待値最大である確率が温度パラメータr>0のギブス分布を用いて\(e^{\hat{\mu}_i/r}\)に比例すると考え、それらを規格化した以下の確率でランダムにアームを引く方策となる。

• 確率的バンディッド問題の為のリグレット解析について

今回は確率的バンディット問題におけるアルゴリズムの性能評価を行う一般的な枠組みについて述べ、それによって「よい」バンディットアルゴリズムが満たすべき条件について述べる。またこの枠組みに基づき、実際のリグレット上界を計算する。

前述では、UCBやトンプソン抽出といった方策が、いずれも「期待値最大である有意水準あるいは事後確率が1/t以上のアームを引く」と解釈することができることについて述べた。これらの直感的な理解はより広義のバンディット問題のクラスにも適用可能であり、そういった問題に対して高性能となる方策のアイデアを得るためには有用だが、その具体的な性能評価にはみう少し詳細な議論が必要となる。ここではベルヌーイ分布モデルを例に、確率的バンディット問題におけるリグレット解析の基本的な考え方について述べ、それをもちいてUCB方策とトンプソン方策の理論評価を行う。

• 敵対的バンディッド問題でのHedgeアルゴリズムとExp3方策

今回は敵対的バンディットにおける設定について述べ、計算論的学習理論における全情報設定のオンライン学習アルゴリズムであるHedgeアルゴリズムのバンディット版としてExp3方策およびその変形であるExp3.P方策について述べ、擬リグレットおよび高確率(で成り立つ)リグレット上界を証明する。また疑リグレットの下界を証明し、下界と同じオーダーの擬リグレットを達成するPoly INF方策について述べる。

• Exp3.P方策と敵対的多腕バンディット問題の下界の理論概要

Exp.3方策はO(TKlogK)の擬リグレットを達成するが、高い信頼性でよいリグレットが得られるとは限らない。Exp3.P方策(Exp3.P policy)では、各アームjの時刻tでの重みをそのアームのそれまでの累積報酬G_j,tの推定値\(\hat{G}_{j,t}\)ではなく、信頼上界\(\hat{G}_{j,t}\)を使って\(\frac{1}{K}e^{\eta\hat{G}_{j,t}}\)に設定する。

パラメータをうまく定めたExp3.Pの疑リグレット上界はO(TKlogK)であることがわかったが、敵対的バンディット問題に対する方策として、この疑リグレットを達成する方策は良い方策といえるのか?それをチェックする一つの方法は、敵対的多腕バンディット問題に対する疑リグレット下界、つまりどのような方策に対しても生じてしまう疑リグレットと比較することとなる。

• バンディット問題における最適腕識別とA/Bテスト(1)

前回までのバンディット問題では、各スロットマシンの期待値を推定(探索)しつつ適切な頻度で現時点で期待値最大と推定されるマシンを選択(知識利用)することで、累積報酬を最大化することを目的としていた。一方、実用上の場面では、探索の期間が明確に区別されていて、その期間中で期待値最大のスロットマシンを高確率で識別したい、という問題も多く現れている。今回は、このような純粋な探索の問題における効率的な方策について述べる。

• バンディット問題における最適腕識別とA/Bテスト(2)

ここでは、厳密な最適腕識別およびε-最適腕識別の両方を含む設定として、事前に定めたε≥0に対してε-最適腕識別を行う方策について考える。方向性として、まず固定信頼度の設定に対する方策について述べ、それらの方策を固定予算の場合に応用する方法について述べる。

リグレット最小化の場合と同様に、方策の構成において中心的な役割を果たすのが信頼区間の考え方となる。ここで累積報酬最大化において信頼上限(Upper Confidence Bound,UCB)をアーム選択の基準として用いることが有効だったのに対して、最適腕識別では以下に説明するような信頼下限(Lower Confidence Bound,LCB)も同時に考えることが重要となる。

• 線形バンディット、文脈付きバンディット、LinUCB方策での線形バンディッド問題

シンプルなバンディット問題の設定では、あるスロットマシンからり報酬が別のマシンに関する情報を一切持たない場合を考えている。一方で実際の応用では、それぞれのスロットマシンが何らかの特徴量によって関連づけられていて、それを用いることであるスロットマシンからの報酬から別のマシンの報酬の性質を推定できる場合が数多くある。ここではそのような設定の代表的な定式化として、報酬期待値が特徴量に関する線形モデルにより表される場合を考える。また、時刻ごとにスロットマシンの特性が変化する文脈付きバンディットも同様の枠組みで定式化することができる。

• トンプソン抽出、ロジスティック回帰モデル上の線形バンディット問題

前述ではUCB方策の線形モデルに対する自然な一般化としてLinUCB方策について述べた。同様にトンプソン抽出を線形モデルに対して一般化することについて述べる。

• プレイヤーの行動の候補が膨大あるいは連続的な場合の最適腕バンディットとベイズ最適(1)

今回は、学習パラメータの調整などのプレイヤーのとりうる行動の候補が膨大あるいは連続的な場合のバンディット問題の定式化と方策について述べる。また、報酬がガウス過程によって生成れるとするベイズ最適化についても述べる。

• プレイヤーの行動の候補が膨大あるいは連続的な場合の最適腕バンディットとベイズ最適(2)

連続腕バンディットにおいては、有限腕バンディットの方策の自然な拡張が可能である他、特に雑音なし・単純リグレット最小化のための方策については、ブラックボックス最適化の研究の文脈でさまざまなものが提案されている。以下では、まずf(a)が生成されているカーネルおよびスケールパラメータσ0,λが既知である場合を考える。これらの推定については後述する。

• バンディッド問題の拡張としての時間変化のあるバンディット問題と比較バンディット

バンディット問題には線型バンディットのほかにも様々な拡張や一般化がある。ニュース推薦などの設定では、クリックの有無といったバンディット問題の報酬に対応する量の確率分布が時刻とともに変化する場合がある。このような設定はいくつか定式化が考えられ、その定式化に応じてさまざまな方策が考えられる。ここではそれらのうち代表的なものについて述べる。

• バンディット問題の拡張としての部分観測問題について

バンディット問題には線型バンディットのほかにも様々な拡張や一般化があり、ここではそれらのうち実用上重要あるいは最近注目されている部分観測問題やその他の拡張について述べる。

• バンディット手法の応用(1)モンテカルロ木探索

ここではバンディット手法の応用として、”モンテカルロ木探索の概要とアルゴリズム及び実装例について“でも述べているゲーム木探索がどのようにしてバンディット問題として扱うことができるのか、また使われている技術は何かについて述べる。

• バンディット手法の応用(2)インターネット広告

今回はインターネット広告での最適な課金・報酬を求めるためにバンディット問題の手法を適用したケースについて述べる。

• バンディット手法の応用(3)推薦システム

今回は最適な推薦解を求めるためにバンディット問題の手法を適用したケースについて述べる。