論文の概要: From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Performance

• arxiv url: http://arxiv.org/abs/2502.05145v3
• Date: Mon, 06 Oct 2025 02:24:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 14:28:09.357518
• Title: From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Performance
• Title（参考訳）: レストレスからコンテクストへ - 有限ホライズンパフォーマンスのためのバンドリフォームの留意点
• Authors: Jiamin Xu, Ivan Nazarov, Aditya Rastogi, África Periáñez, Kyra Gan,
• Abstract要約: 我々は,オンラインRBの改革を,文脈的盗賊の根源として導入する。 単純化された有限ホライゾン設定に対するオラクルポリシーの最初の漸近的でない最適性を証明する。 本研究は, 有限水平RBにおける実践的, サンプル効率の学習を実現するための新しい経路を提供する。
• 参考スコア（独自算出の注目度）: 8.173852377640964
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper addresses the poor finite-horizon performance of existing online \emph{restless bandit} (RB) algorithms, which stems from the prohibitive sample complexity of learning a full \emph{Markov decision process} (MDP) for each agent. We argue that superior finite-horizon performance requires \emph{rapid convergence} to a \emph{high-quality} policy. Thus motivated, we introduce a reformulation of online RBs as a \emph{budgeted thresholding contextual bandit}, which simplifies the learning problem by encoding long-term state transitions into a scalar reward. We prove the first non-asymptotic optimality of an oracle policy for a simplified finite-horizon setting. We propose a practical learning policy under a heterogeneous-agent, multi-state setting, and show that it achieves a sublinear regret, achieving \emph{faster convergence} than existing methods. This directly translates to higher cumulative reward, as empirically validated by significant gains over state-of-the-art algorithms in large-scale heterogeneous environments. Our work provides a new pathway for achieving practical, sample-efficient learning in finite-horizon RBs.
• Abstract（参考訳）: 本稿では,既存のオンライン 'emph{restless bandit} (RB) アルゴリズムの有限ホリゾン性能について述べる。 我々は、優れた有限ホライズン性能は \emph{rapid convergence} を \emph{high-quality} ポリシーに要求する。 そこで我々は,長期的状態遷移をスカラー報酬に符号化することで学習問題を単純化する,オンラインRBの改革を「emph{budgeted thresholding contextual bandit}」として導入する。 単純化された有限ホライゾン設定に対するオラクルポリシーの最初の漸近的でない最適性を証明する。 ヘテロジニアス・エージェント・マルチステート・セッティングの下で実践的な学習方針を提案し,既存の手法よりも「emph{faster convergence"」を達成し,サブ線形後悔を実現することを示す。 これは、大規模な異種環境における最先端アルゴリズムよりも大きな利得によって実証的に検証されるように、直接的に高い累積報酬に変換される。 本研究は, 有限水平RBにおける実践的, サンプル効率の学習を実現するための新しい経路を提供する。

関連論文リスト

• Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits [15.700062892888084]
  我々は、割り当て前に選択した武器に関する情報を戦略的に収集する新しい探索フレームワークを導入する。 報奨分布が知られているオフライン環境では、準モジュラ特性を利用して、証明可能な性能境界を持つ欲求探索アルゴリズムを設計する。 より複雑なオンライン設定では、公平性を維持しながらサブ線形後悔を実現するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2025-06-17T21:43:21Z)
• Exponentially Weighted Algorithm for Online Network Resource Allocation with Long-Term Constraints [0.6466206145151128]
  本稿では,ジョブ転送を伴う通信ネットワークにおける最適資源予約問題について検討する。 本稿では,長期制約を含むランダム化指数重み付け法に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-03T10:12:40Z)
• LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problem [4.666048091337632]
  本稿では、Thresholding Linear Bandit(TLB)問題の固定予算設定のために設計された新しいアルゴリズムであるLinearAPTを提案する。 コントリビューションでは、LinearAPTの適応性、単純性、計算効率を強調しており、複雑なシーケンシャルな意思決定課題に対処するためのツールキットとして貴重なものとなっている。
  論文  参考訳（メタデータ） (2024-03-10T15:01:50Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• 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)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)

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

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