論文の概要: Double Thompson Sampling in Finite stochastic Games

• arxiv url: http://arxiv.org/abs/2202.10008v1
• Date: Mon, 21 Feb 2022 06:11:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-24 12:39:45.640946
• Title: Double Thompson Sampling in Finite stochastic Games
• Title（参考訳）: 有限確率ゲームにおけるダブルトンプソンサンプリング
• Authors: Shuqing Shi, Xiaobin Wang, Zhiyou Yang, Fan Zhang and Hong Qu
• Abstract要約: 有限割引マルコフ決定プロセスの下での探索と利用のトレードオフ問題を考察する。 このような問題を解決するために、二重トンプソンサンプリング強化学習アルゴリズム(DTS)を提案する。
• 参考スコア（独自算出の注目度）: 10.559241770674724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the trade-off problem between exploration and exploitation under finite discounted Markov Decision Process, where the state transition matrix of the underlying environment stays unknown. We propose a double Thompson sampling reinforcement learning algorithm(DTS) to solve this kind of problem. This algorithm achieves a total regret bound of $\tilde{\mathcal{O}}(D\sqrt{SAT})$\footnote{The symbol $\tilde{\mathcal{O}}$ means $\mathcal{O}$ with log factors ignored} in time horizon $T$ with $S$ states, $A$ actions and diameter $D$. DTS consists of two parts, the first part is the traditional part where we apply the posterior sampling method on transition matrix based on prior distribution. In the second part, we employ a count-based posterior update method to balance between the local optimal action and the long-term optimal action in order to find the global optimal game value. We established a regret bound of $\tilde{\mathcal{O}}(\sqrt{T}/S^{2})$. Which is by far the best regret bound for finite discounted Markov Decision Process to our knowledge. Numerical results proves the efficiency and superiority of our approach.
• Abstract（参考訳）: 基礎となる環境の状態遷移行列が未知のままである有限割引マルコフ決定過程における探索と搾取のトレードオフ問題を考える。 このような問題を解決するために、二重トンプソンサンプリング強化学習アルゴリズム(DTS)を提案する。 このアルゴリズムは$\tilde{\mathcal{o}}(d\sqrt{sat})$\footnote{the symbol $\tilde{\mathcal{o}}$ means $\mathcal{o}$ with log factors ignore} in time horizon $t$ with $s$ states, $a$ action and diameter $d$ という完全な後悔を実現できる。 DTSは2つの部分から構成されており、第1部は従来の部分であり、先行分布に基づいて遷移行列に後続サンプリング法を適用する。 第2部では,局所的最適動作と長期的最適動作のバランスをとるために,カウントベースの後続更新法を用いて,大域的最適ゲーム値を求める。 我々は$\tilde{\mathcal{O}}(\sqrt{T}/S^{2})$の後悔の限界を確立した。 これは、有限割引のMarkov Decision Processが私たちの知識に課した最大の後悔である。 数値的な結果は、我々のアプローチの効率と優越性を証明します。

関連論文リスト

• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
  論文  参考訳（メタデータ） (2022-05-23T17:59:18Z)
• On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error [18.19398247972205]
  我々は、少なくとも$n$の成分を持つ、おそらく異なる質量の2つの測度の間の不均衡最適輸送(UOT)について研究する。 UOT問題に対する$varepsilon$-approximateの解を求めるために,GEM-UOT(Gradient Extrapolation Method)に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-08T03:22:39Z)
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition [49.78053380710322]
  我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。 最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。 本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
  論文  参考訳（メタデータ） (2021-06-08T05:46:35Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)

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

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