論文の概要: On the Re-Solving Heuristic for (Binary) Contextual Bandits with Knapsacks

• arxiv url: http://arxiv.org/abs/2211.13952v1
• Date: Fri, 25 Nov 2022 08:21:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-28 17:49:57.230606
• Title: On the Re-Solving Heuristic for (Binary) Contextual Bandits with Knapsacks
• Title（参考訳）: ナップサックを用いた(バイナリ)コンテクストバンディットの解法ヒューリスティックについて
• Authors: Rui Ai, Zhaohua Chen, Xiaotie Deng, Yuqi Pan, Chang Wang and Mingwei Yang
• Abstract要約: 我々は、knapsacks (CBWK) を用いた文脈的包帯問題を考える。 本研究は,収益管理に成功している再解決と,この問題を解決するための分配推定手法を組み合わせたものである。 我々のアルゴリズムは流体ベンチマークに対して$widetilde O(Talpha_u + Talpha_v + T1/2)$ regretを得られることを示す。
• 参考スコア（独自算出の注目度）: 4.2139857669184
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the problem of (binary) contextual bandits with knapsacks (CBwK), the agent receives an i.i.d. context in each of the $T$ rounds and chooses an action, resulting in a random reward and a random consumption of resources that are related to an i.i.d. external factor. The agent's goal is to maximize the accumulated reward under the initial resource constraints. In this work, we combine the re-solving heuristic, which proved successful in revenue management, with distribution estimation techniques to solve this problem. We consider two different information feedback models, with full and partial information, which vary in the difficulty of getting a sample of the external factor. Under both information feedback settings, we achieve two-way results: (1) For general problems, we show that our algorithm gets an $\widetilde O(T^{\alpha_u} + T^{\alpha_v} + T^{1/2})$ regret against the fluid benchmark. Here, $\alpha_u$ and $\alpha_v$ reflect the complexity of the context and external factor distributions, respectively. This result is comparable to existing results. (2) When the fluid problem is linear programming with a unique and non-degenerate optimal solution, our algorithm leads to an $\widetilde O(1)$ regret. To the best of our knowledge, this is the first $\widetilde O(1)$ regret result in the CBwK problem regardless of information feedback models. We further use numerical experiments to verify our results.
• Abstract（参考訳）: knapsacks (CBwK) による文脈的包帯の問題では、エージェントは$T$ラウンドのそれぞれの i.d.コンテキストを受け取り、アクションを選択し、ランダムな報酬と、i.d.外部要因に関連するリソースのランダムな消費をもたらす。 エージェントの目標は、初期リソース制約の下で蓄積された報酬を最大化することである。 本研究では,収益管理に成功している再解決ヒューリスティックと,この問題を解決するための分布推定手法を組み合わせる。 我々は,外部要因のサンプル取得の困難さが異なる2つの情報フィードバックモデルについて検討する。 1)一般的な問題に対して,我々のアルゴリズムは流体ベンチマークに対して,$\widetilde O(T^{\alpha_u} + T^{\alpha_v} + T^{1/2})$の後悔を与えることを示す。 ここで、$\alpha_u$ と $\alpha_v$ はそれぞれコンテキストの複雑さと外部因子分布を反映している。 この結果は既存の結果に匹敵する。 (2) 流体問題は一意で非退化の最適解を持つ線形計画法であるとき、アルゴリズムは$\widetilde o(1)$ regretとなる。 私たちの知る限りでは、これは情報フィードバックモデルによらずcbwk問題を引き起こした最初の$\widetilde o(1)$ regretである。 我々はさらに数値実験を用いて結果を検証する。

関連論文リスト

• 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)

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

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