論文の概要: Bandits with Single-Peaked Preferences and Limited Resources

• arxiv url: http://arxiv.org/abs/2510.09425v1
• Date: Fri, 10 Oct 2025 14:27:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 00:38:49.286598
• Title: Bandits with Single-Peaked Preferences and Limited Resources
• Title（参考訳）: 単一ピークの優先度と限られたリソースを持つ帯域
• Authors: Gur Keinan, Rotem Torkan, Omer Ben-Porat,
• Abstract要約: アルゴリズムがU$ユーザとK$アームとを逐次一致させるオンラインマッチング問題について検討する。 構造的仮定がなければ、最適マッチングの計算はNPハードであり、オンライン学習は計算不可能である。 我々はオフラインの予算マッチング問題に対する効率的なアルゴリズムを考案し、それを$tilde O(UKT2/3)$を後悔して効率的なオンラインアルゴリズムに活用する。
• 参考スコア（独自算出の注目度）: 6.205308371824035
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study an online stochastic matching problem in which an algorithm sequentially matches $U$ users to $K$ arms, aiming to maximize cumulative reward over $T$ rounds under budget constraints. Without structural assumptions, computing the optimal matching is NP-hard, making online learning computationally infeasible. To overcome this barrier, we focus on \emph{single-peaked preferences} -- a well-established structure in social choice theory, where users' preferences are unimodal with respect to a common order over arms. We devise an efficient algorithm for the offline budgeted matching problem, and leverage it into an efficient online algorithm with a regret of $\tilde O(UKT^{2/3})$. Our approach relies on a novel PQ tree-based order approximation method. If the single-peaked structure is known, we develop an efficient UCB-like algorithm that achieves a regret bound of $\tilde O(U\sqrt{TK})$.
• Abstract（参考訳）: 予算制約下での累積報酬を最大化することを目的として,アルゴリズムがU$ユーザをK$アームに順次マッチングするオンライン確率マッチング問題について検討した。 構造的仮定がなければ、最適マッチングの計算はNPハードであり、オンライン学習は計算不可能である。 この障壁を克服するために、我々は「emph{single-peaked preferences」という社会的選択理論の確立された構造に注目し、ユーザの嗜好は、武器に関する共通の順序に関して、一過性である。 我々はオフラインの予算マッチング問題に対して効率的なアルゴリズムを考案し、それを$\tilde O(UKT^{2/3})$を後悔して効率的なオンラインアルゴリズムに活用する。 我々の手法は、新しいPQ木に基づく順序近似法に依存している。 シングルピーク構造が知られている場合、我々は、$\tilde O(U\sqrt{TK})$の後悔境界を達成できる効率的なUPB様アルゴリズムを開発する。

関連論文リスト

• Batched Stochastic Matching Bandits [43.651070266360954]
  本稿では,MNL選択モデルに基づくマッチングのための新しい帯域幅フレームワークを提案する。 私たちの設定では、一方の$N$エージェントは他方の$K$アームに割り当てられます。 目的は、すべてのエージェントで成功した試合から累積収入を最大化することで、後悔を最小限に抑えることである。
  論文  参考訳（メタデータ） (2025-09-04T13:16:32Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback [27.192028744078282]
  離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。 提案手法は準モジュラー地平線における多種多様な応用に適用できる。
  論文  参考訳（メタデータ） (2023-01-30T23:18:06Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• An Improved Algorithm For Online Min-Sum Set Cover [0.45687771576879593]
  我々は、アルゴリズムが注文された$n$要素のリストを保持するオンライン嗜好集約のモデルについて研究する。 競合比(ALG-to-OPTコスト比)が$O(r2)$である計算効率の良いランダム化アルゴリズムを構築する。 O(r3/2 cdot sqrtn)$-competitive and $Omega(r)$ is a lower bound on the performance of any deterministic online algorithm。
  論文  参考訳（メタデータ） (2022-09-11T14:03:51Z)
• Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
  本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。 差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。 同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
  論文  参考訳（メタデータ） (2021-02-16T02:48:16Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)

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

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