多腕バンディット入門

Copyright 2021 TF-AgentsAuthors。

序章

多腕バンディット（MAB）は、エージェントが長期的に累積報酬を最大化するためにアクション（アーム）を選択する必要がある機械学習フレームワークです。各ラウンドで、エージェントは現在の状態（コンテキスト）に関する情報を受け取り、この情報と前のラウンドで収集された経験に基づいてアクションを選択します。各ラウンドの終わりに、エージェントは選択されたアクションに関連付けられた報酬を受け取ります。

おそらく、最も純粋な例では、MABに名前を貸した問題です：私たちが直面していることを想像しkスロットマシン（片腕の山賊）、そしてあまりにも多くのお金を失っていない一方で、我々は、1が最高の支払いを持っているかを把握する必要があります。

各マシンを一度試してから、最も支払いの多いマシンを選択するのは良い戦略ではありません。エージェントは、最初は幸運な結果をもたらしたが、一般的には最適ではないマシンを選択することに陥る可能性があります。代わりに、エージェントは、見栄えの悪いマシンを繰り返し選択して、それらに関する詳細情報を収集する必要があります。これは多腕バンディット問題の主な課題です。エージェントは、最適なアクションを見落とさないように、事前の知識を活用することと探索することの適切な組み合わせを見つける必要があります。

MABのより実用的な例には、学習者が決定を下すたびに、副次的な情報が含まれます。このサイド情報を「コンテキスト」または「観察」と呼びます。

多腕バンディットと強化学習

TF-AgentsライブラリにMABスイートがあるのはなぜですか？ RLとMABの関係は何ですか？多腕バンディットは、強化学習の特殊なケースと考えることができます。引用するRLにイントロを：

各時間ステップで、エージェントは、そのポリシーに基づいて、環境上のアクションをとる $\pi(a_t|s_t)$、 $s_t$ 環境から現在の観測であり、報酬受信 $r_{t+1}$ 、次の観察 $s_{t+1}$ 環境から。目標は、報酬の合計（リターン）を最大化するようにポリシーを改善することです。

一般的なRLの場合には、次の観測 $s_{t+1}$ 以前の状態に依存 $s_t$ 及びアクション $a_t$ ポリシーによって取られます。この最後の部分は、MABをRLから分離するものです。MABでは、次の状態である観測は、エージェントによって選択されたアクションに依存しません。

この類似性により、TFエージェントに存在するすべての概念を再利用できます。

• 環境出力の観察、および報酬とアクションに応答します。
• ポリシーは、観察に基づいてアクションを出力し、そして
• エージェントを繰り返し、以前の観測アクション・報酬のタプルに基づいてポリシーを更新します。

きのこ環境

説明のために、「きのこ環境」と呼ばれるおもちゃの例を使用します。マッシュルームデータセット（ Schlimmer、1981 ）食用と毒キノコの標識された例から成ります。特徴には、形、色、きのこのさまざまな部分のサイズ、臭いなどがあります。

きのこデータセットは、すべての教師あり学習データセットと同様に、コンテキストMAB問題に変換できます。我々はまたによって使用される方法を使用リケルメら。 （2018年） 。この変換では、エージェントはキノコの特徴を受け取り、それを食べるかどうかを決定します。食用キノコを食べると+5の報酬が得られますが、有毒キノコを食べると同じ確率で+5または-35のいずれかが得られます。きのこを食べないと、きのこの種類に関係なく、報酬は0になります。次の表は、報酬の割り当てをまとめたものです。

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

LinUCBエージェント

状況に応じた盗賊環境でうまく機能するには、観察結果を踏まえて、各アクションの報酬関数を適切に見積もる必要があります。 1つの可能性は、線形関数を使用して報酬関数を推定することです。 、すべてのアクションのためのものであること $i$、我々はパラメータ見つけようとしている $\theta_i\in\mathbb R^d$ 見積もりのために

$r_{t, i} \sim \langle v_t, \theta_i\rangle$

可能な限り現実に近いです。ここで $v_t\in\mathbb R^d$ 時間ステップで受信したコンテキストです $t$。エージェントは、その見積りの非常に自信を持っている場合はその後、それは選択することができます $\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle$ 予想される最高の報酬を得るために。

上で説明したように、最も良い推定報酬を持つアームを選択するだけでは、良い戦略にはつながりません。 （参照例があり、線形推定量の薬で搾取と探査を混合するさまざまな方法があり、最も有名なの一つは、（LinUCB）アルゴリズムバウンドリニアアッパー自信あるLiら2010 ）。 LinUCBには2つの主要な構成要素があります（一部の詳細は省略されています）。

1. これは、線形最小二乗ですべてのアームのパラメータの推定値を維持します。 $\hat\theta_i\sim X^+_i r_i$、 $X_i$ と $r_i$ アームラウンドの積層コンテキストと報酬です $i$ 選ばれた、と $()^+$ 擬似逆であります。
2. これは、逆共分散によって定義された信頼楕円体を維持 $X_i^\top X_i$ 上記の見積もりのために。

LinUCBの主なアイデアは、「不確実性に直面した場合の楽観主義」です。エージェントは、推定値の分散に対応する量だけ推定値をブーストすることにより、探索を組み込みます。信頼楕円体は、画像に入って来るところである：すべての腕のために、楽観的な推定値である $\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle$、 $E_i$ 楕円体の周りにある $\hat\theta_i$。エージェントは最高の探してアーム選ぶ $\arg\max_i\hat r_i$。

もちろん、上記の説明は、LinUCBが行うことの直感的ですが表面的な要約です。実装は、私たちのコードベースで見つけることができるここに

次は何ですか？

あなたが私たちのバンディッツのライブラリに、より詳細なチュートリアルを持っているしたい場合は、私たちを見てとるバンディッツためのチュートリアルを。代わりに、あなたはすぐに私たちのライブラリを探索を開始したい場合、あなたはそれを見つけることができるここに。あなたも、より多くの熱心なトレーニング、当社のエンド・ツー・エンドの例のいくつかを見て開始するようにしている場合は、ここでLinUCBと、上記のキノコ環境を含め、ここに。