論文の概要: Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation

• arxiv url: http://arxiv.org/abs/2501.06103v1
• Date: Fri, 10 Jan 2025 16:54:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-13 15:26:19.248149
• Title: Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation
• Title（参考訳）: Finite-Horizon Single-Pull Restless Bandits: 資源配分のための効率的な指標ポリシー
• Authors: Guojun Xiong, Haichuan Wang, Yuqi Pan, Saptarshi Mandal, Sanket Shah, Niclas Boehmer, Milind Tambe,
• Abstract要約: 両腕を1回だけ引っ張ることができる新しい変種であるFinite-Horizon Single-Pull RMABを紹介した。 我々は、ダミー状態を用いてシステムを複製し、腕が活性化されるとダミー状態内でのみ遷移することを提案する。 有限個のアームに対して,我々の指数ポリシが$tildemathcalOleft(frac1rho1/2right)$の線形に崩壊する平均最適性ギャップを達成できることを初めて実証した。
• 参考スコア（独自算出の注目度）: 33.11114874824768
• License:
• Abstract: Restless multi-armed bandits (RMABs) have been highly successful in optimizing sequential resource allocation across many domains. However, in many practical settings with highly scarce resources, where each agent can only receive at most one resource, such as healthcare intervention programs, the standard RMAB framework falls short. To tackle such scenarios, we introduce Finite-Horizon Single-Pull RMABs (SPRMABs), a novel variant in which each arm can only be pulled once. This single-pull constraint introduces additional complexity, rendering many existing RMAB solutions suboptimal or ineffective. %To address this, we propose using dummy states to duplicate the system, ensuring that once an arm is activated, it transitions exclusively within the dummy states. To address this shortcoming, we propose using \textit{dummy states} that expand the system and enforce the one-pull constraint. We then design a lightweight index policy for this expanded system. For the first time, we demonstrate that our index policy achieves a sub-linearly decaying average optimality gap of $\tilde{\mathcal{O}}\left(\frac{1}{\rho^{1/2}}\right)$ for a finite number of arms, where $\rho$ is the scaling factor for each arm cluster. Extensive simulations validate the proposed method, showing robust performance across various domains compared to existing benchmarks.
• Abstract（参考訳）: Restless Multi-armed bandits (RMAB)は、多くのドメインにまたがるシーケンシャルなリソース割り当ての最適化に成功している。 しかし、医療介入プログラムなど、各エージェントが少なくとも1つのリソースしか受信できない、非常に少ないリソースを持つ多くの実践的な環境では、RMABフレームワークは不足している。 このようなシナリオに対処するために、各アームを1回だけ引っ張ることができる新しい変種であるFinite-Horizon Single-Pull RMABs (SPRMABs)を導入する。 この単一プル制約はさらなる複雑さを導入し、既存のRMABソリューションの多くを最適あるいは非効率にレンダリングする。 %) に対処するため, ダミー状態を用いてシステムを複製し, 腕が活性化されると, ダミー状態内でのみ遷移することを提案する。 この欠点に対処するため,システムを拡張し,一括制約を強制する \textit{dummy states} を提案する。 次に、この拡張システムのための軽量インデックスポリシーを設計する。 最初に、我々のインデックスポリシーは、有限個のアームに対して$\tilde{\mathcal{O}}\left(\frac{1}{\rho^{1/2}}\right)$のサブ線形に減衰する平均最適性ギャップを達成し、そこで$\rho$は各アームクラスタのスケーリング係数であることを示した。 大規模なシミュレーションにより提案手法の有効性を検証し,既存のベンチマークと比較し,様々な領域で頑健な性能を示す。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits [16.054685587034836]
  GINO-Qは、レスレスマルチアームバンディット(RMAB)の最適指標ポリシーを学習するために設計された3段階近似アルゴリズムである。 GINO-QはRMABをインデックス化する必要がなく、柔軟性と適用性を高めている。 実験結果から, GINO-Q は非接種可能なRMABに対しても, ほぼ最適に学習できることが示唆された。
  論文  参考訳（メタデータ） (2024-08-19T10:50:45Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget [4.226118870861363]
  固定予算の下で、制約のある純粋な探索、多武装バンディットの定式化を検討する。 本稿では,Successive Rejects フレームワークに基づく textscConstrained-SR というアルゴリズムを提案する。 また, ある特別な場合において, 関連する崩壊速度は情報理論的下界に対してほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2022-11-27T08:58:16Z)
• Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits [30.532795983761314]
  本研究では,複数の行動を伴うレスレス・マルチアーム・バンディット(RMAB)の計画問題について検討する。 まず、Whittleインデックスポリシーは、シンプルで実用的な設定で失敗する可能性があることを示す。 次に,平均場法に基づく代替計画アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-31T19:35:15Z)
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits [8.136957953239254]
  本稿では、R(MA)2Bと呼ばれる複数の動作を持つ有限ホライゾンレス・マルチアームバンディット問題について検討する。 各アームの状態は、制御されたマルコフ決定プロセス(MDP)に従って進化し、アームを引く報酬は、対応するMDPの現在の状態と、取られたアクションの両方に依存する。 最適政策の発見は典型的には難解であるため,我々はOccupancy-Measured-Reward Index Policyと呼ぶ,計算に訴える指標ポリシーを提案する。
  論文  参考訳（メタデータ） (2021-09-20T21:40:12Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
  論文  参考訳（メタデータ） (2020-11-05T05:16:04Z)

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

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