論文の概要: Truly Adapting to Adversarial Constraints in Constrained MABs

• arxiv url: http://arxiv.org/abs/2602.14543v1
• Date: Mon, 16 Feb 2026 08:07:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 16:22:50.331575
• Title: Truly Adapting to Adversarial Constraints in Constrained MABs
• Title（参考訳）: 制約付きMABにおける逆制約への真対応
• Authors: Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti,
• Abstract要約: 本研究では,Emphmulti-armed bandit (MAB) 問題の制約付き変種について検討した。 本稿では,$widetildemathcalO(sqrtT+C)$ regretと$widetildemathcalO(sqrtT+C)$ positive violationを実現するアルゴリズムを提案する。 次に、損失に対して盗聴フィードバックのみが利用可能である場合に、これらの保証を拡張する方法を示す。
• 参考スコア（独自算出の注目度）: 33.41566575424402
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the constrained variant of the \emph{multi-armed bandit} (MAB) problem, in which the learner aims not only at minimizing the total loss incurred during the learning dynamic, but also at controlling the violation of multiple \emph{unknown} constraints, under both \emph{full} and \emph{bandit feedback}. We consider a non-stationary environment that subsumes both stochastic and adversarial models and where, at each round, both losses and constraints are drawn from distributions that may change arbitrarily over time. In such a setting, it is provably not possible to guarantee both sublinear regret and sublinear violation. Accordingly, prior work has mainly focused either on settings with stochastic constraints or on relaxing the benchmark with fully adversarial constraints (\emph{e.g.}, via competitive ratios with respect to the optimum). We provide the first algorithms that achieve optimal rates of regret and \emph{positive} constraint violation when the constraints are stochastic while the losses may vary arbitrarily, and that simultaneously yield guarantees that degrade smoothly with the degree of adversariality of the constraints. Specifically, under \emph{full feedback} we propose an algorithm attaining $\widetilde{\mathcal{O}}(\sqrt{T}+C)$ regret and $\widetilde{\mathcal{O}}(\sqrt{T}+C)$ {positive} violation, where $C$ quantifies the amount of non-stationarity in the constraints. We then show how to extend these guarantees when only bandit feedback is available for the losses. Finally, when \emph{bandit feedback} is available for the constraints, we design an algorithm achieving $\widetilde{\mathcal{O}}(\sqrt{T}+C)$ {positive} violation and $\widetilde{\mathcal{O}}(\sqrt{T}+C\sqrt{T})$ regret.
• Abstract（参考訳）: 本研究では,学習者に対して,学習中に発生する損失の総和を最小化するだけでなく,emph{full} と \emph{bandit feedback} の両条件の下で,複数の \emph{unknown} 制約の違反を制御することを目的とした,MAB問題(英語版)の制約付き変種について検討する。 確率モデルと逆数モデルの両方を仮定し、各ラウンドにおいて、損失と制約の両方を時間とともに任意に変化する分布から引き出す非定常環境を考える。 このような設定では、サブリニア後悔とサブリニア違反の両方を確実に保証することはできない。 したがって、事前の研究は主に確率的制約のある設定に焦点をあてるか、完全に逆の制約を持つベンチマークを緩和することに焦点を当てている (\emph{e g } 。 本稿では, 損失が任意に変化する一方, 制約が確率的である場合に, 後悔の最適率と「emph{ positive}」制約違反を達成し, 同時に, 制約の逆境の度合いと円滑に低下する保証を与えるアルゴリズムを提案する。 具体的には、emph{full feedback} の下で、$\widetilde{\mathcal{O}}(\sqrt{T}+C)$ regret と $\widetilde{\mathcal{O}}(\sqrt{T}+C)$ { positive} breach というアルゴリズムを提案する。 次に、損失に対して盗聴フィードバックのみが利用可能である場合に、これらの保証を拡張する方法を示す。 最後に、制約に対して \emph{bandit feedback} が利用できる場合、$\widetilde{\mathcal{O}}(\sqrt{T}+C)$ { positive} violation と $\widetilde{\mathcal{O}}(\sqrt{T}+C\sqrt{T})$ regret を達成するアルゴリズムを設計する。

関連論文リスト

• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
  本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。 バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
  論文  参考訳（メタデータ） (2026-02-02T18:17:34Z)
• Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints [33.41566575424402]
  本研究では, エンフォリンエピソード制約マルコフ決定過程(CMDP)について, 双方の制約下で検討した。 ストラディらによって導入された最先端のベスト・オブ・ボディーズ・アルゴリズムを大幅に改善する新しいアルゴリズムを提案する。 Slater の条件を使わずにサブリニア制約違反を保証し,インフン制約された最適値に対してサブリニア$alpha$-regret を保証する。
  論文  参考訳（メタデータ） (2025-09-24T13:38:32Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
  論文  参考訳（メタデータ） (2024-12-11T03:06:42Z)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
  本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。 最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。 この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
  論文  参考訳（メタデータ） (2024-05-10T16:22:33Z)
• Multi-point Feedback of Bandit Convex Optimization with Hard Constraints [1.8130068086063336]
  本研究では,学習者が損失関数の部分的情報に基づいて決定列を生成することを目的とした制約付き帯域凸最適化について検討する。 我々は、累積的テクスト制約違反を制約違反の指標として採用する。 我々のアルゴリズムは、凸損失関数と時間変化制約に対して、$O(d2Tmaxc,1-c)$ regret bounds と $O(d2T1-fracc2)$ cumulative hard constraint violation bounds を得る。
  論文  参考訳（メタデータ） (2023-10-17T02:43:22Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints [24.97580261894342]
  本稿では,長期的制約を伴うオンライン凸最適化について考察する。 新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
  論文  参考訳（メタデータ） (2021-06-09T15:18:06Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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