論文の概要: Online Resource Allocation under Horizon Uncertainty

• arxiv url: http://arxiv.org/abs/2206.13606v1
• Date: Mon, 27 Jun 2022 19:54:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-29 14:33:40.311130
• Title: Online Resource Allocation under Horizon Uncertainty
• Title（参考訳）: 水平不確実性下におけるオンライン資源配分
• Authors: Santiago Balseiro, Christian Kroer, Rachitesh Kumar
• Abstract要約: 収益管理やオンライン広告では、需要の変動やユーザートラフィックの強度のためにリクエスト数が大きく変化する可能性がある。 既知の水平配置とは対照的に、地平線の不確実性に依存しない一定の競合比を達成するアルゴリズムは存在しない。 我々のアルゴリズムは、地平線不確実性が大きくなると、その競合比が最適な成長率に達するという意味で、ほぼ最適である。
• 参考スコア（独自算出の注目度）: 27.21119630468227
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic online resource allocation: a decision maker needs to allocate limited resources to stochastically-generated sequentially-arriving requests in order to maximize reward. Motivated by practice, we consider a data-driven setting in which requests are drawn independently from a distribution that is unknown to the decision maker. Online resource allocation and its special cases have been studied extensively in the past, but these previous results crucially and universally rely on a practically-untenable assumption: the total number of requests (the horizon) is known to the decision maker in advance. In many applications, such as revenue management and online advertising, the number of requests can vary widely because of fluctuations in demand or user traffic intensity. In this work, we develop online algorithms that are robust to horizon uncertainty. In sharp contrast to the known-horizon setting, we show that no algorithm can achieve a constant asymptotic competitive ratio that is independent of the horizon uncertainty. We then introduce a novel algorithm that combines dual mirror descent with a carefully-chosen target consumption sequence and prove that it achieves a bounded competitive ratio. Our algorithm is near-optimal in the sense that its competitive ratio attains the optimal rate of growth when the horizon uncertainty grows large.
• Abstract（参考訳）: 意思決定者は、報酬を最大化するために、確率的に生成される逐次的な要求に限られたリソースを割り当てる必要がある。 実際にモチベーションとして,意思決定者にとって未知の分布から要求を独立して引き出す,データ駆動型設定を考える。 オンラインリソースの割り当てとその特別事例は過去に広く研究されてきたが、これらの以前の結果は極めて重要かつ普遍的に、事実上不可能な仮定に依存している。 収益管理やオンライン広告といった多くのアプリケーションでは、需要の変動やユーザートラフィックの強度のためにリクエスト数が大きく変化する可能性がある。 本研究では,地平線不確実性に頑健なオンラインアルゴリズムを開発する。 既知の水平配置とは対照的に、地平線の不確実性に依存しない漸近的な競合比を達成するアルゴリズムは存在しない。 次に, 二重ミラー降下と, 慎重な目標消費列を組み合わせた新しいアルゴリズムを導入し, 有界な競合比を達成することを証明した。 我々のアルゴリズムは、その競合比が地平線の不確かさが大きくなると最適な成長速度に達するという意味で、ほぼ最適である。

関連論文リスト

• Uncertainty Quantification for Forward and Inverse Problems of PDEs via Latent Global Evolution [110.99891169486366]
  本稿では,効率的かつ高精度な不確実性定量化を深層学習に基づく代理モデルに統合する手法を提案する。 本手法は,フォワード問題と逆問題の両方に対して,堅牢かつ効率的な不確実性定量化機能を備えたディープラーニングに基づく代理モデルを提案する。 提案手法は, 長期予測を含むシナリオに適合し, 拡張された自己回帰ロールアウトに対する不確かさの伝播に優れる。
  論文  参考訳（メタデータ） (2024-02-13T11:22:59Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。 本手法は, 精度の高い問題に特に適している。 提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
  論文  参考訳（メタデータ） (2023-11-08T00:10:21Z)
• Fairness in Matching under Uncertainty [78.39459690570531]
  アルゴリズム的な二面市場は、こうした設定における公平性の問題に注意を向けている。 我々は、利益の不確実性を尊重する両面の市場設定において、個々人の公正性の概念を公理化する。 そこで我々は,配当よりも公平なユーティリティ最大化分布を求めるために,線形プログラミングフレームワークを設計する。
  論文  参考訳（メタデータ） (2023-02-08T00:30:32Z)
• Sequential Fair Resource Allocation under a Markov Decision Process Framework [9.440900386313213]
  限られた資源を有限の地平線上で到着する際の要求を明らかにするエージェントに割り当てることのシーケンシャルな意思決定問題について検討する。 我々は,地平線上での要求全体に対して公平なアロケーションを行う新しいアルゴリズムであるSAFFEを提案する。 SAFFEはより公平で効率的なアロケーションを実現し、密着度の高い設定で最適に近い性能を実現する。
  論文  参考訳（メタデータ） (2023-01-10T02:34:00Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。 提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-28T02:21:06Z)
• 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)
• Online Decision Trees with Fairness [8.949941684885323]
  本稿では,分散フローの可能なデータストリームに公平性を持つオンライン決定ツリーの新たなフレームワークを提案する。 具体的には、まず、データを可能な限り符号化する2つの新しい公平分割基準を提案する。 第2に、オンラインの公正意思決定要求を満たす2つの公正決定木オンライン成長アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-15T02:50:13Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。 この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。 目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
  論文  参考訳（メタデータ） (2020-07-01T14:24:58Z)

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

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