論文の概要: Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits

• arxiv url: http://arxiv.org/abs/2011.02664v2
• Date: Fri, 6 Nov 2020 08:00:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-29 12:25:48.114738
• Title: Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• Title（参考訳）: Restless-UCB - オンラインレスレスバンドの効率的かつ低複雑さアルゴリズム
• Authors: Siwei Wang, Longbo Huang, John C.S. Lui
• Abstract要約: 我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
• 参考スコア（独自算出の注目度）: 61.490254407420906
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the online restless bandit problem, where the state of each arm evolves according to a Markov chain, and the reward of pulling an arm depends on both the pulled arm and the current state of the corresponding Markov chain. In this paper, we propose Restless-UCB, a learning policy that follows the explore-then-commit framework. In Restless-UCB, we present a novel method to construct offline instances, which only requires $O(N)$ time-complexity ($N$ is the number of arms) and is exponentially better than the complexity of existing learning policy. We also prove that Restless-UCB achieves a regret upper bound of $\tilde{O}((N+M^3)T^{2\over 3})$, where $M$ is the Markov chain state space size and $T$ is the time horizon. Compared to existing algorithms, our result eliminates the exponential factor (in $M,N$) in the regret upper bound, due to a novel exploitation of the sparsity in transitions in general restless bandit problems. As a result, our analysis technique can also be adopted to tighten the regret bounds of existing algorithms. Finally, we conduct experiments based on real-world dataset, to compare the Restless-UCB policy with state-of-the-art benchmarks. Our results show that Restless-UCB outperforms existing algorithms in regret, and significantly reduces the running time.
• Abstract（参考訳）: そこで本研究では,各アームの状態がマルコフ連鎖に従って進化するオンラインレストレスバンディット問題について検討し,アームを引っ張る報酬は,引っ張られたアームと対応するマルコフ連鎖の現在の状態の両方に依存することを示した。 本稿では,探索課題の枠組みに従う学習方針であるRestless-UCBを提案する。 Restless-UCBにおいて、オフラインインスタンスを構築する新しい方法を提案する。これは、O(N)$time-complexity(N$は腕の数)だけで、既存の学習ポリシーの複雑さよりも指数関数的に優れている。 また、Restless-UCB が $\tilde{O}((N+M^3)T^{2\over 3})$ の後悔の上界を達成することを証明している。 既存のアルゴリズムと比較すると,本手法は一般のrestless bandit問題における遷移のスパーシティの新たな利用により,後悔の上限値の指数係数($m,n$)を除去した。 その結果,既存のアルゴリズムの残差を厳格化するために解析手法が適用可能となった。 最後に、実世界のデータセットに基づいて実験を行い、Restless-UCBポリシーと最先端ベンチマークを比較した。 その結果,restless-ucbは既存のアルゴリズムを上回っており,実行時間を大幅に削減できることがわかった。

関連論文リスト

• Variance-Aware Linear UCB with Deep Representation for Neural Contextual Bandits [9.877915844066338]
  ニューラルアッパー信頼バウンド(UCB)アルゴリズムは、文脈的帯域幅で成功している。 本稿では,$sigma2_t$,すなわちラウンド$t$における報奨雑音の上限値を利用する分散認識アルゴリズムを提案する。 我々は,本アルゴリズムのオラクル版として,オラクル分散上界$sigma2_t$と,この分散境界に対する新しい推定値を持つ実用版を特徴とする。
  論文  参考訳（メタデータ） (2024-11-08T21:24:14Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Stochastic Rising Bandits [40.32303434592863]
  本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。 この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2022-12-07T17:30:45Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-16T17:52:32Z)
• 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)
• Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
  本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。 ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。 私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
  論文  参考訳（メタデータ） (2020-12-01T07:33:00Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
  本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。 以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-02-24T08:59:34Z)

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

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