論文の概要: Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing
- arxiv url: http://arxiv.org/abs/2608.12831v2
- Date: Fri, 14 Aug 2026 03:53:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-17 13:59:16.2193
- Title: Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing
- Title（参考訳）: 高速A/B/nテスト:ツリー結合フィードバック共有による実効多目的比較
- Abstract要約: 木結合型A/Bテスト(TCAB: Tree-Coupled A/B Testing)は、任意の履歴に依存したコンテキスト帯域ポリシーのための、正確なフィードバック共有設計である。
すべてのポリシーは、意図的に依存しているにもかかわらず、スタンドアローンの有限水平軌道法則を正確に保持する。
報酬モデル評価、複数選択言語モデル評価、適応探索ポリシーの実験は、コスト-精度-フロンティアの大幅な改善を示している。
- 参考スコア（独自算出の注目度）: 5.922488908114023
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online platforms increasingly compare many adaptive decision policies---ranking systems, recommendation algorithms, pricing rules, and language-model agents---while each reward-bearing interaction can be costly or risky. A direct A/B/n design gives each of $J\ge 2$ policies its own horizon-$T$ trajectory and therefore uses $JT$ outcomes. We introduce Tree-Coupled A/B Testing (\TCAB), an exact feedback-sharing design for arbitrary history-dependent contextual-bandit policies. At each round, a predictable tree connects the current policy histories; every parent--child context--action law is maximally coupled, and one reward is shared within each component of matched tree edges. Every policy retains exactly its standalone finite-horizon trajectory law, even though the policies are deliberately dependent. If $D_{e,t}$ records a mismatch on tree edge $e$ at round $t$, the number of reward queries satisfies the pathwise identity $N(T)=T+\sum_{t,e}D_{e,t}$ and hence equals $T$ plus cumulative tree-edge total variation in expectation. This cost is conditionally optimal among exact edge-local designs on the selected tree, and a current-round minimum-spanning tree is myopically optimal among tree designs. For fixed $J$, sublinear pseudo-regret of every policy and almost-sure uniqueness of the oracle action imply $\mathbb{E}[N(T)]=T+o(T)$, versus $JT$ for independent runs. We also obtain finite-sample variance bounds for pairwise policy contrasts. Experiments on reward-model evaluation, multiple-choice language-model evaluation, and adaptive search policies demonstrate substantial improvements in the cost--precision frontier.
- Abstract（参考訳）: オンラインプラットフォームは、多くの適応的な意思決定ポリシー – グレードシステム、レコメンデーションアルゴリズム、価格ルール、言語モデルエージェント – を比較している。
直接のA/B/n設計では、各$J\ge 2$ポリシーが独自の水平線である-$T$軌道を与え、従って$JT$結果を使用する。
木結合型A/Bテスト (\TCAB) は、任意の履歴に依存したコンテキスト帯域ポリシーのための正確なフィードバック共有設計である。
各ラウンドにおいて、予測可能なツリーは現在のポリシー履歴を結び、親子関係のすべてのアクション法則は最大結合され、マッチしたツリーエッジの各コンポーネントで1つの報酬が共有される。
すべてのポリシーは、意図的に依存しているにもかかわらず、スタンドアローンの有限水平軌道法則を正確に保持する。
もし$D_{e,t}$がツリーエッジ$e$のミスマッチをラウンド$t$で記録するなら、報酬クエリの数はパスワイズIDである$N(T)=T+\sum_{t,e}D_{e,t}$を満たす。
このコストは、選択した木のエッジローカルな設計において条件的に最適であり、現在の最小スパンニングツリーは、木の設計においてミオプティカルに最適である。
固定$J$の場合、すべてのポリシーのサブ線形擬似回帰とオラクルアクションのほぼ確実な一意性は、独立ランに対して$\mathbb{E}[N(T)]=T+o(T)$であることを意味する。
また、ペアのポリシーコントラストに対する有限サンプル分散境界を得る。
報酬モデル評価、複数選択言語モデル評価、適応探索ポリシーの実験は、コスト-精度-フロンティアの大幅な改善を示している。
関連論文リスト
- The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。
ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。
我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
論文 参考訳（メタデータ） (2026-05-28T09:12:20Z) - Cast a Wider Net: Coordinated Pass@K Policy Optimization for Code Reasoning [8.638696735781478]
Coordinated Pass@$K$ Policyは、pass@$K$ジェネレーションを戦略に関する共同調査に変える。
APPS、CodeContests、LiveCodeBench-v6全体で、CPPOは、直接サンプリング、プランニングベースライン、プランナーのみのSFT、パス@$K$-orientedで、同じ$K=4$ソルバ回避予算で、pass@4$を改善している。
論文 参考訳（メタデータ） (2026-05-26T13:21:11Z) - From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。
文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。
本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
論文 参考訳（メタデータ） (2025-02-13T12:13:25Z) - Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time
Guarantees [3.5509551353363644]
ラベル付き例の挿入と削除の任意の順序に近似的な決定木を保持する最初のアルゴリズムを与える。
我々は$O!left(fracd, f(n)n operatornamenamepolyfrachepsilonright)$ Operations per updateを使って$epsilon$-approximate treeを維持する決定論的アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-02-08T11:02:58Z) - Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic
Shortest Path [106.37656068276902]
本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。
学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。
我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
論文 参考訳（メタデータ） (2022-10-10T18:34:32Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
我々は、ツリー検索をポリシー勾配に統合する最初のアプローチであるSoftTreeMaxを紹介します。
Atariでは、SoftTreeMaxが分散PPOと比較して、実行時のパフォーマンスを最大5倍向上させる。
論文 参考訳（メタデータ） (2022-09-28T09:55:47Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Coordinated Attacks against Contextual Bandits: Fundamental Limits and
Defense Mechanisms [75.17357040707347]
オンラインレコメンデーションシステムによってモチベーションされた我々は,文脈的包帯における最適政策の発見問題を提案する。
目標は、優れたユーザに対する報酬を可能な限り少ないユーザインタラクションで最大化するポリシーを、しっかりと学習することだ。
効率的なロバストな平均推定器を用いることで、$tildeO(min(S,A)cdot alpha/epsilon2)$ upper-boundを実現できることを示す。
論文 参考訳（メタデータ） (2022-01-30T01:45:13Z) - Characterizing Uniform Convergence in Offline Policy Evaluation via
model-based approach: Offline Learning, Task-Agnostic and Reward-Free [34.54294677335518]
オフライン政策評価問題における一様収束の統計的限界(一様OPEの略)とモデルに基づくMDP設定手法について検討する。
本研究の主な成果は,MPPの長期的最適政策に対する$tildeO(H2/d_mepsilon2)$のエピソード複雑性を確立することである。
論文 参考訳（メタデータ） (2021-05-13T01:36:34Z) - Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。
textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
論文 参考訳（メタデータ） (2020-10-12T17:51:19Z) - On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。
我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
論文 参考訳（メタデータ） (2020-08-20T03:42:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。