論文の概要: Contextual Decision-Making with Knapsacks Beyond the Worst Case
- arxiv url: http://arxiv.org/abs/2211.13952v2
- Date: Wed, 18 Dec 2024 05:29:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-19 13:23:56.738085
- Title: Contextual Decision-Making with Knapsacks Beyond the Worst Case
- Title（参考訳）: クナプサックによる文脈決定-最悪の場合を超えて-
- Authors: Zhaohua Chen, Rui Ai, Mingwei Yang, Yuqi Pan, Chang Wang, Xiaotie Deng,
- Abstract要約: 資源制約を伴う動的意思決定シナリオの枠組みについて検討する。
このフレームワークでは、エージェントがランダムな要求を観察すると、各ラウンドでアクションを選択する。
我々のアルゴリズムは最悪の場合であっても、ほぼ最適の$widetildeO(sqrtT)$ regretを維持していることを証明している。
- 参考スコア（独自算出の注目度）: 5.65888994172721
- License:
- Abstract: We study the framework of a dynamic decision-making scenario with resource constraints. In this framework, an agent, whose target is to maximize the total reward under the initial inventory, selects an action in each round upon observing a random request, leading to a reward and resource consumptions that are further associated with an unknown random external factor. While previous research has already established an $\widetilde{O}(\sqrt{T})$ worst-case regret for this problem, this work offers two results that go beyond the worst-case perspective: one for the worst-case gap between benchmarks and another for logarithmic regret rates. We first show that an $\Omega(\sqrt{T})$ distance between the commonly used fluid benchmark and the online optimum is unavoidable when the former has a degenerate optimal solution. On the algorithmic side, we merge the re-solving heuristic with distribution estimation skills and propose an algorithm that achieves an $\widetilde{O}(1)$ regret as long as the fluid LP has a unique and non-degenerate solution. Furthermore, we prove that our algorithm maintains a near-optimal $\widetilde{O}(\sqrt{T})$ regret even in the worst cases and extend these results to the setting where the request and external factor are continuous. Regarding information structure, our regret results are obtained under two feedback models, respectively, where the algorithm accesses the external factor at the end of each round and at the end of a round only when a non-null action is executed.
- Abstract（参考訳）: 資源制約を伴う動的意思決定シナリオの枠組みについて検討する。
この枠組みでは、初期在庫の総報酬を最大化することを目的としたエージェントが、ランダムな要求を観察してラウンド毎にアクションを選択し、未知のランダムな外部要因にさらに関連付けられた報酬とリソース消費をもたらす。
これまでの研究では、この問題に対して$\widetilde{O}(\sqrt{T})$ worst-case regretをすでに確立しているが、この研究は最悪のケースの視点を超えた2つの結果を提供している。
最初に、よく使われる流体ベンチマークとオンライン最適度の間の$\Omega(\sqrt{T})$距離は、前者が退化最適解を持つ場合、避けられないことを示す。
アルゴリズム側では、再解ヒューリスティックと分布推定スキルを融合し、流体LPが一意かつ非退化解を持つ限り、$\widetilde{O}(1)$ regretを達成するアルゴリズムを提案する。
さらに,我々のアルゴリズムは,最悪の場合であっても,ほぼ最適の$\widetilde{O}(\sqrt{T})$後悔を保ち,これらの結果を要求と外部因子が連続的な設定にまで拡張する。
情報構造に関しては,各ラウンドの終了時に,ラウンドの終了時にのみ,ラウンドの終了時に,アルゴリズムが外部要因にアクセスするという2つのフィードバックモデルに基づいて,後悔の結果が得られた。
関連論文リスト
- Online Fair Allocation of Perishable Resources [1.4952056744888913]
我々は、標準オンラインフェアアロケーション問題の事実上の動機付け型を考察する。
意思決定者は、一定回数のラウンドを割り当てるために、パーシシブルなリソースの予算を持っている。
目標は、うらやましいほど効率的で効率的なアロケーションのシーケンスを構築することです。
論文 参考訳（メタデータ） (2024-06-04T15:14:10Z) - Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring [41.20252349191698]
部分的な監視は、限られたフィードバックを伴うオンライン意思決定問題の一般的なフレームワークである。
ハイブリッド正規化器を用いたExOの新しいフレームワークと解析法を提案する。
特に、$O(sum_a neq a*)$で、$k$、$m$、$T$はアクション、観察、ラウンドの数である。
論文 参考訳（メタデータ） (2024-02-13T09:34:22Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - 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) - 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) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Algorithmic Challenges in Ensuring Fairness at the Time of Decision [6.228560624452748]
社会的文脈におけるアルゴリズムによる意思決定は、帯域幅フィードバックの下で最適化される。
最近の訴訟は、アルゴリズムによる価格設定の慣行を展開している企業を非難している。
凸最適化の文脈において、遠心自由というよく研究された公正性の概念を導入する。
論文 参考訳（メタデータ） (2021-03-16T19:06:28Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳（メタデータ） (2020-07-13T16:30:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。