論文の概要: Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems

• arxiv url: http://arxiv.org/abs/2103.04730v1
• Date: Mon, 8 Mar 2021 13:10:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-09 15:59:33.142236
• Title: Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems
• Title（参考訳）: 有限水平およびストリーミングレスマルチアーム帯域問題に対する効率的なアルゴリズム
• Authors: Aditya Mate, Arpita Biswas, Christoph Siebenbrunner, Milind Tambe
• Abstract要約: インデックスベースのソリューションを計算するための新しいスケーラブルなアプローチを提案します。 コストのかかる有限地平線問題を解くことなく,指数減衰をキャプチャするアルゴリズムを提供する。 当社のアルゴリズムは、これらのタスクにおける既存の方法よりも150倍以上のスピードアップを実現し、パフォーマンスを損ないません。
• 参考スコア（独自算出の注目度）: 30.759279275710078
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Restless Multi-Armed Bandits (RMABs) have been popularly used to model limited resource allocation problems. Recently, these have been employed for health monitoring and intervention planning problems. However, the existing approaches fail to account for the arrival of new patients and the departure of enrolled patients from a treatment program. To address this challenge, we formulate a streaming bandit (S-RMAB) framework, a generalization of RMABs where heterogeneous arms arrive and leave under possibly random streams. We propose a new and scalable approach to computing index-based solutions. We start by proving that index values decrease for short residual lifetimes, a phenomenon that we call index decay. We then provide algorithms designed to capture index decay without having to solve the costly finite horizon problem, thereby lowering the computational complexity compared to existing methods.We evaluate our approach via simulations run on real-world data obtained from a tuberculosis intervention planning task as well as multiple other synthetic domains. Our algorithms achieve an over 150x speed-up over existing methods in these tasks without loss in performance. These findings are robust across multiple domains.
• Abstract（参考訳）: Restless Multi-Armed Bandits (RMAB) はリソース割り当ての問題のモデル化に広く使われている。 近年,これらを健康モニタリングや介入計画に活用している。 しかし、既存のアプローチは、新しい患者の到着と、治療プログラムから登録された患者の出発を考慮に入れていない。 この課題に対処するため,非均質な腕が到達し,おそらくランダムなストリームの下を離れるRMABの一般化であるストリーミングバンディット(S-RMAB)フレームワークを策定する。 インデックスベースのソリューションを計算するための新しいスケーラブルなアプローチを提案します。 まず、指標値が短い寿命で減少することが証明され、これは指数減衰と呼ばれる現象である。 次に、コストのかかる有限な地平線問題を解決することなくインデックス崩壊を捕捉するアルゴリズムを提供し、既存の手法と比較して計算の複雑さを低減し、結核介入計画タスクと複数の合成領域から得られた実世界データを用いたシミュレーションによるアプローチを評価します。 当社のアルゴリズムは、これらのタスクにおける既存の方法よりも150倍以上のスピードアップを実現し、パフォーマンスを損ないません。 これらの発見は複数のドメインにまたがって堅牢である。

関連論文リスト

• 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)
• QN-Mixer: A Quasi-Newton MLP-Mixer Model for Sparse-View CT Reconstruction [0.0]
  準ニュートン法に基づくアルゴリズムQN-Mixerを導入する。 Incept-Mixerは非局所正規化用語として機能する効率的なニューラルネットワークである。 我々のアプローチは知的に情報をサンプリングし、計算要求を大幅に削減する。
  論文  参考訳（メタデータ） (2024-02-28T00:20:25Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep Unrolling(ディープ・アンローリング)は、トレーニング可能なニューラルネットワークの層に切り捨てられた反復アルゴリズムをアンロールする、新たな学習最適化手法である。 アンロールネットワークの収束保証と一般化性は、いまだにオープンな理論上の問題であることを示す。 提案した制約の下で訓練されたアンロールアーキテクチャを2つの異なるアプリケーションで数値的に評価する。
  論文  参考訳（メタデータ） (2023-12-25T18:51:23Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits [30.532795983761314]
  本研究では,複数の行動を伴うレスレス・マルチアーム・バンディット(RMAB)の計画問題について検討する。 まず、Whittleインデックスポリシーは、シンプルで実用的な設定で失敗する可能性があることを示す。 次に,平均場法に基づく代替計画アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-31T19:35:15Z)
• Estimating Optimal Infinite Horizon Dynamic Treatment Regimes via pT-Learning [2.0625936401496237]
  モバイルヘルス(mHealth)技術の最近の進歩は、個人の健康状態を監視し、ジャスト・イン・タイムのパーソナライズされた介入を提供する効果的な方法を提供する。 mHealthテクノロジーの実用化は、最適な動的治療体制を学習する上で、既存の方法論に固有の課題を提起する。 本稿では,決定論的とスパース政策モデルの間で適応的に調整された最適条件を推定する近時学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-10-20T18:38:22Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
  論文  参考訳（メタデータ） (2020-11-05T05:16:04Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Differentiable Causal Discovery from Interventional Data [141.41931444927184]
  本稿では、介入データを活用可能なニューラルネットワークに基づく理論的基盤化手法を提案する。 提案手法は,様々な環境下での美術品の状態と良好に比較できることを示す。
  論文  参考訳（メタデータ） (2020-07-03T15:19:17Z)
• Structure Adaptive Algorithms for Stochastic Bandits [22.871155520200773]
  構造化多武装バンディット問題のクラスにおける報酬最大化について検討する。 平均的な武器の報酬は、与えられた構造的制約を満たす。 我々は、反復的なサドルポイントソルバを用いて、インスタンス依存の低バウンドからのアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-07-02T08:59:54Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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