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

• arxiv url: http://arxiv.org/abs/2206.13606v3
• Date: Thu, 22 Jun 2023 20:56:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-26 17:54:49.487016
• 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. At each time step, 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 prior results crucially and universally rely on the strong assumption that 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, no algorithm can achieve even a constant asymptotic competitive ratio that is independent of the horizon uncertainty. We introduce a novel generalization of dual mirror descent which allows the decision maker to specify a schedule of time-varying target consumption rates, and prove corresponding performance guarantees. We go on to give a fast algorithm for computing a schedule of target consumption rates that leads to near-optimal performance in the unknown-horizon setting. In particular, our competitive ratio attains the optimal rate of growth (up to logarithmic factors) as the horizon uncertainty grows large. Finally, we also provide a way to incorporate machine-learned predictions about the horizon which interpolates between the known and unknown horizon settings.
• 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)

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

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