論文の概要: Improved Algorithms for Multi-period Multi-class Packing Problems with~Bandit~Feedback

• arxiv url: http://arxiv.org/abs/2301.13791v1
• Date: Tue, 31 Jan 2023 17:35:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-01 15:45:15.613906
• Title: Improved Algorithms for Multi-period Multi-class Packing Problems with~Bandit~Feedback
• Title（参考訳）: Bandit~Feedbackを用いた多周期マルチクラスパッケージ問題に対する改良アルゴリズム
• Authors: Wonyoung Kim, Garud Iyengar, Assaf Zeevi
• Abstract要約: LMMPには、特殊なケースとして、knapsackとオンライン収益管理を備えた線形コンテキストバンドレットが含まれている。 我々は,より高速な収束速度を保証し,その結果,そのような問題に対する後悔の少ない新しいより効率的な推定器を確立する。 本稿の数値実験は,本手法が文献の他のベンチマークよりも優れていることを明らかに示している。
• 参考スコア（独自算出の注目度）: 18.208834479445894
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the linear contextual multi-class multi-period packing problem~(LMMP) where the goal is to pack items such that the total vector of consumption is below a given budget vector and the total value is as large as possible. We consider the setting where the reward and the consumption vector associated with each action is a class-dependent linear function of the context, and the decision-maker receives bandit feedback. LMMP includes linear contextual bandits with knapsacks and online revenue management as special cases. We establish a new more efficient estimator which guarantees a faster convergence rate, and consequently, a lower regret in such problems. We propose a bandit policy that is a closed-form function of said estimated parameters. When the contexts are non-degenerate, the regret of the proposed policy is sublinear in the context dimension, the number of classes, and the time horizon~$T$ when the budget grows at least as $\sqrt{T}$. We also resolve an open problem posed in Agrawal & Devanur (2016), and extend the result to a multi-class setting. Our numerical experiments clearly demonstrate that the performance of our policy is superior to other benchmarks in the literature.
• Abstract（参考訳）: 我々は, 消費の合計ベクトルが与えられた予算ベクトル以下であり, 総値が可能な限り大きいようなアイテムをパックすることを目的として, 線形文脈的マルチ周期パッキング問題 (lmmp) を考える。 本稿では,各アクションに関連付けられた報酬と消費ベクトルがコンテキストのクラス依存線形関数であるような設定を考察し,意思決定者は帯域フィードバックを受け取る。 LMMPには、特殊なケースとして、knapsackとオンライン収益管理を備えた線形コンテキストバンドレットが含まれている。 我々は,より高速な収束速度を保証し,その結果,そのような問題に対する後悔の少ない新しいより効率的な推定器を確立する。 推定パラメータの閉形式関数であるバンドポリシーを提案する。 文脈が非退化の場合、提案されたポリシーの後悔は、少なくとも予算が$\sqrt{T}$として増加するとき、文脈次元、クラス数、および時間地平線~$T$のサブ線形である。 また、Agrawal & Devanur (2016) で提起されたオープンな問題を解決し、結果をマルチクラス設定に拡張する。 数値実験により,我々の方針の性能が文献の他のベンチマークよりも優れていることが明らかとなった。

関連論文リスト

• Information Capacity Regret Bounds for Bandits with Mediator Feedback [55.269551124587224]
  我々は,政策セットの複雑さに対する情報理論尺度として,政策セットの容量を導入する。 古典的なEXP4アルゴリズムを採用することで、ポリシーセットの容量に応じて、新たな後悔の限界を提供する。 ポリシーセットファミリの選択については、キャパシティと同じようなスケールで、ほぼ整合性の低い境界を証明します。
  論文  参考訳（メタデータ） (2024-02-15T19:18:47Z)
• 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)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。 提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
  論文  参考訳（メタデータ） (2023-01-31T03:49:00Z)
• Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits [18.971564419292893]
  我々は、$O(sqrtdTlog T)$ regret boundで、$d$は文脈の次元、$T$は時間地平線であるような線形文脈的帯域幅アルゴリズムを提案する。 提案アルゴリズムは,探索を明示的ランダム化により埋め込んだ新しい推定器を備える。
  論文  参考訳（メタデータ） (2022-06-11T02:43:17Z)
• Variational Bayesian Optimistic Sampling [43.130465039780084]
  エージェントが探索と搾取のバランスをとる必要があるオンラインシーケンシャルな意思決定問題を考える。 我々は、多腕バンディットの場合、トンプソンサンプリングポリシーを含むベイズ楽観的な政策の集合を導出する。 楽観的な集合におけるポリシーを生成するアルゴリズムは、$T$ラウンド後の$A$アクションの問題に対して$tilde O(sqrtAT)$ Bayesian regretを楽しんでいることが示される。
  論文  参考訳（メタデータ） (2021-10-29T11:28:29Z)
• Dynamic Planning and Learning under Recovering Rewards [18.829837839926956]
  我々は「純粋周期ポリシー」のクラスの性能保証を提案し、構築し、証明する。 私たちのフレームワークとポリシー設計は、他のオフライン計画およびオンライン学習アプリケーションに適応する可能性がある。
  論文  参考訳（メタデータ） (2021-06-28T15:40:07Z)
• Off-Policy Evaluation of Slate Policies under Bayes Risk [70.10677881866047]
  スレートのスロット上でロギングポリシーが因子化される典型的なケースにおいて、スレート帯のオフポリシ評価の問題について検討する。 PIによるリスク改善はスロット数とともに線形に増加し、スロットレベルの分岐の集合の算術平均と調和平均とのギャップによって線形に増加することを示す。
  論文  参考訳（メタデータ） (2021-01-05T20:07:56Z)
• Policy Optimization as Online Learning with Mediator Feedback [46.845765216238135]
  ポリシー最適化(PO)は、継続的制御タスクに対処するための広く使われているアプローチである。 本稿では、政策分野におけるオンライン学習問題としてpoを枠組みとする仲介者フィードバックの概念を紹介する。 本稿では,再帰的最小化のために,RIST (Multiple Importance Smpling with Truncation) を用いたアルゴリズム RANDomized-Exploration Policy Optimization を提案する。
  論文  参考訳（メタデータ） (2020-12-15T11:34:29Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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