論文の概要: Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games

• arxiv url: http://arxiv.org/abs/2411.06069v1
• Date: Sat, 09 Nov 2024 05:03:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-12 14:11:11.668224
• Title: Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games
• Title（参考訳）: 繰り返し競技における平均リワードRLのモデル選択と実用性最大化への応用
• Authors: Alireza Masoumian, James R. Wright,
• Abstract要約: 平均報酬RL設定のためのオンラインモデル選択アルゴリズムを提案する。 モデル選択の追加コストは、モデルクラスの数である$M$でのみ線形にスケールすることを示す。 また,学習者の後悔度を低く抑えることで,$m*$への指数的依存が避けられないことを示す。
• 参考スコア（独自算出の注目度）: 1.9161424760743742
• License:
• Abstract: In standard RL, a learner attempts to learn an optimal policy for a Markov Decision Process whose structure (e.g. state space) is known. In online model selection, a learner attempts to learn an optimal policy for an MDP knowing only that it belongs to one of $M >1$ model classes of varying complexity. Recent results have shown that this can be feasibly accomplished in episodic online RL. In this work, we propose $\mathsf{MRBEAR}$, an online model selection algorithm for the average reward RL setting. The regret of the algorithm is in $\tilde O(M C_{m^*}^2 \mathsf{B}_{m^*}(T,\delta))$ where $C_{m^*}$ represents the complexity of the simplest well-specified model class and $\mathsf{B}_{m^*}(T,\delta)$ is its corresponding regret bound. This result shows that in average reward RL, like the episodic online RL, the additional cost of model selection scales only linearly in $M$, the number of model classes. We apply $\mathsf{MRBEAR}$ to the interaction between a learner and an opponent in a two-player simultaneous general-sum repeated game, where the opponent follows a fixed unknown limited memory strategy. The learner's goal is to maximize its utility without knowing the opponent's utility function. The interaction is over $T$ rounds with no episode or discounting which leads us to measure the learner's performance by average reward regret. In this application, our algorithm enjoys an opponent-complexity-dependent regret in $\tilde O(M(\mathsf{sp}(h^*) B^{m^*} A^{m^*+1})^{\frac{3}{2}} \sqrt{T})$, where $m^*\le M$ is the unknown memory limit of the opponent, $\mathsf{sp}(h^*)$ is the unknown span of optimal bias induced by the opponent, and $A$ and $B$ are the number of actions for the learner and opponent respectively. We also show that the exponential dependency on $m^*$ is inevitable by proving a lower bound on the learner's regret.
• Abstract（参考訳）: 標準的なRLでは、学習者は、構造(例えば状態空間)が知られているマルコフ決定プロセスの最適ポリシーを学習しようとする。 オンラインモデル選択において、学習者は、M>1$モデルクラスの1つに属することのみを知って、MDPの最適ポリシーを学習しようとする。 近年の研究では、オンラインRLで実現可能であることが示されている。 本研究では,平均報酬RL設定のためのオンラインモデル選択アルゴリズムである$\mathsf{MRBEAR}$を提案する。 アルゴリズムの後悔は、$\tilde O(M C_{m^*}^2 \mathsf{B}_{m^*}(T,\delta))$ ここで、$C_{m^*}$は最も単純で特定されたモデルクラスの複雑さを表し、$\mathsf{B}_{m^*}(T,\delta)$は対応する後悔境界である。 この結果は、平均報酬 RL において、オンラインRL と同様に、モデル選択の追加コストは、モデルクラスの数である$M$でのみ線形にスケールすることを示している。 我々は,2人のプレイヤーが同時に繰り返し行うゲームにおいて,学習者と対戦者の相互作用に$\mathsf{MRBEAR}$を適用する。 学習者の目標は、相手の実用性を知らずにその実用性を最大化することである。 インタラクションは、エピソードや割引のない$T$ラウンド以上で、平均的な報酬後悔によって学習者のパフォーマンスを測定する。 本手法では,M(M(\mathsf{sp}(h^*) B^{m^*} A^{m^*+1})^{\frac{3}{2}} \sqrt{T})$, $m^*\le M$は相手の未知のメモリ限界であり,$\mathsf{sp}(h^*)$は相手が引き起こす最適バイアスの未知のスパンであり,$A$と$B$は学習者のアクションの数である。 また,m^*$に対する指数的依存は,学習者の後悔度を下げることによって必然的であることを示す。

関連論文リスト

• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  我々はMassartノイズの存在下でのオンライン学習の課題について検討する。 計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。 我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-05-21T17:31:10Z)
• Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes [21.77276136591518]
  我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。 シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
  論文  参考訳（メタデータ） (2023-06-28T17:43:19Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• Model Selection with Near Optimal Rates for Reinforcement Learning with General Model Classes [27.361399036211694]
  有限地平線エピソディック強化学習(RL)問題に対するモデル選択の問題に対処する。 モデル選択フレームワークでは、$mathcalP*$の代わりに、遷移カーネルのネストされたファミリーが$M$を与えられる。 textttARL-GENが$TildemathcalO(d_mathcalE* H2+sqrtd_mathcalE* mathbbM* H2T)$の後悔を得ることを示す。
  論文  参考訳（メタデータ） (2021-07-13T05:00:38Z)
• Near-optimal Representation Learning for Linear Bandits and Linear RL [41.33483293243257]
  私たちはまず、次元が$d$の線形バンディットを同時に$M$で演奏する設定を考えます。 これらの包帯は、$k$-次元線型表現を共有するので、$kll d$ と $k ll M$ が成り立つ。 我々は、共有表現を利用して$tildeO(MsqrtdkT + dsqrtkMT )を後悔するサンプル効率のアルゴリズムMTLR-OFULを提案する。
  論文  参考訳（メタデータ） (2021-02-08T11:11:53Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Model-Based Reinforcement Learning with Value-Targeted Regression [48.92439657407732]
  我々は、遷移モデル $P$ が既知のモデルの族 $mathcalP$ に属する有限水平エピソード RL に焦点を当てる。 線形混合の特別な場合において、後悔束は $tildemathcalO(dsqrtH3T)$ という形を取る。
  論文  参考訳（メタデータ） (2020-06-01T17:47:53Z)

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

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