論文の概要: 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指数の存在(インデクサビリティ)とアルゴリズムに対する同値性を理論的に証明する。
これらの条件が成立しない場合,数値実験によりアルゴリズムの最適に近い性能を示す。
関連論文リスト
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [48.92318828548911]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳(メタデータ) (2024-02-24T06:36:08Z) - 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) - Efficient Reinforcement Learning with Impaired Observability: Learning
to Act with Delayed and Missing State Observations [92.25604137490168]
本稿では,制御系における効率的な強化学習に関する理論的研究を紹介する。
遅延および欠落した観測条件において,RL に対して $tildemathcalO(sqrtrm poly(H) SAK)$ という形でアルゴリズムを提示し,その上限と下限をほぼ最適に設定する。
論文 参考訳(メタデータ) (2023-06-02T02:46:39Z) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳(メタデータ) (2023-01-18T00:53:46Z) - Stochastic Rising Bandits [40.32303434592863]
本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。
この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。
我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
論文 参考訳(メタデータ) (2022-12-07T17:30:45Z) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳(メタデータ) (2022-02-03T21:19:36Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Maillard Sampling: Boltzmann Exploration Done Optimally [11.282341369957216]
この論文は、$K$武装バンディット問題に対するランダム化アルゴリズムを示す。
メイラードサンプリング(MS)は、各アームを閉じた形で選択する確率を計算する。
最適性を失わずに$sqrtKTlogK$に制限された最小値を改善するMS$+$というMSの変種を提案する。
論文 参考訳(メタデータ) (2021-11-05T06:50:22Z) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳(メタデータ) (2020-11-05T05:16:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。