論文の概要: Online Linear Programming with Batching
- arxiv url: http://arxiv.org/abs/2408.00310v1
- Date: Thu, 1 Aug 2024 06:13:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-04 21:35:40.860412
- Title: Online Linear Programming with Batching
- Title（参考訳）: バッチによるオンライン線形プログラミング
- Authors: Haoran Xu, Peter W. Glynn, Yinyu Ye,
- Abstract要約: オンライン線形プログラミング(OLP)をOmegaで研究する。
後悔によって測定されたように、意思決定を遅らせる能力は、より良い運用パフォーマンスをもたらすことが示されます。
提案されたアルゴリズムはすべて、最初のバッチと最後のバッチにのみ到着する顧客の決定を遅らせる。
- 参考スコア（独自算出の注目度）: 18.989352151219336
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study Online Linear Programming (OLP) with batching. The planning horizon is cut into $K$ batches, and the decisions on customers arriving within a batch can be delayed to the end of their associated batch. Compared with OLP without batching, the ability to delay decisions brings better operational performance, as measured by regret. Two research questions of interest are: (1) What is a lower bound of the regret as a function of $K$? (2) What algorithms can achieve the regret lower bound? These questions have been analyzed in the literature when the distribution of the reward and the resource consumption of the customers have finite support. By contrast, this paper analyzes these questions when the conditional distribution of the reward given the resource consumption is continuous, and we show the answers are different under this setting. When there is only a single type of resource and the decision maker knows the total number of customers, we propose an algorithm with a $O(\log K)$ regret upper bound and provide a $\Omega(\log K)$ regret lower bound. We also propose algorithms with $O(\log K)$ regret upper bound for the setting in which there are multiple types of resource and the setting in which customers arrive following a Poisson process. All these regret upper and lower bounds are independent of the length of the planning horizon, and all the proposed algorithms delay decisions on customers arriving in only the first and the last batch. We also take customer impatience into consideration and establish a way of selecting an appropriate batch size.
- Abstract（参考訳）: オンライン線形プログラミング(OLP)をバッチ処理で研究する。
計画の地平線はK$バッチにカットされ、バッチ内に到着する顧客の決定は、関連するバッチの終了まで遅らせることができる。
バッチ処理なしでのOPPと比較して、決定を遅らせる能力は、後悔によって測定されるように、より良い運用パフォーマンスをもたらす。
興味のある2つの研究質問は以下の通りである: (1) 後悔の下位境界は$K$の関数である。
2) 後悔の少ない境界を達成できるアルゴリズムは何か?
これらの質問は、顧客からの報酬の分配とリソース消費が有限である場合に、文献で分析されている。
これとは対照的に,資源消費に対する報酬の条件分布が連続している場合の質問を解析し,この条件下での回答が異なることを示す。
一種類のリソースしか存在せず、意思決定者が総顧客数を知っている場合、我々は、$O(\log K)$後悔の上限付きアルゴリズムを提案し、$Omega(\log K)$後悔下限付きアルゴリズムを提供する。
また,複数種類のリソースが存在する設定や,Poissonプロセスの後に顧客が到着する設定に対して,$O(\log K)$残念な上限を持つアルゴリズムを提案する。
これらの残念な上限と下限は計画の地平線の長さとは無関係であり、提案されたアルゴリズムはすべて、最初のバッチと最後のバッチにのみ到着する顧客の決定を遅らせる。
また、顧客の不注意を考慮に入れ、適切なバッチサイズを選択する方法を確立します。
関連論文リスト
- Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Learning to Order for Inventory Systems with Lost Sales and Uncertain
Supplies [21.690446677016247]
我々は, 在庫管理システムを, 計画的地平線上でのリードタイム$L$とみなし, 供給は不確実であり, 注文量の関数である。
提案アルゴリズムは,O(L+sqrtT)$が$Lgeqlog(T)$である場合に,そのアルゴリズムのコストと,O(L+sqrtT)$に対する最適ポリシーとの相違(英語版)を生じることを示す。
論文 参考訳（メタデータ） (2022-07-10T22:11:32Z) - Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。
この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
論文 参考訳（メタデータ） (2022-05-16T15:47:41Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - 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) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳（メタデータ） (2020-10-12T20:53:52Z) - An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。
T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
論文 参考訳（メタデータ） (2020-10-05T07:08:26Z) - Continuous-Time Multi-Armed Bandits with Controlled Restarts [32.63624728528415]
時間制約決定過程に対する再起動制御による帯域幅問題について検討する。
特に、各決定がランダムな完了時間を要し、最後にランダムで相関した報酬が得られるような帯域設定を考える。
我々は,再起動戦略の有限かつ連続的な行動空間において,$O(log(tau))$と$O(sqrttaulog(tau))$後悔を用いて効率的なオンライン学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-30T19:50:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。