論文の概要: Maillard Sampling: Boltzmann Exploration Done Optimally

• arxiv url: http://arxiv.org/abs/2111.03290v1
• Date: Fri, 5 Nov 2021 06:50:22 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-08 14:45:22.344909
• Title: Maillard Sampling: Boltzmann Exploration Done Optimally
• Title（参考訳）: Maillardのサンプリング:ボルツマン探査が最適に
• Authors: Jie Bian, Kwang-Sung Jun
• Abstract要約: この論文は、$K$武装バンディット問題に対するランダム化アルゴリズムを示す。 メイラードサンプリング(MS)は、各アームを閉じた形で選択する確率を計算する。 最適性を失わずに$sqrtKTlogK$に制限された最小値を改善するMS$+$というMSの変種を提案する。
• 参考スコア（独自算出の注目度）: 11.282341369957216
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The PhD thesis of Maillard (2013) presents a randomized algorithm for the $K$-armed bandit problem. This less-known algorithm, which we call Maillard sampling (MS), computes the probability of choosing each arm in a closed form, which is useful for counterfactual evaluation from bandit-logged data but was lacking from Thompson sampling, a widely-adopted bandit algorithm in the industry. Motivated by such merit, we revisit MS and perform an improved analysis to show that it achieves both the asymptotical optimality and $\sqrt{KT\log{T}}$ minimax regret bound where $T$ is the time horizon, which matches the standard asymptotically optimal UCB's performance. We then propose a variant of MS called MS$^+$ that improves its minimax bound to $\sqrt{KT\log{K}}$ without losing the asymptotic optimality. MS$^+$ can also be tuned to be aggressive (i.e., less exploration) without losing theoretical guarantees, a unique feature unavailable from existing bandit algorithms. Our numerical evaluation shows the effectiveness of MS$^+$.
• Abstract（参考訳）: the phd thesis of maillard (2013)は、$k$-armed bandit問題のランダム化アルゴリズムを示している。 筆者らがMaillard sample (MS)と呼ぶこのあまり知られていないアルゴリズムは、各アームをクローズドな形で選択する確率を計算する。 このようなメリットに動機づけられて、我々はmsを再検討し、漸近的最適性と$\sqrt{kt\log{t}}$ minimax regret bound where $t$ is the time horizon, これは標準漸近的最適ucbのパフォーマンスと一致することを示した。 次に、漸近的最適性を失うことなく、その最小値が$\sqrt{kt\log{k}}$となるms$^+$と呼ばれる変種を提案する。 ms$^+$は、既存のbanditアルゴリズムでは利用できないユニークな機能である理論的保証を失うことなく、アグレッシブであるように調整することもできる。 数値評価の結果,ms$^+$の有効性が示された。

関連論文リスト

• Minimum Empirical Divergence for Sub-Gaussian Linear Bandits [10.750348548547704]
  LinMEDは、アームサンプリング確率のクローズドフォーム計算を許容するランダム化アルゴリズムである。 我々の実証研究は、LinMEDが最先端のアルゴリズムと競合する性能を持っていることを示している。
  論文  参考訳（メタデータ） (2024-10-31T21:54:44Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Thompson Sampling for Unimodal Bandits [21.514495320038712]
  本稿では, 半順序の腕に対して期待される報酬が一様であるアンフンモダル・バンディットに対するトンプソンサンプリングアルゴリズムを提案する。 ガウスの報酬に対して、我々のアルゴリズムの後悔は$mathcalO(log T)$であり、標準的なトンプソンサンプリングアルゴリズムよりもはるかに優れている。
  論文  参考訳（メタデータ） (2021-06-15T14:40:34Z)
• Multinomial Logit Contextual Bandits: Provable Optimality and Practicality [15.533842336139063]
  パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。 本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。 本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
  論文  参考訳（メタデータ） (2021-03-25T15:42:25Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。