論文の概要: Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem
- arxiv url: http://arxiv.org/abs/2209.12013v1
- Date: Sat, 24 Sep 2022 14:02:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-27 15:21:32.484404
- Title: Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem
- Title(参考訳): Knapsacks問題における帯域の非単調資源利用
- Authors: Raunak Kumar and Robert Kleinberg
- Abstract要約: knapsacks (BwK) を用いたバンドは、不確実性の下でのシーケンシャルな意思決定に影響を及ぼすモデルである。
非単調な資源利用を可能にするBwK問題の自然な一般化を導入する。
- 参考スコア(独自算出の注目度): 6.227074051959886
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bandits with knapsacks (BwK) is an influential model of sequential
decision-making under uncertainty that incorporates resource consumption
constraints. In each round, the decision-maker observes an outcome consisting
of a reward and a vector of nonnegative resource consumptions, and the budget
of each resource is decremented by its consumption. In this paper we introduce
a natural generalization of the stochastic BwK problem that allows
non-monotonic resource utilization. In each round, the decision-maker observes
an outcome consisting of a reward and a vector of resource drifts that can be
positive, negative or zero, and the budget of each resource is incremented by
its drift. Our main result is a Markov decision process (MDP) policy that has
constant regret against a linear programming (LP) relaxation when the
decision-maker knows the true outcome distributions. We build upon this to
develop a learning algorithm that has logarithmic regret against the same LP
relaxation when the decision-maker does not know the true outcome
distributions. We also present a reduction from BwK to our model that shows our
regret bound matches existing results.
- Abstract(参考訳): knapsacks (BwK) は、資源消費制約を含む不確実性の下でのシーケンシャルな意思決定のモデルである。
各ラウンドにおいて、意思決定者は、報酬と非負のリソース消費のベクトルからなる結果を観察し、各リソースの予算はその消費によって減少する。
本稿では,非単調な資源利用を可能にする確率的BwK問題の自然な一般化を提案する。
各ラウンドにおいて、意思決定者は、正、負、ゼロの可能性のある報酬とリソースドリフトのベクトルからなる結果を観察し、各リソースの予算はそのドリフトによって増分される。
我々の主な成果はマルコフ決定プロセス(MDP)政策であり、意思決定者が真の結果分布を知っていれば、線形プログラミング(LP)緩和に対して常に後悔する。
これに基づいて、意思決定者が真の結果分布を知らない場合に、同じLP緩和に対して対数的後悔を持つ学習アルゴリズムを開発する。
また、BwK から BwK への還元をモデルに示し、既存の結果に一致した後悔の意を示す。
関連論文リスト
- Fair Resource Allocation in Weakly Coupled Markov Decision Processes [3.824858358548714]
マルコフ決定過程の弱結合としてモデル化された逐次的意思決定環境における資源配分について考察する。
我々は、従来の実用的(total-sum)目的ではなく、一般化されたジーニ関数を用いた公正性の定義を採用する。
論文 参考訳(メタデータ) (2024-11-14T20:40:55Z) - Value-Distributional Model-Based Reinforcement Learning [59.758009422067]
政策の長期的業績に関する不確実性の定量化は、シーケンシャルな意思決定タスクを解決するために重要である。
モデルに基づくベイズ強化学習の観点から問題を考察する。
本稿では,値分布関数を学習するモデルに基づくアルゴリズムであるEpicemic Quantile-Regression(EQR)を提案する。
論文 参考訳(メタデータ) (2023-08-12T14:59:19Z) - Bandits with Replenishable Knapsacks: the Best of both Worlds [26.786438972889208]
非単調な資源利用を可能にするBwKフレームワークの自然な一般化について検討する。
入力モデルの下で、我々のアルゴリズムはインスタンスに依存しない $tildeO(T1/2)$ regret bound を生成する。
論文 参考訳(メタデータ) (2023-06-14T12:34:00Z) - Policy Evaluation in Distributional LQR [70.63903506291383]
ランダムリターンの分布を閉形式で表現する。
この分布は有限個の確率変数で近似できることを示す。
近似回帰分布を用いて,リスク・アバースLQRに対するゼロ階ポリシー勾配アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-23T20:27:40Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-21T00:17:24Z) - Contextual Decision-Making with Knapsacks Beyond the Worst Case [5.65888994172721]
資源制約を伴う動的意思決定シナリオの枠組みについて検討する。
このフレームワークでは、エージェントがランダムな要求を観察すると、各ラウンドでアクションを選択する。
我々のアルゴリズムは最悪の場合であっても、ほぼ最適の$widetildeO(sqrtT)$ regretを維持していることを証明している。
論文 参考訳(メタデータ) (2022-11-25T08:21:50Z) - Non-stationary Bandits with Knapsacks [6.2006721306998065]
非定常環境におけるクナプサック(BwK)による包帯問題について検討する。
我々は、この問題の上下境界を導出するために、非定常対策を両方採用する。
論文 参考訳(メタデータ) (2022-05-25T01:22:36Z) - Universal Off-Policy Evaluation [64.02853483874334]
ユニバーサルオフ政治推定器(UnO)への第一歩を踏み出す
我々は, 平均, 分散, 分位数/中間数, 分位数範囲, cvar, および累積分布全体の推定と同時結合に uno を用いる。
論文 参考訳(メタデータ) (2021-04-26T18:54:31Z) - Stein Variational Model Predictive Control [130.60527864489168]
不確実性の下での意思決定は、現実の自律システムにとって極めて重要である。
モデル予測制御 (MPC) 法は, 複雑な分布を扱う場合, 適用範囲が限られている。
この枠組みが、挑戦的で非最適な制御問題における計画の成功に繋がることを示す。
論文 参考訳(メタデータ) (2020-11-15T22:36:59Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。
この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。
目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
論文 参考訳(メタデータ) (2020-07-01T14:24:58Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
我々はReLU回帰の根本的な問題を考察する。
目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
論文 参考訳(メタデータ) (2020-05-26T16:26:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。