ホーム » 「バンディット」タグがついた投稿

タグアーカイブ: バンディット

Contextual Bandit LinUCB LinTS

こんにちは。kiwamizamuraiです。

本日は文脈バンディットをやっていきます。行列とかでてきて、、、、計算が苦手な僕は、、、って感じなんですけどやってることは前回のUCBをTSと全く同じなので気楽にいきましょう。

Contextual Bandit

文脈バンディットとは以前のバンディット問題にユーザーの特徴量ベクトルを導入されたものです。というとは、前回は単純に時刻tにおいて行動価値関数のみでアームを選んでいましたが、文脈バンディットではユーザーの情報も加味してアームを選ぼうという考えです。
アルゴリズムに入っていく前に具体例と一緒にこの文脈バンディット問題の全体像を掴みます。
たとえば上の図のような感じです。報酬は購入額(例えば正規分布)とかでもいいです。とりあえず問題設定はできました。

ポリシーに対するoffline評価などはまた次回やりたいと思います。今回は単純に次の二つのポリシーの実装のお話です。

LinUCB

まずLinUCBとは前回したUCBの文脈バンディットへの拡張アルゴリズムです。この時点で上界・分散的なイメージをもって欲しいです。また、Linearの略です。見ていきます。(添字a,tは時刻tにおける行動aに対する、という意味)
LinUCBのLinearの部分はここからきています。LinUCBは報酬に対して上記の線形モデルを仮定します。また、ノイズとしてsub-Gaussianを乗せます。すると期待値は次の通りです。
このように行動aに対して確率分布を仮定し、さらにそのパラメータを逐次的に更新することでより柔軟なアームの選択が可能になります。ではそのパラメータの更新式を導出します。
上のように定義します。するとbiased-MFまたはRidgeの時と同じ導出より 次が得られます。
次にUCBの部分についてです、
どうやら上は定理のようです。そこまで終えませんでした。すいません。とはいえこれがわかったので前回のUCBを思い出してUpper Boundを加算してアームを選べばよいだけです。
まあA_aは共分散行列とやらですね、inverseをとる点だけ注意していればおkです。では改めましてpresuso-codeは
いい感じですね。ちなみにハイブリットモデルというバージョンのものもあります。
ハイブリッドでは上のように報酬に対する線形モデルが少し変わります。これは前回実装したbiased-MFと全く同じ発想で、zはユーザーの特徴ベクトル、betaは全アームに共通する共有ベクトルと行った感じです。(勝手に命名しました。)presudo-codeも貼っておきます。
でわLinear Thompson Samplingも見ていきましょう

LinTS

これは前回のTSと全く同じで事後分布からパラメータシータをサンプリングする方法です。 ただ、論文中の事前分布とかは結構複雑で結果的に次のpresudo-codeになってます、
ガウス分布を仮定していますが、パラメータが複雑なので簡略化しましょう。なので上の疑似コードは一旦無視です。
とりあえずベイズを使って上を分解していくんですけど、ここでは事前分布としてsub-Gaussianを仮定します。
尤度は今回の場合だとガウス分布です。(最初の線形モデルの仮定より)
となると事後分布なんですけど、「ガウス x ガウス = ガウス」なのですが、、、、、問題は多次元なんですよね、、、、僕計算めちゃめちゃ嫌いなんですよね、、、、 って感じで、一応サンプリングできます。

LogisticTS

ただ、前回実装したbanditって報酬はベルヌーイを仮定したじゃないです か、ということはcontextualにもあるはずですよね。

モデルは簡単です、先ほどの線形モデルにロジスティックをかますだけです。 そうなんです、あるんです、ただロジスティックを使ってしまうと事後分布が解析的には得られないので勾配法とかになっちゃうところをラプラス近似でやろう!という発想です。僕はラプラス近似をあまり知らないのでそれも勉強しないといけませんが、とりあえず話を進めると事後分布は正規分布になるようです、さらに共分散行列は対角行列らしいです。presudo-codeは次のとおりです。
ぎょえええって感じですね、これを実装しなければいけないのか、、、、

実装

実際の報酬のアームの分布は次の通りです。
LinUCBの結果
LinTSの結果
パラメータを変化させてRegretも確認
ちょっと疲れました。
ロジスティックはまた今度機会があればやります。

References

Doubly Robust AIPTW

こんにちは。kiwamizamuraiです。

本日はダブルロバストについて勉強します。まぁ、IPWも厳密には理解できていないんですけどね。。。。僕の勉強スタイルはとにかく大きく進んで大きく戻っての繰り返しです。するとたまにぱってアイデアが生まれてわかる時があります。まあそんなことはおいておいて

Recap

この記事ではダブルロバストの理論について触れます。その前に前回のIPWの復習も行い、新しい知見が得られることにも個人的に期待します。

ただ、Counterfactual Machine Learningにもダブルロバストが登場して用語などが非常にごっちゃになりやすいところだと思うのでそれについてもまとめます。

  • Multi-Arm Bandit Algorithm
  • Reinforcement Learning
  • Counterfactual Machine Learning
  • Causal Inference
ここら辺は正直ごちゃまぜになっている気がしますね。。。。。さきに断りますが今回のダブルロバストは因果推論におけるものを指します。反事実機械学習のポリシー評価に対するダブルロバストではありません。

因果推論の復習

僕たちが測りたい因果効果はATE(Average Treatment Effect)といいます。
ちなみに割り当てがされた、つまり処置群における平均処置効果はATTといいます。
ATEについては各群間での効果量の差をとればいいじゃん、という単純な案がありましたが駄目でした。それはoutcomeであるyの期待値が確率収束するものの条件付きの値だからです。つまり、上記のATEではないということです。そこでRubinのSUTVAの仮定のもとで因果効果を「無作為割り当てでないことによるバイアス」を消去しつつ測ろうというものでした。
そして登場するのが傾向スコアです。yに対してセミパラメトリックなアプローチができ、モデルの誤設定の可能性が低まります。また、N次元であった共変量が1次元になることでその影響も排除することができます。
この傾向スコアはSUTVAを満たしてくれるので等しい傾向スコアのもとで

が成り立ち、
がATEであることがわかります。少し補足をしておきます。

傾向スコアのモデルはロジスティックが一般的ですが、RFなどのアルゴリズムも使用可能です。ただ、その後たとえばマッチングを行うと仮定するとRFの高精度な分類により各分布が大きくことなる可能性があります。この場合、マッチングがうまく働かないかもしれません。なので個人的にはロジスティックがいいかなと思います。

Inverse Propensity Score Weighting

最近傍マッチングと層別解析については触れません。ここではIPWの復習を個人的に行います。このアルゴリズムは無作為割り当ての問題を解決しつATEを算出することができます。では解説します。

真の傾向スコアが既知かつSUTVAが成り立つとする。

このとき、上のように定義することでそれぞれy1,y0の周辺平均の不偏推定量となります。さらに、我々が算出する傾向スコアに対してもタイスの法則よりこれらは一致推定量になります。(ちなみに分母を集合の濃度Nで代用する方法もありますがこちらのほうが精度は高いことがしられています。)次のセクションではこの意味について考えてみます。

Pseudo-population

eは傾向スコア、つまり確率です。この逆数を重みとする、というのはどういう意味があるのでしょうか?例えば0.1の逆数は10です。0.8の逆数は1.25です。

これはつまり確率を割合として考えれば個人的にはわかる気がします。つまり、各群の集合の濃度を傾向スコアの逆数で補正しているということです。Inverse Weightingの値をPseudo-populationといいます。たとえばマッチングにおける問題点の一つは分布差でした。つまり。個体数が異なります。この個体数差をInverseで重み付けという形で加味できるということです。

Doubly Robust

では個人的に本題のダブルロバストについてです。これは二つのモデルを仮定してどちらか少なくともどちらか一方が正しければうまくいく、というものです。二つのモデルのうちの一つは単純な回帰によるATEの推定モデルです。
これはyの真のモデルであればの話です。そしてもう一つはIPWを使った上記のものです。
こちらは傾向スコアを通したATE測定のためのモデルでした。ダブルロバストはこれらを融合します。つまり、yとeのモデルを融合するということです。DR(Doubly Robust)はこれらのモデルによって得られたe,y_1y_0を用いて算出されます。
計算式は上の通りです。シグマの前の1/nはIPWのセクションで述べた理由からです。デルタはATEのことです。非常にややこしい式ですね、、、少しずつみていきます。
この大括弧内の初項はIPTW、第二項はAugmentationと呼ばれます。とりあえずこの期待値をみてみましょう。
つまり、第二項がゼロでいてくれればE(Y1)が推定できます。ではどのような時がゼロになってくれるのか?ここでダブルロバストが生きます。

まず、傾向スコアが正しくて、回帰モデルが誤っている場合。つまり、
であり、傾向スコアが真であるとき、
とうまく第二項が消えてくれました。わーい。E(y0)も同様です。では逆の場合を考えましょう。つまり、傾向スコアが誤っていて、回帰モデルが正しい場合
であり、回帰モデルmは正しい時、同じように第二項は
となります。こういう意味でダブルロバストと言われています。ちなみにですがこの推定方法をAugmented IPTWといいます。AIPTWです。

実装

データは前回と同じものを使いました。IPTWとAIPTWを比較するとわずかですが今回はIPTWが勝ちました。また、分母に集合濃度Nを用いると大きく精度が悪化しました。
次は反事実機械学習のダブルロバスト!

References

Counterfactual Machine Learning 入門

こんにちは。kzです。

本日は反事実機械学習に軽く入門してみようと思います。Causal InferenceやCounterfactual MLは個人的にはまだ若い分野だと思っていて非常に今後が楽しみです。ちなみに共分散構造分析(SEM)も気になります。

表記とか

反事実機械学習とは「オフライン環境下での新しいポリシーの学習・評価」のことです。まず記事中の表記は下の通りです。
\deltaが報酬ですね。ちなみにx_iはContextとありますがこれは文脈バンディットの文脈にあたります。Contextual Banditとは各ユーザーのデータx_iをその特徴ベクトルし、バンディット問題を達成するアルゴリズムです。この特徴ベクトルをcontextといいます。

広告を例にとりますとこんな感じです。
このデータセットSより以下を目標とします。いわばこれが反事実機械学習の考え方の核です。(ちなみにデータのことをポリシー\piによるログデータともいいます。)
まずonlineとofflineについてですがこれらは逐次学習と一括学習をそれぞれ意味します。新たなアルゴリズムによるsystemをofflineで評価することが目的です。また、より良いsystemを学習させることも目標になります。(systemはpolicyのこと)画像を通してみてみます。
ポリシーの評価についてもっとも単純なアイデアはA/Bテストですね。画像上のことです。これをcounterfactorを用いてオフラインで行うことが目標です。画像下のことです。

そこで重要なのが評価指標です。CTRなどは前回解説しました。他にも次のようなものがあります。
特にインターリービングは僕は今回初めて知ったんですがA/Bテストより大いに効果を発揮してくれるものだそうです。Netflixさんも使っているらしいです。また今度詳しくみてみます。

Reward Prediction

system\piを評価する方法の一つ目がReward Predictorです。これは報酬関数を学習により得ようとする方針です。報酬関数がわかれば新たなポリシーに対してシミュレーションができます。
ただ、この方法だと\piがバイアスに影響を受けやすいようです。考えられるバイアスとしてはモデルバイアスとセレクションバイアスがあります。モデルバイアスとは特徴量とモデルに依存します。セレクションバイアスはポリシーによる過学習(過表現)です。
モデルバイアスとは報酬関数の複雑性に起因します。この関数は非線形であったり、または考え付かないほど複雑な構造を持っているかもしれません。そのような関数を学習することは難しいです。セレクションバイアスとはポリシーによる行動選択が一部に偏ってしまう現象をいいます。これはポリシーによる各行動の分布差から生じます。

Counterfactual model

そこで登場する手法が反事実モデルです。報酬関数を高い精度で得るためにまずはポリシーの分布を近づけてバイアスを消そうというアイデアです。
次の例を考えます。
つまり3種類のアクションに対して、各報酬はバイナリです。まずは単純な評価を行ってみます。
本当にこれでいいのでしょうか?そこで反事実という概念を導入します。

選択していないアクションはCounterfactorと呼ばれます。従来のポリシーの評価では選択したアクションのみが評価対象でした、ここでは反事実つまり、選択されなかったアクションも評価にいれます。ではどうやって導入して、さらには指標として生かすのかみていきます。

Inverse Propensity Score Estimator

IPSと呼ばれる指標を紹介します。
このように行動に対するIPSは反事実を含めて算出されます。単純計算(3/4)から得られるよりも実質的な効果を表しているんじゃないかと個人的に考えています。とはいえこのIPSを用いてポリシーの評価方法を考えていきます。

IPS Utility Estimator

このIPSを用いて次のように改めて定義します。先ほどの指示関数のところが新しいポリシーによる確率分布に変わりました。分母は変わらず傾向スコアです。
こう定義することで以下が得られます。計算
んー、正直僕はまだちゃんと理解できていません。すいません。ただわかったことを改めてまとめますと反事実モデルとIPSを用いることによって新たなアルゴリズム(ポリシー)のシミュレーションができると言うことです。

最後にその他の指標について軽く触れておきます。少しでも理解しておきたい、、、、

Self-Normalized Estimator

どうやらIPSにおける定数問題を解決した指標らしい

Doubly Robust Estimator

二つの手法のいいとこ取りをした指標らしい

感想

非常に難しいです。新しい知識が多く得られたのでその点は嬉しいですが自分の実力不足にかなり萎えています。もう一度勉強しなおそうと思います。でわ

References

バンディットアルゴリズムの続き

こんにちは。kzです。

今回は前回のバンディットアルゴリズムの続きです。UCBと簡単なトンプソンサンプリングの実装を行います。前回実装した\epsilon-GreedyとBoltzmann Softmaxとの最終的な比較も行います。

Keywords

この記事のキーワードを先にリストアップします。

  • \epsilon-Greedy
  • Boltzmann Softmax
  • Hoeffding’s inequality
  • UCB
  • Bayesian UCB
  • Thompson Sampling
  • scaled inverse chi-squared Distribution
先頭2つは前回やったので3つ目から話します。

Hoeffding’s inequality

Hoeffdingの不等式です。これはUCBの導出に使います。証明にはマルコフの不等式とチェビシェフの不等式を使います。まあそれは置いておいて、この不等式の意味を考えます。

確率変数Zの平均とその期待値の誤差t\in\mathbb{R}_+の確率をtで測っています。これがまさに後述するUCBの核の考え方です。こちら側でtそ操作することで、期待値のブレの許容範囲をある確率の範囲で操作することができます。

UCB

UCBはアームの期待値に加えてその上限(Upper Confidence Bound)、いわばアームの可能性(分散)、を考慮したアルゴリズムです。どうやって上限を加味するかといいますと、対象のアームを選択した回数の逆数で重み付けします。こうすることで多数引いたアームにはより小さい上限を、少数引いたアームにはより大きい上限を付与することができます。

これは直感的にもいいですよね。何度も引いたことのあるガチャガチャよりも数回しか引いたことのないガチャガチャの方が可能性を感じますよね。そういうことです。

ただし、
見ての通り、分母N_t(a)が小さいほど大きい値が加算されます。イメージは次の感じです。
お気づきかもしれませんが逆数と言いつつ、ルートを付けてます。気になりますよね。ということで証明します。先程のHoeffdingの不等式を用います。

Hoeffdingの不等式においてX_i \in [a,b][0,1]として次が得られます。(u\geq 0)。報酬はベルヌーイを仮定しました。
a \in \mathcal{A}を一つとり固定します。私たちの問題に書き換えるためNotationを定義します。

  • r_t(a) 報酬(確率変数)
  • \mathcal{Q}(a)  を真の行動価値
  • \mathcal{\hat{Q}}(a)  を経験上の行動価値
  • u をupper confidence bound, u=U_t(a)
代入しますと
ここで上限に対する閾値をこちらで設定します。
これをU_t(a)に関して解けば終了です
おや?よくみると2の位置が異なります。それは\epsilonをこちらで設定する必要があるからです。confidence levelと言われます。

UCBはこのconfidence levelをパラメータとして持ちます。もっとも一般的な値は次のようになります。
そしてこの時のアルゴリズムをUCB1いいます。代入して計算すると
先程の結果になりました。では実装してみます。
実はよくない結果です。前回のEGとBSと比べるとわかります。この記事の最後に全アルゴリズムの比較を行いますのでとりあえずは進めていきます。

Bayesian UCB

UCBにベイズを応用したアルゴリズムのことです。今までは報酬の分布にベルヌーイを仮定しましたが、他にもガウス分布の仮定があります。それぞれ次のように呼びます

  • Bernoulli – Thompson Sampling
  • Gaussian – Thompson Sampling
察しの通り事後分布からパラメータをサンプリングしてアームを選択します。

本当にハードなんですが、Gaussianの場合の詳しい計算は この方がやってくれています。

Thompson Sampling

定義は少し複雑ですが、実装の際はサンプリングを行うので思ったよりはシンプルです。
とあるaが他のどのa'よりも価値が高い、という事後確率(\pi)を計算してaを選ぶアルゴリズムです。R_tは時刻tまでのアームのhistoryです。

事後確率は積分を用いて次のように計算されます。
ここでR_iarm_iの報酬履歴です。左の積分が\mathcal{Q}(a) = \theta_iになる確率で右の積分がその他のアームで\mathcal{Q}(a') \leq \theta_iとなる確率です。積分が解析的ではないので、サンプリングします。困ったときはサンプリングです。結果アルゴリズムは次のように単純化できます。
  1. 各アームaの報酬の期待値に関する事後分布\pi( \theta  |R_a)から乱数\theta_aを生成
  2.  TS(a) = \arg \max_{a\in\mathcal{A}}  \theta_a \sim \pi( \theta |R_a)
何度も言いますが報酬の分布はベルヌーイを仮定するので事後分布であるベータ分布は非常にシンプルになります。
実装では一様分布を仮定するのでパラメータは共に1とします。

Best Arm RateをUCBと比較してみます。
全アルゴリズムでBARとCumulative Rewardsも比較してみます。
Thompson Samplingが圧勝でした。

scaled inverse chi-squared Distribution

もしGaussianでThompson Samplingを実装するならばこちらを\sigma^2の事前分布として導入します。(事前分布p(\mu, \sigma^2)を条件付き確率で分解する)scaled inverse chi-squared分布といいます。

    \[  p (\sigma^2) \sim  \mathcal{X}^2 (v_{0}, \hat{\sigma}_{0}^{2})  \]


Code

Gaussian Thompson Samplingすごく難しいですね、パラメータが多すぎてなにがなんだが、、、

次回はContextual BanditとIPSについてまとめたいと思います。でわ

References

強化学習 Bandit Algorithm で入門する

こんにちは。kzです。

本日は強化学習に入門します。けどMDPとかはやらないので安心してください。簡単だと思います。ビジネスにおいてもバンディット問題は多くあるということなのでためになるかなーと思います。

Keywords

この記事のキーワードを先にリストアップします。こうしたほうが読みやすくないか?と最近やっと気づきましたすいません。

  • Exploitation / Exploration
  • MAB (Multi-Armed-Bandit)
  • Advertising Technology
  • A/B Test
  • Bayesian A/B Test
  • \epsilon – Greedy
  • Boltzmann Softmax

Exploration / Exploitation

  • Exploitation is 活用
  • Exploration is 探索
になります。僕の日常生活を例にして説明します。

ラーメンが好きで毎回行きつけのラーメン屋さんにいくんですよね。もちろん、毎回いっているということはそこが美味しいって経験からわかっているので通っているんです。これがExploitationです。

しかし、同じラーメン屋さんにばかり通っていると仮に近くにもっと美味しいラーメン屋さんやつけ麺屋さんがあってもその存在を知り得ないですよね。なのでたまには自分の知らないお店に期待していきたくなりますよね。僕も3回に1回くらいの割合で新しいお店を体験します。これがExplorationです。

ただ、新しいお店だと「美味しい!」時と「普通かなー」な時と「んー」な時がありますよね。これらを報酬といいます。もちろん報酬の高い、つまり「美味しい!」を選択できるようなExplorationができれば理想ですね。

これらを考慮すると、ベストな選択としては行きつけでExploitationしつつも期待度の高いお店にExplorationしたいですよね。
期間T内で探索・活用をベストな比率で行って最終的に最高の報酬(満足度)を得たい!がBandit問題です。

Multi-Armed Bandit

上記のように複数の選択肢に対してExploration / Exploitationを考える問題を多腕バンディット問題といいます。

  • 期待値がわからないK個の選択肢が存在する
  • N回の試行全てにおいて最善の選択肢を選び続けトータルの報酬を最大化したい
という感じです。(お気づきの方もいるかもしれませんが状態Sを考えません。厳密には|S| = 1

もっともポピュラーな例は広告の最適化とかですかね。薬の投与などもたまにExampleで見られますがここでは広告を例にして話を進めます。なのでいったんBanditからは離れてこれについてちょっと深入りしていきます。

Advertising Technology

広告に関わる全住民つまり、広告主側と媒体側(広告主,メディア,消費者)を幸せにするためのテクノロジーです。

そのなかでもReal time bidding(RTB)がキーワードになります。それを説明する前に次の用語を簡単に

  • DSP (Demand-Side Platform)
  • SSP (Supply Side Platform)
DSPは広告主側の広告効果を最適化するため、ユーザーに適した単価の安い配信先を探す側。媒体側の広告収益を最適化するため、より高額な広告に入札する側です。

つまり、DSPが「この広告貼ってー」とお願いし、SSPが「ええよー」と返します。しかし、一対一関係ではないので「俺の広告も貼ってくれー」といろんな人がお願いします。(SSPも複数あります。サイトA、サイトB的な感じです)

そんなマーケットのことをRTBといいます。複数のDSPが各々資金を持ってSSPに交渉し、最も価格の高いDSPをSSPが決定します。ただ値段の妥当性がわからないですよね。これも機械学習で最適化するそうです。そこで次の用語が登場します。

  • CVR:ConVersion Rate.コンバージョン率
  • CTR:Click Through Rate.クリック率
これらの指標をもちいてDSPの値段が決定されたりします。これ以上はここでは触れません。気になる方は参考文献より飛んでください。

Bayesian A/B Test

A/Bテストってご存知ですよね。AとBどっちがいいの??を統計学的仮説検定を元に検証する試験のことです。

Bayesian A/Bテストとは、A/Bテストをベイズでやろう!!のことです。たとえば商品Aの購入率がp、商品Bの購入率がqとしたとき分布に有意差あんの?をベイズで解決します。

この方の記事が最高に纏まっています。一応僕もベイズ推定の記事書いてます。

ちなみにバンディットのアルゴリズム実装の最後にベイズ使うので理解しておくことをおすすめします。

Banditを再確認

これらを踏まえてBanditをおさらいすると
バンディットアルゴリズムはアームを選択した結果得られる報酬を逐次的に反映し、次のアームの選択に活かすことからA/Bテストに比べて機会損失の低減が見込めます。いわば逐次最適化A/Bテスト的な感じですかね。


加えてですねえ、A/Bテストは事前分布の問題もあるのでねえ、では次のセクションで最適化に移るためにBandit Algorithmを定式化します。
英語やああああああ、と思わないでください。よく見てくださいめっちゃ簡単な単語しか出てきてません。

注目して欲しいのは\mathcal{Q}(a)です。これは行動aを入力とする行動価値関数と言われます。
注目すべきはRegret(後悔)です。これは最適な行動価値から実際にとった行動価値の差分で定義されます。定義より小さいほうがいいことがわかります。

\epsilon – Greedy

では一つ目のアルゴリズムの紹介です。
  • パラメータ\epsilon \in (0,1)を設定
  • \epsilonの確率でExploration
    • ランダムでArmを選択
  • 1-\epsilonの確率でExploitation
    • 経験を元に、最大の行動価値を持つArmを選択
経験を元に算出される行動価値は次で定義されます
ただし
はaction=aが選択された総数です。したがってExploitationは次のように定式化されます
\epsilonを変化させて実装結果を確認します。アームは10種類でそれぞれの確率は単調増加で設定しました。なのでインデックスでは9番が最大の行動価値をもったアームということになります。
たしかに、\epsilonを増やすとExplorationが多くされていることがわかりまうす。Rewardsと最適なアームを選んだ割合(BAR)の変化を比較します。
青が小さい\epsilonでオレンジが大きい\epsilonでの結果です。\epsilonをおきくするほど探索の割合が大きくなるのでその影響がBARに顕著に現れています。

Boltzmann Softmax

\epsilonの問題は探索をランダムで行っている点です。つまり、実際には行動価値の高いアームも低いアームも等確率で扱っていた点です。BoltzmannのアルゴリズムではSoftmax関数を用いることで各アームを経験行動価値で重み付します。その出力をそれぞれのアームの確率で扱います。
  • パラメータ\epsilon \in (0,1)を設定 (small)
  • パラメータw \in (0,1)を設定 (small)
  • \epsilonの確率でExploration
    • 各Armの行動価値をSoftmaxで重み付けし選択
  • 1-\epsilonの確率でExploitation
    • 経験を元に、最大の行動価値を持つArmを選択
定式化すると次のようになります。
よく見てみるとwで割り算されていることがわかります。これもハイパーパラメータです。察しの通りでw \rightarrow \inftyのときp_a = 1/|\mathcal{A}|となるので\epsilon-Greedyと同じようになります。

したがってExploitationは次のように定式化されます
では実装結果を確認します。
\epsilon-Greedyと比較してみます。
いいかんじ
Tを分割して確認しますとうすい水色である本来のベストなアームがT=200を超えたあたりから盛り返してきてることがわかります。

最後にコードを貼っておきます。
次回はUDBとThompson sampling実装しますー。でそのノリでContextual Banditとかも頑張りますー。

References

  • https://accel-brain.com/semantics-of-natural-language-processing-driven-by-bayesian-information-search-by-deep-reinforcement-learning/verstarkungslernalgorithmus-als-funktionale-erweiterung-des-banditenalgorithmus/
  • https://ferret-plus.com/11986
  • https://www.cs.princeton.edu/courses/archive/fall16/cos402/lectures/402-lec22.pdf
  • https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html
  • https://www.smartbowwow.com/2018/08/python.html
  • https://haltaro.github.io/2017/08/08/introduction-to-ad-tech
  • https://github.com/brianfarris/RLtalk/blob/master/RLtalk.ipynb
  • https://blog.albert2005.co.jp/2017/01/23/%E3%83%90%E3%83%B3%E3%83%87%E3%82%A3%E3%83%83%E3%83%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%80%80%E5%9F%BA%E6%9C%AC%E7%B7%A8/
  • https://www.cs.princeton.edu/courses/archive/fall16/cos402/lectures/402-lec22.pdf