論文の概要: Satisficing Regret Minimization in Bandits with Knapsacks

• arxiv url: http://arxiv.org/abs/2610.39321v1
• Date: Thu, 29 Oct 2026 04:06:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.457322
• Title: Satisficing Regret Minimization in Bandits with Knapsacks
• Title（参考訳）: クナップサックによるバンドの満足度最小化
• Abstract要約: Knapsacks (BwK) による包帯の後悔の満足度について検討した。 そこで本研究では,BwK学習オラクルアルゴリズムを用いたアルゴリズムテンプレートを提案する。 我々の後悔分析は、LP-双対の議論に支えられ、SELECTwKが満足のいく政策が存在する場合に、常に満足のいく後悔を達成できることを証明している。
• 参考スコア（独自算出の注目度）: 12.695396362340347
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study satisficing regret minimization in bandits with knapsacks (BwK), where a learner sequentially selects randomized policies, i.e., distributions over arms, to obtain mean rewards above a satisficing threshold as frequently as possible while respecting finite resource budgets. The performance is measured by satisficing regret, the cumulative deficits of the selected policies' mean rewards below this threshold. Resource constraints introduce two difficulties: an algorithm can incur linear satisficing regret even with small standard regret as deficits to the threshold cannot be compensated, and random consumption can cause early resource depletion even when policies are feasible in expectation. To address these challenges, we propose SELECTwK, a general algorithmic template that uses a BwK learning oracle algorithm with sub-linear expected (standard) regret upper bound to search for and test candidate satisficing policies (i.e., policies whose mean rewards exceed satisficing threshold and whose expected resource consumption is feasible over the time horizon). Our regret analysis, supported by an LP-duality argument, establishes that SELECTwK attains constant expected satisficing regret when a satisficing policy exists. We further introduce a stronger regret condition that bounds the expected sum of positive reward deficits to the optimal one at each time step, under which SELECTwK achieves a sharper constant bound together with a sub-linear bound in the time horizon. As a complement, SELECTwK still preserves the oracle's sub-linear expected standard regret bound if the satisficing threshold is unattainable. Finally, we establish the oracle conditions and corresponding satisficing regret bound for existing finite-armed BwK and dynamic pricing algorithms, and conduct numerical experiments on dynamic pricing with limited inventory to demonstrate the empirical performance of SELECTwK.
• Abstract（参考訳）: そこでは,学習者がランダム化されたポリシー,すなわち武器の分布を連続的に選択し,限られた資源予算を尊重しながら,満足度閾値を超える平均報酬を得る。 パフォーマンスは、後悔、選択された政策の平均報酬の累積的赤字をこのしきい値以下に満たすことで測定される。 リソース制約は2つの困難を生じさせる: アルゴリズムは、しきい値の欠陥を補うことができないため、小さな標準的後悔であっても、線形に満足する後悔を引き起こすことができ、ランダムな消費は、期待された政策が実現可能であったとしても、早期に資源の枯渇を引き起こす。 これらの課題に対処するために、SELECTwKを提案する。これは、BwK学習オラクルアルゴリズムとサブ線形(標準)後悔の上界を用いて、候補充足ポリシー(すなわち、平均報酬が満足しきい値を超え、リソース消費が時間的地平線上で実現可能なポリシー)を探索し、テストする一般的なアルゴリズムテンプレートである。 我々の後悔分析は、LP-双対の議論に支えられ、SELECTwKが満足のいく政策が存在する場合に、常に満足のいく後悔を達成できることを証明している。 さらに、SELECTwKが時間軸のサブ線形境界とともによりシャープな定数を達成し、各時間ステップで正の報酬損失の期待和を最適値にバウンドする強い後悔条件を導入する。 補足として、SELECTwKは、満足しきい値が達成できない場合、オラクルのサブ線形予測された標準後悔境界を引き続き保持する。 最後に,既存の有限武装型BwKと動的価格アルゴリズムに対するオラクル条件とそれに対応する後悔条件を確立し,SELECTwKの実証性能を示すために,在庫限定による動的価格設定に関する数値実験を行った。

関連論文リスト

• Optimistic Feasible Search for Closed-Loop Fair Threshold Decision-Making [0.0]
  バンディットフィードバックからの1次元しきい値ポリシーのオンライン学習について検討する。 我々は,報酬と制約残差に対する信頼境界を維持する単純なグリッドベース手法であるOptimistic Feasible Search (OFS)を提案する。
  論文  参考訳（メタデータ） (2025-12-26T10:44:40Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  バッチ二分決定における近似的後続確率を用いた余剰リスクの定量化を行う。 我々は、再校正のみが後悔のほとんどに対処する体制と、後悔が集団的損失に支配される体制を識別する。 NLP実験では、これらの量によって、より高度なポストトレーニングの期待値が運用コストに値するかどうかが分かる。
  論文  参考訳（メタデータ） (2025-03-23T10:52:36Z)
• Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution [5.03122566946086]
  本稿では,SampLing と LowEr Confidence bound Testing を用いて,Regret Minimization を満足するアルゴリズムテンプレートを提案する。 本報告では,SELECT-LITEを導入し,軽快な後悔分布と,実現不可能なケースでは一定の満足な後悔と,実現不可能なケースではサブ線形(標準)の後悔を実現する。 以上の結果から, 常に期待される満足な後悔と, 満足な後悔の分布の相違が明らかとなった。
  論文  参考訳（メタデータ） (2024-06-10T21:15:28Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。 我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。 本稿では,リスク・サーキングとリスク・アバース・ポリシー最適化のいずれにも適用可能な汎用ポリシー最適化アルゴリズムQ-Uncertainty Soft Actor-Critic (QU-SAC)を導入する。
  論文  参考訳（メタデータ） (2023-12-07T15:55:58Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)

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

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