論文の概要: Bandits with Anytime Knapsacks

• arxiv url: http://arxiv.org/abs/2501.18560v1
• Date: Thu, 30 Jan 2025 18:36:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-31 15:14:26.869906
• Title: Bandits with Anytime Knapsacks
• Title（参考訳）: 任意のクナップサックによるバンド
• Authors: Eray Can Elumar, Cem Tekin, Osman Yagan,
• Abstract要約: 我々は,腕の最適な混合を識別するために,上限値を用いたSUAKを提案する。 我々は、より単純なBwKフレームワークの下で以前の作業で確立された$O(K log T)$と同じ問題依存の後悔上限が得られることを示す。
• 参考スコア（独自算出の注目度）: 14.69261466438399
• License:
• Abstract: We consider bandits with anytime knapsacks (BwAK), a novel version of the BwK problem where there is an \textit{anytime} cost constraint instead of a total cost budget. This problem setting introduces additional complexities as it mandates adherence to the constraint throughout the decision-making process. We propose SUAK, an algorithm that utilizes upper confidence bounds to identify the optimal mixture of arms while maintaining a balance between exploration and exploitation. SUAK is an adaptive algorithm that strategically utilizes the available budget in each round in the decision-making process and skips a round when it is possible to violate the anytime cost constraint. In particular, SUAK slightly under-utilizes the available cost budget to reduce the need for skipping rounds. We show that SUAK attains the same problem-dependent regret upper bound of $ O(K \log T)$ established in prior work under the simpler BwK framework. Finally, we provide simulations to verify the utility of SUAK in practical settings.
• Abstract（参考訳）: 我々は,BwK問題の新しいバージョンであるknapsacks (BwAK) による盗賊について検討する。 この問題設定は、意思決定プロセス全体を通して制約への順守を義務付けることで、さらなる複雑さをもたらす。 探索と搾取のバランスを保ちながら、高信頼境界を利用して最適な腕の混合を識別するアルゴリズムSUAKを提案する。 SUAKは、意思決定プロセスにおいて各ラウンドで利用可能な予算を戦略的に活用し、いかなるコスト制約にも違反できる場合、ラウンドをスキップする適応アルゴリズムである。 特にSUAKは、ラウンドをスキップする必要性を減らすため、利用可能なコスト予算をわずかに過小評価している。 我々は、より単純なBwKフレームワークの下で以前の作業で確立された$O(K \log T)$と同じ問題依存の後悔上限が得られることを示す。 最後に,SuAKの実用性を検証するためのシミュレーションを行う。

関連論文リスト

• Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits [1.4732811715354452]
  我々は、各アームが選択時に異なるリソースを消費する、$Kの武器付きバンディット問題を考える。 我々はトンプソンサンプリングのようにランダム化される一連のアルゴリズムを提案するが、予算制約に関してより慎重に決定を最適化する。
  論文  参考訳（メタデータ） (2024-08-28T04:56:06Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Bandits with Replenishable Knapsacks: the Best of both Worlds [26.786438972889208]
  非単調な資源利用を可能にするBwKフレームワークの自然な一般化について検討する。 入力モデルの下で、我々のアルゴリズムはインスタンスに依存しない $tildeO(T1/2)$ regret bound を生成する。
  論文  参考訳（メタデータ） (2023-06-14T12:34:00Z)
• Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness [1.6741394365746018]
  我々は,各ラウンドにおいてスカラー報酬が得られ,ベクトル値のコストがかかる問題であるknapsacks[CBwK]のコンテキスト的帯域幅問題を考える。 予測段階更新に基づく二元的戦略を導入し,多元対数項まで$sqrtT$の総コスト制約を扱えるようにした。
  論文  参考訳（メタデータ） (2023-05-25T07:41:35Z)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。 提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
  論文  参考訳（メタデータ） (2023-01-31T03:49:00Z)
• 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)
• A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback [22.17503016665027]
  各アクションが未知の関節分布からランダムな報酬、コスト、ペナルティを返す問題を考える。 我々は、$tt LyOn$という新しい低複雑さアルゴリズムを提案し、$O(sqrtBlog B)$ regretと$O(log B/B)$ constraint-violationを達成することを証明した。 計算コストの低い$tt LyOn$は、Lyapunovをベースとしたアルゴリズム設計手法が制約付き帯域最適化問題の解決に有効であることを示唆している。
  論文  参考訳（メタデータ） (2021-06-09T16:12:07Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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