論文の概要: Low-Complexity Algorithm for Restless Bandits with Imperfect Observations
- arxiv url: http://arxiv.org/abs/2108.03812v3
- Date: Mon, 13 May 2024 05:32:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-15 02:11:16.649405
- Title: Low-Complexity Algorithm for Restless Bandits with Imperfect Observations
- Title（参考訳）: 不完全な観測を伴うレストレスバンドの低複素性アルゴリズム
- Authors: Keqin Liu, Richard Weber, Chengzhong Zhang,
- Abstract要約: 我々は、強化学習と最適化において幅広い応用分野を見出す、レスレス・バンディット問題の一類を考察する。
我々は,観測誤差を伴う一般的なレスト・バンディット・モデルに容易に適用可能な,高い性能を実現する低複雑性アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 1.4542411354617986
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a class of restless bandit problems that finds a broad application area in reinforcement learning and stochastic optimization. We consider $N$ independent discrete-time Markov processes, each of which had two possible states: 1 and 0 (`good' and `bad'). Only if a process is both in state 1 and observed to be so does reward accrue. The aim is to maximize the expected discounted sum of returns over the infinite horizon subject to a constraint that only $M$ $(<N)$ processes may be observed at each step. Observation is error-prone: there are known probabilities that state 1 (0) will be observed as 0 (1). From this one knows, at any time $t$, a probability that process $i$ is in state 1. The resulting system may be modeled as a restless multi-armed bandit problem with an information state space of uncountable cardinality. Restless bandit problems with even finite state spaces are PSPACE-HARD in general. We propose a novel approach for simplifying the dynamic programming equations of this class of restless bandits and develop a low-complexity algorithm that achieves a strong performance and is readily extensible to the general restless bandit model with observation errors. Under certain conditions, we establish 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 the general parametric space. Furthermore, we theoretically prove the optimality of our algorithm for homogeneous systems.
- Abstract（参考訳）: 我々は、強化学習と確率的最適化において幅広い応用領域を見出す、レスレスバンディット問題の一類を考察する。
N$独立離散時間マルコフ過程を考えると、それぞれ 1 と 0 (`good' と `bad') の2つの可能な状態を持つ。
プロセスが状態1内にあり、そうであるように観察された場合のみ、報酬が発生する。
目的は、各ステップでM$$(<N)$プロセスしか観察できないという制約の下で、無限の地平線上でのリターンの期待の割引和を最大化することである。
状態 1 (0) が 0(1) として観測される確率は知られている。
このことから、いつでも$t$、プロセス$i$が状態1にある確率が分かる。
結果のシステムは、非可算基数の情報状態空間を持つレスレスマルチアームバンディット問題としてモデル化することができる。
有限状態空間においても、レスレスバンディット問題は一般にPSPACE-HARDである。
本稿では,このタイプのレスレス・バンディットの動的プログラミング方程式を単純化する新しい手法を提案し,観測誤差のある一般的なレスレス・バンディットモデルに対して容易に拡張可能な低複雑性アルゴリズムを提案する。
ある条件下では、ウィトル指数の存在(インデクサビリティ)と、アルゴリズムに対する同値性を確立する。
これらの条件が満たされていない場合、数値実験により、一般パラメトリック空間におけるアルゴリズムのほぼ最適性能を示す。
さらに,同質系に対するアルゴリズムの最適性を理論的に証明する。
関連論文リスト
- 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 [45.729105054410745]
この仕事の動機は、再現可能な機械学習の需要の増加にある。
特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
論文 参考訳（メタデータ） (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) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。