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

• arxiv url: http://arxiv.org/abs/2502.05145v1
• Date: Fri, 07 Feb 2025 18:23:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-10 14:55:56.892454
• Title: From Restless to Contextual: A Thresholding Bandit Approach to Improve Finite-horizon Performance
• Title（参考訳）: レストレスからコンテクストへ - 有限ホライズン性能向上のためのバンド利きアプローチ-
• Authors: Jiamin Xu, Ivan Nazarov, Aditya Rastogi, África Periáñez, Kyra Gan,
• Abstract要約: オンラインのレスレス・バンディットは、国家の移行と予算の制約を取り入れることで、古典的な文脈的バンディットを拡張している。 我々は、拡張性のある予算付きしきい値付き帯域幅問題として問題を再構築する。 本稿では,オンラインマルチステート設定において,最小限の最小定数後悔を実現するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 4.770896774729555
• License:
• Abstract: Online restless bandits extend classic contextual bandits by incorporating state transitions and budget constraints, representing each agent as a Markov Decision Process (MDP). This framework is crucial for finite-horizon strategic resource allocation, optimizing limited costly interventions for long-term benefits. However, learning the underlying MDP for each agent poses a major challenge in finite-horizon settings. To facilitate learning, we reformulate the problem as a scalable budgeted thresholding contextual bandit problem, carefully integrating the state transitions into the reward design and focusing on identifying agents with action benefits exceeding a threshold. We establish the optimality of an oracle greedy solution in a simple two-state setting, and propose an algorithm that achieves minimax optimal constant regret in the online multi-state setting with heterogeneous agents and knowledge of outcomes under no intervention. We numerically show that our algorithm outperforms existing online restless bandit methods, offering significant improvements in finite-horizon performance.
• Abstract（参考訳）: オンラインのレスレス・バンディットは、国家の移行と予算の制約を取り入れ、各エージェントをマルコフ決定プロセス(MDP)として表現することで、古典的な文脈的バンディットを拡張している。 このフレームワークは、長期的利益のために限られたコストの介入を最適化し、有限水平戦略資源割り当てに不可欠である。 しかし、各エージェントに対する基礎となるMDPの学習は、有限水平設定において大きな課題となる。 学習を容易にするため、我々は、スケーラブルな予算付きしきい値境界バンドイット問題として問題を再構築し、状態遷移を報酬設計に注意深く統合し、しきい値を超えるアクション利益を持つエージェントを特定することに重点を置いている。 簡単な2状態設定でオラクルの欲求解の最適性を確立し、異種エージェントを用いたオンライン多状態設定において、最小限の絶対的後悔と介入のない結果の知識を実現するアルゴリズムを提案する。 提案アルゴリズムは既存のオンラインレス・バンディット法よりも優れており,有限水平性能が大幅に向上していることを示す。

関連論文リスト

• 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)

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

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