論文の概要: Best-of-Both Worlds for linear contextual bandits with paid observations
- arxiv url: http://arxiv.org/abs/2510.07424v1
- Date: Wed, 08 Oct 2025 18:23:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-10 17:54:14.657777
- Title: Best-of-Both Worlds for linear contextual bandits with paid observations
- Title（参考訳）: 有給観測による線形文脈帯域に対するBest-of-Both Worlds
- Authors: Nathan Boyer, Dorian Baudry, Patrick Rebeschini,
- Abstract要約: 本稿では,この問題に対する計算効率の良いBest-of-Both-Worldsアルゴリズムを提案する。
また, 逆数設定では$Theta(T2/3)$のミニマックス最適後悔を達成し, 複数対数的後悔を(破損した)レジームで保証することを示した。
- 参考スコア（独自算出の注目度）: 16.13456643813766
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of linear contextual bandits with paid observations, where at each round the learner selects an action in order to minimize its loss in a given context, and can then decide to pay a fixed cost to observe the loss of any arm. Building on the Follow-the-Regularized-Leader framework with efficient estimators via Matrix Geometric Resampling, we introduce a computationally efficient Best-of-Both-Worlds (BOBW) algorithm for this problem. We show that it achieves the minimax-optimal regret of $\Theta(T^{2/3})$ in adversarial settings, while guaranteeing poly-logarithmic regret in (corrupted) stochastic regimes. Our approach builds on the framework from \cite{BOBWhardproblems} to design BOBW algorithms for ``hard problem'', using analysis techniques tailored for the setting that we consider.
- Abstract（参考訳）: そこで,各ラウンドにおいて学習者が与えられたコンテキストにおける損失を最小限に抑えるために行動を選択し,任意のアームの損失を観測するために固定費用を支払うことを決定できる。
行列幾何サンプリングによる効率的な推定器を用いたFollow-the-Regularized-Leaderフレームワーク上に構築し,この問題に対する計算効率の良いBest-of-Both-Worlds(BOBW)アルゴリズムを提案する。
また, 確率的条件下では, 反逆的条件下では$\Theta(T^{2/3})$のミニマックス最適後悔を達成でき, 確率的条件下では多対数的後悔を保証できることを示した。
提案手法は,BOBWhardproblems} から '`hard problem'' に対して BOBW アルゴリズムを設計するフレームワーク上に構築されている。
関連論文リスト
- Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration [6.287267171078442]
ニューラルネットワークを利用して非線形ユーティリティ関数を近似する分散認識アルゴリズムを提案する。
十分広いニューラルネットワークに対して,我々のアルゴリズムが次数$bigollt(d sqrtsum_t=1T sigma_t2 + sqrtdTrt)のサブ線形累積平均後悔を達成できることを示す理論的保証を確立する。
論文 参考訳（メタデータ） (2025-06-02T01:58:48Z) - Influential Bandits: Pulling an Arm May Change the Environment [44.71145269686588]
現実世界のアプリケーションは、しばしば非定常環境と武器間の相互依存を含む。
本稿では,未知の,対称な正の半定値相互作用行列による腕間相互作用をモデル化する,影響力のあるバンドイット問題を提案する。
我々は,損失ダイナミクスの構造に合わせて,低信頼境界(LCB)推定器に基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-11T02:05:51Z) - High-dimensional Linear Bandits with Knapsacks [7.8856737627153874]
本研究では,スパース推定をオンラインで行うハードしきい値アルゴリズムのオンライン版を開発する。
以下の構造的仮定のいずれかが、よりシャープな後悔境界である$tildeO(s_0 sqrtT)$に対して十分であることを示す。
副産物として、クナップサック制約を伴わない高次元のコンテキスト帯域に我々のフレームワークを適用することで、データポーラとデータリッチレジームの両方において最適な後悔率を回復する。
論文 参考訳（メタデータ） (2023-11-02T15:40:33Z) - Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear
Contextual Bandits and Markov Decision Processes [59.61248760134937]
本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。
提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。
本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
論文 参考訳（メタデータ） (2022-12-12T15:04:56Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳（メタデータ） (2020-11-05T05:16:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。