論文の概要: Adaptive Bandit Algorithms for Contextual Matching Markets

• arxiv url: http://arxiv.org/abs/2605.28290v1
• Date: Wed, 27 May 2026 10:40:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-28 17:38:55.980871
• Title: Adaptive Bandit Algorithms for Contextual Matching Markets
• Title（参考訳）: コンテキストマッチング市場のための適応帯域幅アルゴリズム
• Authors: Shiyun Lin, Simon Mauras, Vianney Perchet, Nadav Merlis,
• Abstract要約: プレイヤーとアームが2つの市場側を占めており、プレイヤーのユーティリティはアームの文脈で線形である。 各ラウンドでは、新しいアームが観測可能なコンテキストと共に到着し、アルゴリズムがプレイヤーにマッチし、安定したマッチングベンチマークに対して各プレイヤーの後悔を最小限に抑える。 これは、潜在分布から引き出されたコンテキストと、任意であるかもしれない敵コンテキストの2つの設定で対処する。
• 参考スコア（独自算出の注目度）: 34.58046942241621
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study bandit learning in matching markets, where players and arms constitute the two market sides, and the players' utilities are linear in the arm contexts. In each round, new arms arrive with observable contexts. Then, the algorithm matches them to players, aiming to minimize each player's regret against a stable matching benchmark. This contextual structure creates significant complexity: subtle context shifts can slightly alter one player's utility while completely reconfiguring the underlying benchmark, causing large regret spikes for others. We address this in two settings: stochastic contexts, drawn from a latent distribution, and adversarial contexts, which may be arbitrary. For the stochastic case, we introduce a novel minimum preference gap to capture learning difficulty and provide a fully adaptive algorithm with an instance-dependent poly-logarithmic regret upper bound. We also establish matching instance-independent regret upper and lower bounds under a mild distributional assumption. For the adversarial setting, we propose a tractable regret notion that remains valid under arbitrary contexts and achieves an instance-independent sublinear regret bound via an adaptive algorithm.
• Abstract（参考訳）: プレイヤーとアームが2つの市場側を占めており、プレイヤーのユーティリティはアームの文脈で線形である。 各ラウンドで、新しいアームが観測可能なコンテキストで到着する。 このアルゴリズムは,各プレイヤーの後悔を最小化し,安定なマッチングベンチマークに対して最小化することを目的として,プレイヤーにマッチする。 微妙なコンテキストシフトは、あるプレイヤーのユーティリティをわずかに変更し、基盤となるベンチマークを完全に再構成し、他のプレイヤーにとって大きな後悔のスパイクを引き起こす。 確率的文脈とは、潜在分布から引き出された確率的文脈と、任意であるかもしれない対数的文脈の2つの設定で対処する。 確率的ケースでは、学習困難を捉えるために、新しい最小限の選好ギャップを導入し、インスタンス依存の多対数的後悔上限を持つ完全適応アルゴリズムを提供する。 また、軽度分布仮定の下で、インスタンス非依存の後悔の上と下の境界を一致させる。 本稿では,任意の状況下でも有効であり,適応アルゴリズムを用いてインスタンス非依存のサブ線形後悔を実現する,抽出可能な後悔の概念を提案する。

関連論文リスト

• Optimal cross-learning for contextual bandits with unknown context distributions [28.087360479901978]
  本稿では,バルセイロ等のクロスラーニング環境において,文脈的包括的アルゴリズムを設計する際の問題点について考察する。 コンテクスト数によらずに$widetildeO(sqrtTK)$というほぼ厳密な(対数的要因まで)後悔境界を持つ効率的なアルゴリズムを提供する。 アルゴリズムのコアとなるのは,複数のエポックにまたがるアルゴリズムの実行をコーディネートする新しい手法である。
  論文  参考訳（メタデータ） (2024-01-03T18:02:13Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization [29.579719765255927]
  本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。 我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
  論文  参考訳（メタデータ） (2023-07-05T08:34:54Z)
• Reproducible Bandits [95.8830340560603]
  バンディット環境におけるポリシーは、2つの異なる実行において全く同じ腕列を高い確率で引き出すと再現可能と呼ばれる。 再現可能なポリシが存在するだけでなく、時間的地平線の観点から、ほぼ同じ(再現不可能な)後悔境界を達成することを示す。 以上の結果から,無作為化が探索・探索トレードオフに不可欠であるにもかかわらず,同一の腕を2回の異なるラウンドで引き抜いて最適なバランスをとれることが示唆された。
  論文  参考訳（メタデータ） (2022-10-04T20:36:45Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [61.6869963435955]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• Contextual Blocking Bandits [35.235375147227124]
  我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。 アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。 我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2020-03-06T20:34:42Z)

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

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