論文の概要: A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming

• arxiv url: http://arxiv.org/abs/2603.14673v1
• Date: Sun, 15 Mar 2026 23:59:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 16:19:35.958843
• Title: A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
• Title（参考訳）: 非定常オンライン線形計画法のための単サンプル多対数レグレット境界
• Authors: Haoran Xu, Owen Shen, Peter Glynn, Yinyu Ye, Patrick Jaillet,
• Abstract要約: 非定常オンライン線形計画法(OLP)について検討する。 OLPでは、$n$の注文は、独立だが必ずしも同一に分散されたランダムベクトルの列を形成する報酬と資源の消費のペアと共に順次届く。 本稿では,動的プログラミングの観点を,従来の静止環境において採用されていたデュアルベースフレームワークと統合した新しい再解法を提案する。
• 参考スコア（独自算出の注目度）: 29.531157410826825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study nonstationary Online Linear Programming (OLP), where $n$ orders arrive sequentially with reward-resource consumption pairs that form a sequence of independent, but not necessarily identically distributed, random vectors. At the beginning of the planning horizon, the decision-maker is provided with a resource endowment that is sufficient to fulfill a significant portion of the requests. The decision-maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to this resource endowment. We focus on the challenging single-sample setting, where only one sample from each of the $n$ distributions is available at the start of the planning horizon. We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of orders, we prove that our algorithm achieves $O((\log n)^2)$ regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.
• Abstract（参考訳）: 我々は、非定常オンライン線形計画法(OLP)について研究し、$n$の注文は、独立だが必ずしも同じ分布のランダムベクトルの列を形成する報酬-資源消費ペアで順次届く。 計画の開始時に、意思決定者は、要求のかなりの部分を満たすのに十分なリソースを提供する。 決定者は、各注文に対して即時かつ取り消し不能な受理又は拒否決定を行うことにより、このリソースの付与を受けることにより、予想される総報酬を最大化することを試みる。 計画の開始時点では、$n$のディストリビューションから1つのサンプルしか利用できない、挑戦的なシングルサンプル設定に重点を置いています。 本稿では,動的プログラミングの観点を,従来の静止環境において採用されていたデュアルベースフレームワークと統合した新しい再解法を提案する。 資源供給が順序数と線形にスケールする大規模資源体制において、我々のアルゴリズムが非定常分布列の幅広いクラスで$O((\log n)^2)$ regretを達成することを証明している。 以上の結果から, 環境変化やデータ可用性の最小化の下でも, 多言語的後悔は可能であり, 定常ALPとより不安定な実世界の資源配分問題とのギャップを埋めることが可能であることが示唆された。

関連論文リスト

• Non-Stationary Online Resource Allocation: Learning from a Single Sample [5.81028169940199]
  最低限のオフラインデータ要求で,非定常要求下でのオンラインリソース割り当てについて検討する。 本稿では,この問題をモジュラーコンポーネントに分解する,型依存型量子型メタ政治を提案する。
  論文  参考訳（メタデータ） (2026-02-20T10:07:35Z)
• Online Linear Programming with Replenishment [9.214452378957697]
  オンライン線形プログラミング(OLP)モデルについて検討し、在庫を事前に提供せず、補充プロセスを通じて徐々に到着する。 分散された不確実な補充の導入は、古典的なALPの構造を根本的に変える。 我々は,ALP文献で研究されている3つの主要な分布系について,新しいアルゴリズムと後悔の分析法を開発した。
  論文  参考訳（メタデータ） (2026-01-21T04:09:29Z)
• No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
  アクション選択の前に報酬とコストが観測される$(i)$オンラインリソース割当と、アクション選択後、完全なフィードバックや盗賊フィードバックの下で、リソース制限付きオンライン学習である$(ii)$オンラインリソース割当に焦点を当てた。 報酬とコスト分布が時間とともに任意に変化する場合、これらの設定でサブ線形後悔を達成することは不可能であることが知られている。 我々は、支出計画に従う基準線に対する半線形後悔を実現する一般的な(基本的)二重的手法を設計し、また、支出計画が予算のバランスの取れた配分を保証すると、アルゴリズムの性能が向上する。
  論文  参考訳（メタデータ） (2025-06-16T08:42:31Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。 提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-28T02:21:06Z)
• Solving Multistage Stochastic Linear Programming via Regularized Linear Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
  AdaSO(Adaptive least absolute shrinkage and selection operator)に基づく線形決定規則(LDR)の新しい正規化手法を提案する。 実験により、MSLPを解くために古典的な非正規化LDRを使用する場合、過度に適合する脅威は無視できないことが示された。 LHDP問題に対しては、非正規化ベンチマークと比較して、提案したフレームワークの次の利点を強調した。
  論文  参考訳（メタデータ） (2021-10-07T02:36:14Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。 意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。 この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
  論文  参考訳（メタデータ） (2020-12-13T04:47:37Z)
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems [7.433931244705934]
  本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。 様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。 我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
  論文  参考訳（メタデータ） (2020-11-18T18:39:17Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  本研究では, 資源制約を満たすため, エージェントを安定な集団状態へ誘導する新しい手法を提案する。 提案手法は,ゲームラグランジアンの拡張によるリソース負荷に基づく分散リソース価格設定手法である。
  論文  参考訳（メタデータ） (2020-10-21T10:11:17Z)

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

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