論文の概要: Whittle Index for A Class of Restless Bandits with Imperfect Observations

• arxiv url: http://arxiv.org/abs/2108.03812v1
• Date: Mon, 9 Aug 2021 05:01:19 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-11 04:03:47.322165
• Title: Whittle Index for A Class of Restless Bandits with Imperfect Observations
• Title（参考訳）: 不完全な観察を行うレストレスバンドのWhittle Index
• Authors: Keqin Liu and Ting Wu
• Abstract要約: 我々は、最適化、強化学習、運用研究において幅広い応用分野を見出す、レスレスバンディット問題の一類を考察する。 我々のモデルでは、独立な2ドル状態のマルコフプロセスがあり、それを観察し、報酬を得るためにアクセスすることができる。 我々は,このタイプのレスレス・バンディットに対して高い性能を実現する,低複雑さのアルゴリズムを確立する。
• 参考スコア（独自算出の注目度）: 4.822598110892847
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a class of restless bandit problems that finds a broad application area in stochastic optimization, reinforcement learning and operations research. In our model, there are $N$ independent $2$-state Markov processes that may be observed and accessed for accruing rewards. The observation is error-prone, i.e., both false alarm and miss detection may happen. Furthermore, the user can only choose a subset of $M~(M<N)$ processes to observe at each discrete time. If a process in state~$1$ is correctly observed, then it will offer some reward. Due to the partial and imperfect observation model, the system is formulated as a restless multi-armed bandit problem with an information state space of uncountable cardinality. Restless bandit problems with finite state spaces are PSPACE-HARD in general. In this paper, we establish a low-complexity algorithm that achieves a strong performance for this class of restless bandits. Under certain conditions, we theoretically prove the existence (indexability) of Whittle index and its equivalence to our algorithm. When those conditions do not hold, we show by numerical experiments the near-optimal performance of our algorithm in general.
• Abstract（参考訳）: 本稿では,確率的最適化,強化学習,運用研究において幅広い応用領域を見出す,restless bandit問題の一クラスについて考察する。 我々のモデルでは、独立な2ドル状態のマルコフプロセスがあり、それを観察し、報酬を得るためにアクセスすることができる。 観測はエラーを起こしやすいため、誤報と誤検知の両方が起こる可能性がある。 さらに、ユーザーは各離散時間に観察するために$M~(M<N)$プロセスのサブセットしか選択できない。 状態~1$のプロセスが正しく観察された場合、何らかの報酬が与えられる。 部分的かつ不完全な観測モデルにより、このシステムは無数濃度の情報状態空間を持つレスレスマルチアームバンディット問題として定式化される。 有限状態空間のレスレスバンディット問題は一般にPSPACE-HARDである。 本稿では,このタイプのrestレスバンディットに対して強力な性能を実現するための低複雑度アルゴリズムを提案する。 ある条件下では、Whittle指数の存在(インデクサビリティ)とアルゴリズムに対する同値性を理論的に証明する。 これらの条件が成立しない場合,数値実験によりアルゴリズムの最適に近い性能を示す。

関連論文リスト

• Nearly Optimal Sample Complexity of Offline KL-Regularized Contextual Bandits under Single-Policy Concentrability [49.96531901205305]
  我々は,オフラインの文脈的包帯に対する単一政治中心性の下でのサンプル複雑性を$tildeO(epsilon-1)$とするemphfirstアルゴリズムを提案する。 我々の証明は、KL正則化の強い凸性と、真の報酬と悲観的推定子のギャップの条件的非負性を利用する。 我々は,このアルゴリズムを文脈的デュエル帯域に拡張し,ほぼ最適なサンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Replicability is Asymptotically Free in Multi-armed Bandits [41.86005698892541]
  我々は,アルゴリズムの動作シーケンスがデータセットに固有のランダム性の影響を受けないことを高い確率で保証する,レプリカブルなマルチアームバンディットアルゴリズムを考察する。 非複製の確率を制限するための原則的アプローチを提案する。
  論文  参考訳（メタデータ） (2024-02-12T03:31:34Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• PCL-Indexability and Whittle Index for Restless Bandits with General Observation Models [0.0]
  我々は、任意の初期信念から始まる可算な信念状態空間を持つレスレス・バンディットとして問題を定式化する。 有限状態問題に対するNino-Mora と Bertsimas の AG アルゴリズムを適用可能な問題に変換する近似法を提案する。
  論文  参考訳（メタデータ） (2023-07-06T14:56:13Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control [0.0]
  このノートは"One-Way Ticket to Las Vegas and the Quantum Adversary"という論文を補完している。 私は、Barnum-Saks-Szegedyと同じ視点で、逆境界-普遍アルゴリズムの双対性を異なる形で開発する。
  論文  参考訳（メタデータ） (2022-11-29T15:25:45Z)
• Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference [23.364534479492715]
  期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。 本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
  論文  参考訳（メタデータ） (2022-07-23T20:25:07Z)
• 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)

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

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