論文の概要: Design Experiments to Compare Multi-armed Bandit Algorithms

• arxiv url: http://arxiv.org/abs/2603.05919v1
• Date: Fri, 06 Mar 2026 05:17:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-09 13:17:45.103302
• Title: Design Experiments to Compare Multi-armed Bandit Algorithms
• Title（参考訳）: マルチアーム帯域幅アルゴリズムの比較のための設計実験
• Authors: Huiling Meng, Ningyuan Chen, Xuefeng Gao,
• Abstract要約: オンラインプラットフォームは、UCBやトンプソン・サンプリングといったマルチアームのバンディットアルゴリズムを常に比較して、最高のパフォーマンスポリシーを選択する。 静的な処理のための標準的なA/Bテストとは異なり、$T$のユーザに対するバンディットアルゴリズムの各実行は、1つの依存した軌道のみを生成する。 本稿では,この問題に対する新しい実験設計として,Artificial Replay (AR)を提案する。
• 参考スコア（独自算出の注目度）: 6.741852800770004
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online platforms routinely compare multi-armed bandit algorithms, such as UCB and Thompson Sampling, to select the best-performing policy. Unlike standard A/B tests for static treatments, each run of a bandit algorithm over $T$ users produces only one dependent trajectory, because the algorithm's decisions depend on all past interactions. Reliable inference therefore demands many independent restarts of the algorithm, making experimentation costly and delaying deployment decisions. We propose Artificial Replay (AR) as a new experimental design for this problem. AR first runs one policy and records its trajectory. When the second policy is executed, it reuses a recorded reward whenever it selects an action the first policy already took, and queries the real environment only otherwise. We develop a new analytical framework for this design and prove three key properties of the resulting estimator: it is unbiased; it requires only $T + o(T)$ user interactions instead of $2T$ for a run of the treatment and control policies, nearly halving the experimental cost when both policies have sub-linear regret; and its variance grows sub-linearly in $T$, whereas the estimator from a naïve design has a linearly-growing variance. Numerical experiments with UCB, Thompson Sampling, and $ε$-greedy policies confirm these theoretical gains.
• Abstract（参考訳）: オンラインプラットフォームは、UPBやトンプソン・サンプリングといったマルチアームのバンディットアルゴリズムを常に比較して、最高のパフォーマンスポリシーを選択する。 静的な処理のための標準的なA/Bテストとは異なり、$T$以上のバンディットアルゴリズムの各実行は、アルゴリズムの判断が過去のすべてのインタラクションに依存するため、1つの依存した軌道のみを生成する。 したがって、信頼性の高い推論では、アルゴリズムの独立した再起動が要求されるため、実験はコストがかかり、デプロイメントの決定が遅れる。 本稿では,この問題に対する新しい実験設計として,Artificial Replay (AR)を提案する。 ARはまず1つのポリシーを実行し、その軌道を記録します。 第2のポリシが実行されると、最初のポリシがすでに実行したアクションを選択すると、記録された報酬を再利用し、実際の環境のみをクエリする。 我々は、この設計のための新しい分析フレームワークを開発し、結果として得られる推定器の3つの重要な特性を証明している: バイアスがない; 処理および制御ポリシーの実行に2Tドルではなく、わずか$T + o(T)$のユーザインタラクションしか必要とせず、両方のポリシーがサブ線形後悔を持つ場合の実験コストをほぼ半分にし、その分散は$T$でサブ線形に増加するが、ナイーブ設計からの推定器は線形に変化する分散を持つ。 UCB、トンプソンサンプリング、および$ε$-greedyポリシーによる数値実験は、これらの理論的な利得を裏付ける。

関連論文リスト

• Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits [6.402634424631123]
  ランダムなラウンドリングを持つ自然な有限水平LP更新ポリシーは、無限時間平均報酬問題において$O(log Nsqrt1/N)$Optimity gapを達成することを示す。 本研究は, 共分散性の概念を提唱し, 予測制御文学の手法を取り入れたものである。
  論文  参考訳（メタデータ） (2025-11-11T10:53:49Z)
• Oracle-Efficient Reinforcement Learning for Max Value Ensembles [7.404901768256101]
  大または無限の状態空間における強化学習(RL)は、理論上、実験的に困難である。 この作業では、$textitmax-following Policy$と競合することを目指しています。 我々の主な成果は、構成ポリシーのみにアクセスすると、最大フォローポリシーと競合する効率的なアルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-27T01:08:23Z)
• Policy Gradient with Active Importance Sampling [55.112959067035916]
  政策勾配法(PG法)はISの利点を大いに生かし、以前に収集したサンプルを効果的に再利用することができる。 しかし、ISは歴史的サンプルを再重み付けするための受動的ツールとしてRLに採用されている。 我々は、政策勾配のばらつきを減らすために、サンプルを収集する最良の行動ポリシーを模索する。
  論文  参考訳（メタデータ） (2024-05-09T09:08:09Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Online Resource Allocation with Average Budget Constraints [17.47923923731483]
  平均予算制約によるオンライン資源配分の問題点を考察する。 簡単なポリシーがOmega(sqrtT)$ regretを達成していることを示す。 予算安全バッファを組み込んだ新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2024-02-18T02:11:54Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [59.02170783023547]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Can Q-learning solve Multi Armed Bantids? [0.0]
  現在の強化学習アルゴリズムでは,マルチアーマッド・バンディット問題を解くことができないことを示す。 これはポリシー間の差異が原因であり、2つの問題を引き起こす。 本稿では,アダプティブ・シンメトリ・リワード・ノーミング(ASRN)手法を提案する。
  論文  参考訳（メタデータ） (2021-10-21T07:08:30Z)
• Differentiable Bandit Exploration [38.81737411000074]
  我々は、$mathcalP$からサンプルを使って未知のディストリビューション$mathcalP$についてそのようなポリシーを学ぶ。 我々のアプローチはメタラーニングの形式であり、その形式について強い仮定をすることなく$mathcalP$のプロパティを利用する。
  論文  参考訳（メタデータ） (2020-02-17T05:07:35Z)

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

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