論文の概要: Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets

• arxiv url: http://arxiv.org/abs/2510.14097v1
• Date: Wed, 15 Oct 2025 21:09:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-17 21:15:14.619608
• Title: Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets
• Title（参考訳）: オンライン学習における2段階市場におけるほぼ最適レグレット・キュー長トレードオフ
• Authors: Zixian Yang, Sushil Mahavir Varma, Lei Ying,
• Abstract要約: 我々は、価格に敏感な異種顧客とサーバが到着し、それぞれのキューに参加する二面市場について検討する。 互換性のあるカスタマサーバペアはプラットフォームによってマッチングされ、その時点でシステムを離れる。 我々の目標は、適切な待ち時間を維持しながら、プラットフォームの利益を最大化する価格とマッチングアルゴリズムを設計することである。
• 参考スコア（独自算出の注目度）: 11.51661878156199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a two-sided market, wherein, price-sensitive heterogeneous customers and servers arrive and join their respective queues. A compatible customer-server pair can then be matched by the platform, at which point, they leave the system. Our objective is to design pricing and matching algorithms that maximize the platform's profit, while maintaining reasonable queue lengths. As the demand and supply curves governing the price-dependent arrival rates may not be known in practice, we design a novel online-learning-based pricing policy and establish its near-optimality. In particular, we prove a tradeoff among three performance metrics: $\tilde{O}(T^{1-\gamma})$ regret, $\tilde{O}(T^{\gamma/2})$ average queue length, and $\tilde{O}(T^{\gamma})$ maximum queue length for $\gamma \in (0, 1/6]$, significantly improving over existing results [1]. Moreover, barring the permissible range of $\gamma$, we show that this trade-off between regret and average queue length is optimal up to logarithmic factors under a class of policies, matching the optimal one as in [2] which assumes the demand and supply curves to be known. Our proposed policy has two noteworthy features: a dynamic component that optimizes the tradeoff between low regret and small queue lengths; and a probabilistic component that resolves the tension between obtaining useful samples for fast learning and maintaining small queue lengths.
• Abstract（参考訳）: 我々は、価格に敏感な異種顧客とサーバが到着し、それぞれのキューに参加する二面市場について検討する。 互換性のあるカスタマサーバペアはプラットフォームによってマッチングされ、その時点でシステムを離れる。 我々の目標は、適切な待ち時間を維持しながら、プラットフォームの利益を最大化する価格とマッチングアルゴリズムを設計することである。 価格に依存した到着率を規定する需要と供給曲線は実際には分かっていないため、我々は新しいオンライン学習ベースの価格政策を設計し、そのほぼ最適性を確立する。 特に、3つのパフォーマンス指標のトレードオフを証明している: $\tilde{O}(T^{1-\gamma})$ regret, $\tilde{O}(T^{\gamma/2})$ average queue length, $\tilde{O}(T^{\gamma})$ maximum queue length for $\gamma \in (0, 1/6]$。 さらに、許容範囲を$\gamma$とすると、後悔と平均キュー長の間のこのトレードオフは、ポリシーのクラスにおける対数的要因に最適であることを示す。 提案するポリシには,低遅延長と小待ち長のトレードオフを最適化する動的コンポーネントと,高速学習と小待ち長の維持に有用なサンプルの取得との間に生じる緊張を解消する確率的コンポーネントという,2つの特徴がある。

関連論文リスト

• Analyzing homogenous and heterogeneous multi-server queues via neural networks [0.0]
  我々は,シングルステイトンマルチサーバシステムにおいて,顧客数の定常分布を予測するために,機械学習アプローチを用いる。 システム内の顧客数の定常分布を、$GI/GI_i/2$キューで予測するのは私たちだけです。
  論文  参考訳（メタデータ） (2025-04-01T12:30:18Z)
• Learning payoffs while routing in skill-based queues [0.4077787659104315]
  我々は,全支払パラメータを適応的に学習し,全支払パラメータを最大化する機械学習アルゴリズムを構築した。 このアルゴリズムは,残差の下限を導出することにより,対数項に最適であることを示す。
  論文  参考訳（メタデータ） (2024-12-13T14:33:50Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Learning-Based Pricing and Matching for Two-Sided Queues [14.854050478428727]
  複数のタイプの顧客とサーバを持つ動的システムについて検討する。 各キューの到着率は、未知の需要または供給機能に応じて価格によって決定される。 このシステムは、乗客やドライバーとの乗り合い市場のような、両側の市場をモデル化するのに使用することができる。
  論文  参考訳（メタデータ） (2024-03-17T05:07:04Z)
• 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)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• MNL-Bandits under Inventory and Limited Switches Constraints [38.960764902819434]
  我々は、データから顧客の選択を学習しながら、アソートを最適化する効率的な UCB ライクなアルゴリズムを開発した。 我々のアルゴリズムは、$O(Talpha)$スイッチが許される場合、サブ線形後悔境界$tildeOleft(T1-alpha/2right)$を達成できることを証明している。
  論文  参考訳（メタデータ） (2022-04-22T16:02:27Z)
• Linear Speedup in Personalized Collaborative Learning [69.45124829480106]
  フェデレート学習におけるパーソナライゼーションは、モデルのバイアスをトレーディングすることで、モデルの精度を向上させることができる。 ユーザの目的の最適化として、パーソナライズされた協調学習問題を定式化する。 分散の低減のためにバイアスを最適にトレードオフできる条件について検討する。
  論文  参考訳（メタデータ） (2021-11-10T22:12:52Z)
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation [81.0955457177017]
  GAIL(Generative Adversarial mimicion Learning)では、特定の報酬セットにおいて、専門家の政策からそのパフォーマンスを区別できないように、専門家のデモンストレーションからポリシーを学習することを目的としている。 GAILをオンラインとオフラインの両方で線形関数近似を用いて検討し、その変換関数と報酬関数は特徴写像において線形である。
  論文  参考訳（メタデータ） (2021-08-19T16:16:00Z)

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

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