論文の概要: Replicable Bandits with UCB based Exploration

• arxiv url: http://arxiv.org/abs/2604.20024v1
• Date: Tue, 21 Apr 2026 22:04:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-23 15:36:10.871097
• Title: Replicable Bandits with UCB based Exploration
• Title（参考訳）: UCBを用いたリプリケータブル帯域探索
• Authors: Rohan Deb, Udaya Ghai, Karan Singh, Arindam Banerjee,
• Abstract要約: 我々は,UPB(Upper Confidence Bound)を用いたマルチアーム・バンディット(MAB)とリニア・バンディットの探索アルゴリズムについて検討した。 バンディットアルゴリズムが$$-replicable(英語版)であるとは、共用内部と独立の報酬実現を用いた2つの実行が、少なくとも1-$の確率で同じアクションシーケンスを生成することである。 我々はRepUCBが、後悔の$O!left(fracK2log2 T2sum_a:_a>0left(_a+fraclog(KTlog T)_に達することを示す。
• 参考スコア（独自算出の注目度）: 26.974139987497818
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study replicable algorithms for stochastic multi-armed bandits (MAB) and linear bandits with UCB (Upper Confidence Bound) based exploration. A bandit algorithm is $ρ$-replicable if two executions using shared internal randomness but independent reward realizations, produce the same action sequence with probability at least $1-ρ$. Prior work is primarily elimination-based and, in linear bandits with infinitely many actions, relies on discretization, leading to suboptimal dependence on the dimension $d$ and $ρ$. We develop optimistic alternatives for both settings. For stochastic multi-armed bandits, we propose RepUCB, a replicable batched UCB algorithm and show that it attains a regret $O\!\left(\frac{K^2\log^2 T}{ρ^2}\sum_{a:Δ_a>0}\left(Δ_a+\frac{\log(KT\log T)}{Δ_a}\right)\right)$. For stochastic linear bandits, we first introduce RepRidge, a replicable ridge regression estimator that satisfies both a confidence guarantee and a $ρ$-replicability guarantee. Beyond its role in our bandit algorithm, this estimator and its guarantees may also be of independent interest in other statistical estimation settings. We then use RepRidge to design RepLinUCB, a replicable optimistic algorithm for stochastic linear bandits, and show that its regret is bounded by $\widetilde{O}\!\big(\big(d+\frac{d^3}ρ\big)\sqrt{T}\big)$. This improves the best prior regret guarantee by a factor of $O(d/ρ)$, showing that our optimistic algorithm can substantially reduce the price of replicability.
• Abstract（参考訳）: 確率的マルチアームバンディット (MAB) と, UCB (Upper Confidence Bound) に基づく探索による線形バンディットのレプリカブルアルゴリズムについて検討した。 バンディットアルゴリズムが$ρ$-replicable(英語版)であるとは、共有内部ランダム性と独立報酬実現を用いた2つの実行が、少なくとも1-ρ$の確率で同じアクションシーケンスを生成することである。 以前の作業は、主に除去に基づくものであり、無限に多くの作用を持つ線形包帯において、離散化に依存し、$d$と$ρ$の次元に最適以下の依存をもたらす。 どちらの設定にも楽観的な代替手段を開発します。 確率的マルチアームバンディットに対して,レプリカブルバッチ UCB アルゴリズム RepUCB を提案する。 \left(\frac{K^2\log^2 T}{ρ^2}\sum_{a:Δ_a>0}\left(Δ_a+\frac{\log(KT\log T)}{Δ_a}\right)\right)$。 確率線形包帯に対して、まずRepRidgeを導入する。RepRidgeは、信頼性保証と$ρ$-replicability保証の両方を満たすレプリカブルリッジ回帰推定器である。 バンディットアルゴリズムにおけるその役割以外にも、この推定器とその保証は、他の統計的推定設定に対して独立した関心を持つ可能性がある。 次にRepRidgeを使って確率線形包帯のレプリケートな楽観的アルゴリズムRepLinUCBを設計し、その後悔が$\widetilde{O}\! \big(\big(d+\frac{d^3}ρ\big)\sqrt{T}\big)$。 これにより、O(d/ρ)$の係数で最優先の後悔の保証が向上し、我々の楽観的なアルゴリズムがレプリカ化のコストを大幅に削減できることが示される。

関連論文リスト

• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Replicability is Asymptotically Free in Multi-armed Bandits [41.86005698892541]
  我々は,アルゴリズムの動作シーケンスがデータセットに固有のランダム性の影響を受けないことを高い確率で保証する,レプリカブルなマルチアームバンディットアルゴリズムを考察する。 非複製の確率を制限するための原則的アプローチを提案する。
  論文  参考訳（メタデータ） (2024-02-12T03:31:34Z)
• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise [45.60098988395789]
  マルチアームバンディットのためのUCB型アルゴリズムを構築するための新しいアルゴリズムを提案する。 報酬の対称雑音の場合、$O(log TsqrtKTlog T)$ regret bound を $Oleft の代わりに達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-10T22:38:21Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• 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)
• Multi-armed Bandit Algorithm against Strategic Replication [5.235979896921492]
  我々は,各エージェントが一組のアームを登録する多腕バンディット問題を考慮し,各エージェントがそのアームを選択すると報酬を受け取る。 エージェントは、より多くの武器を複製で戦略的に送信し、バンディットアルゴリズムの探索と探索のバランスを悪用することで、より多くの報酬をもたらす可能性がある。 本稿では,複製の復号化と,最小限の累積後悔を実現するバンディットアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-23T07:38:44Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-14T00:41:26Z)

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

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