論文の概要: Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

• arxiv url: http://arxiv.org/abs/2608.11383v1
• Date: Tue, 11 Aug 2026 19:46:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-13 19:07:54.362528
• Title: Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints
• Title（参考訳）: Knapsack制約によるコンテキスト帯域の再最適化アルゴリズム
• Abstract要約: 我々は Knapsack を用いたコンテキスト帯域に対する新しいアルゴリズムについて検討した。 再最適化の利点を生かして,我々のアルゴリズムは平均で$O(frac(ln T)3T)$で,$T$は水平長であることを示す。
• 参考スコア（独自算出の注目度）: 3.2017121489002744
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study new algorithms for Contextual Bandits with Knapsack. In these problems, there are finitely many types of customers, products, and resources. Each product is made from a fixed combination of resources, and resources have finite capacity. A decision maker must assign each arriving customer one out of a set of multiple possible products. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function. We propose a natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms and apply re-optimization techniques. We show that by taking advantage of re-optimization, our algorithm achieves an average regret of $O(\frac{(\ln T)^3}{T})$ where $T$ is the horizon length. Our bound significantly reduces the $O(\frac{1}{\sqrt{T}})$ bound in the literature for closely related dynamic-pricing problems that are based on re-optimization.
• Abstract（参考訳）: 我々は Knapsack を用いたコンテキスト帯域に対する新しいアルゴリズムについて検討した。 これらの問題には、顧客、製品、リソースのタイプが有限である。 各製品は固定された資源の組み合わせで作られ、資源は有限の容量を持つ。 意思決定者は、到着した各顧客に対して、複数の可能な製品セットのうち1つを割り当てなければならない。 製品に顧客を割り当てるたびにランダムな報酬が発生し、それは顧客や製品の特徴の未知の線形関数に等しい。 本研究の目的は、平均報酬関数を共同で学習し、その報酬関数を知っている最適政策に対して、期待される収益損失を最小限に抑えるオンライン課題を行うことである。 本稿では,アルゴリズムのアッパー信頼境界(UCB)系列の自然かつ単純な拡張を提案し,再最適化手法を適用した。 再最適化の利点を生かして、我々のアルゴリズムは平均的後悔を$O(\frac{(\ln T)^3}{T})$で達成し、そこで$T$は地平線長であることを示す。 我々の境界は、再最適化に基づく密接に関連する動的価格問題に対する文献の$O(\frac{1}{\sqrt{T}})$境界を著しく減少させる。

関連論文リスト

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints [8.314956969778692]
  本研究では, 長期的予算制約を伴うオンライン学習問題を, 対戦環境において検討する。 この問題では、各ラウンド$t$で、学習者は凸集合からアクションを選択し、その後、相手がコスト関数を明らかにする。 提案手法は, 保証を改善した$textttAdversas$問題に対して, 効率的なソリューションを提供する。
  論文  参考訳（メタデータ） (2025-08-23T11:21:24Z)
• Online Linear Programming with Batching [18.989352151219336]
  オンライン線形プログラミング(OLP)をOmegaで研究する。 後悔によって測定されたように、意思決定を遅らせる能力は、より良い運用パフォーマンスをもたらすことが示されます。 提案されたアルゴリズムはすべて、最初のバッチと最後のバッチにのみ到着する顧客の決定を遅らせる。
  論文  参考訳（メタデータ） (2024-08-01T06:13:24Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation [41.460894569204065]
  線形文脈マルコフ決定過程(MDP)の遺残条件における生涯強化学習(RL)について検討する。 本稿では, UCB Lifelong Value Distillation (UCBlvd) と呼ばれるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T06:53:28Z)
• New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees [21.30065439295409]
  オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。 提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。 我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
  論文  参考訳（メタデータ） (2022-02-09T20:56:16Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm [50.50545326342971]
  複数の長期目標の非線形凹関数を最大化する問題を定式化する。 この問題に対してポリシー段階に基づくモデルフリーアルゴリズムを提案する。 提案アルゴリズムは,グローバルオプティマの$epsilon$以内に収束することが示されている。
  論文  参考訳（メタデータ） (2021-05-28T22:20:54Z)
• A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit [2.9998316151418107]
  我々は、意思決定者が消費者に製品のサブセットを提供する動的集合最適化問題を考える。 MNL(Multinomial Logit)モデルを用いて消費者選択行動のモデル化を行う。 後悔は$O(sqrtdT + kappa)$で束縛され、既存のメソッドよりもパフォーマンスが大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2020-11-28T00:20:36Z)
• 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)

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

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