論文の概要、ライセンス

# (参考訳) 測定可能なモンテカルロ探索誤差境界 [全文訳有]

Measurable Monte Carlo Search Error Bounds ( http://arxiv.org/abs/2106.04715v1 )

ライセンス: CC BY 4.0
John Mern, Mykel J. Kochenderfer(参考訳) モンテカルロプランナーは、無限サンプルの極限に収束することが保証されているとしても、しばしば準最適作用を返すことができる。 既知の漸近的後悔の境界は、探索の終了時に推奨される行動の信頼度を測定する手段を提供しない。 本研究では,非定常バンドイットとマルコフ決定過程に対するモンテカルロ推定の準最適性の境界を証明した。 これらの境界は探索の終了時に直接計算することができ、真の作用値の知識を必要としない。 表される境界は、軽収束条件を満たす一般モンテカルロ解法に対して成り立つ。 単純解法とモンテカルロ木探索の双方に対して,マルチアームバンディットの実験と離散マルコフ決定過程により,境界の密度を実証的に検証する。

Monte Carlo planners can often return sub-optimal actions, even if they are guaranteed to converge in the limit of infinite samples. Known asymptotic regret bounds do not provide any way to measure confidence of a recommended action at the conclusion of search. In this work, we prove bounds on the sub-optimality of Monte Carlo estimates for non-stationary bandits and Markov decision processes. These bounds can be directly computed at the conclusion of the search and do not require knowledge of the true action-value. The presented bound holds for general Monte Carlo solvers meeting mild convergence conditions. We empirically test the tightness of the bounds through experiments on a multi-armed bandit and a discrete Markov decision process for both a simple solver and Monte Carlo tree search.
公開日: Tue, 8 Jun 2021 22:20:14 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
Measurable Monte Carlo Search Error Bounds 測定可能なモンテカルロ探索誤差境界 0.69
Department of Aeronautics and Astronautics Department of Aeronautics and Astronautics 航空宇宙学科 航空宇宙学科 0.51
Mykel J. Kochenderfer† マイケル・J・コヘンダーフェル 0.31
Stanford University Stanford, CA 94305 スタンフォード大学スタンフォード, ca 94305 0.57
mykel@stanford.edu mykel@stanford.edu 0.78
John Mern∗ Stanford University Stanford, CA 94305 ジョン・メルン* スタンフォード大学スタンフォード, ca 94305 0.56
jmern91@stanford.edu jmern91@stanford.edu 0.67
1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] I A . s c [ 8 【私】 A! sc [ 0.65
1 v 5 1 7 4 0 1 v 5 1 7 4 0 0.85
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Abstract Monte Carlo planners can often return sub-optimal actions, even if they are guaranteed to converge in the limit of infinite samples. 概要 モンテカルロプランナーは、無限サンプルの極限に収束することが保証されているとしても、しばしば準最適作用を返すことができる。 0.54
Known asymptotic regret bounds do not provide any way to measure confidence of a recommended action at the conclusion of search. 既知の漸近的後悔の境界は、探索の終了時に推奨される行動の信頼度を測定する手段を提供しない。
訳抜け防止モード: 既知の漸近的後悔境界はいかなる方法も提供しない 検索の終了時に推奨行動の信頼度を測定すること。
0.76
In this work, we prove bounds on the sub-optimality of Monte Carlo estimates for non-stationary bandits and Markov decision processes. 本研究では,非定常バンドイットとマルコフ決定過程に対するモンテカルロ推定の準最適性の境界を証明した。 0.65
These bounds can be directly computed at the conclusion of the search and do not require knowledge of the true action-value. これらの境界は探索の終了時に直接計算することができ、真の作用値の知識を必要としない。 0.66
The presented bound holds for general Monte Carlo solvers meeting mild convergence conditions. 表される境界は、軽収束条件を満たす一般モンテカルロ解法に対して成り立つ。 0.58
We empirically test the tightness of the bounds through experiments on a multi-armed bandit and a discrete Markov decision process for both a simple solver and Monte Carlo tree search. 単純解法とモンテカルロ木探索の双方に対して,マルチアームバンディットの実験と離散マルコフ決定過程により,境界の密度を実証的に検証する。 0.68
1 Introduction Monte Carlo (MC) methods are powerful tools for solving decision problems when environment dynamics are not fully known. 1 はじめに モンテカルロ法(MC)は、環境力学が完全には分かっていないときに、意思決定問題を解決する強力なツールである。 0.65
Monte Carlo solvers sample experiences from a generative model of the environment to estimate the values different actions. モンテカルロ解法は、異なるアクションの値を推定するために、環境の生成モデルから経験をサンプリングする。 0.71
On and off-policy solvers based on Monte Carlo sampling have been proposed for single-step and sequential decision problems [1]. モンテカルロサンプリングに基づく一段階および逐次決定問題に対して, オン・オフ・ポリシーソルバが提案されている。 0.66
Monte Carlo tree search (MCTS) is a planning method for Markov decision processes (MDPs) that uses MC sampling to build a search tree over possible trajectories of states and actions. モンテカルロ木探索 (monte carlo tree search, mcts) は、マルコフ決定過程 (mdps) の計画手法であり、mcサンプリングを用いて状態や動作の可能性のある軌道上に探索木を構築する。
訳抜け防止モード: モンテカルロ木探索(MCTS)はマルコフ決定過程(MDP)の計画手法である MCサンプリングを使用して、可能な状態と動作の軌跡の上に検索ツリーを構築する。
0.87
MCTS has been a critical component of several recent advances in sequential decision making and reinforcement learning [2], [3]. MCTSは、シーケンシャルな意思決定と強化学習における最近のいくつかの進歩の重要な要素である[2],[3]。 0.73
Recent work has explored integration of MCTS in self-driving vehicle systems [4], [5]. 最近の研究は、MCTSの自動運転車システムへの統合について検討している[4], [5]。 0.67
Despite the popularity of MC methods, practical understanding of their behavior remains limited. MC法の人気にもかかわらず、その行動の実践的理解は依然として限られている。 0.56
Monte Carlo solvers typically select actions to sample according to a non-stationary search policy that converges during search to the optimal policy. モンテカルロソルバーは通常、最適方針の探索中に収束する非定常探索ポリシーに従ってサンプルのアクションを選択する。 0.79
For many MC algorithms, regret and convergence rate bounds have been defined in terms of unknown parameters of the true action value distributions and asymptotic solver behavior in the limit of infinite samples [1]. 多くのMCアルゴリズムにおいて、後悔と収束率の境界は、真の作用値分布の未知のパラメータと無限サンプルの極限における漸近的解法挙動 [1] で定義される。 0.87
For example, the upper confidence tree (UCT) MCTS algorithm, has known bounds on the probability of several different measures of error defined in terms of the difference between the converged Monte Carlo estimate and the true action value [6]. 例えば、上位信頼木 (UCT) MCTS アルゴリズムは、収束したモンテカルロの推定値と真の作用値 [6] との差で定義されるいくつかの異なる誤差尺度の確率に関する既知の境界を持つ。 0.81
While these expressions provide understanding of the general behavior of this algorithm, they cannot generally be calculated. これらの表現は、このアルゴリズムの一般的な振る舞いの理解を提供するが、一般には計算できない。 0.69
The non-stationary payout distributions encountered during search make defining general error bounds with finite samples difficult. 探索中に遭遇する非定常ペイアウト分布は有限サンプルの一般誤差境界を定義するのを困難にする。 0.70
Monte Carlo solvers reduce the expected error due to bias in the baseline policy at the cost of expected error from sample variance [7]. モンテカルロ・ソルバは、サンプル分散[7]から期待される誤差を犠牲にして、ベースラインポリシーのバイアスによる期待誤差を低減します。 0.68
Expected variance error tends to decrease with the number of samples. 期待分散誤差はサンプル数で減少する傾向がある。 0.77
Sampling enough experience is critical to ensuring an accurate value estimate and action recommendation. 十分な経験をサンプリングすることは、正確な価値見積とアクションレコメンデーションを保証するために重要です。 0.53
Many Monte Carlo algorithms are run online with arbitrary, heuristic stopping conditions such as reaching a sample limit. 多くのモンテカルロアルゴリズムは、サンプル限界に達するような任意のヒューリスティックな停止条件でオンラインで実行される。 0.72
Results from such solvers do not provide a meaningful このような解法の結果は意味をなさない 0.71
∗PhD Candidate, Stanford Intelligent Systems Laboratory †Associate Professor, Stanford Intelligent Systems Laboratory *PhD Candidate, Stanford Intelligent Systems Laboratory, Stanford Intelligent Systems Laboratory, Asociate Professor, Stanford Intelligent Systems Laboratory 0.77
Preprint. Under review. プレプリント。 レビュー中。 0.63
英語(論文から抽出)日本語訳スコア
measure of confidence on the returned estimates. 返却された見積の信頼度の測定。 0.63
Monte Carlo search using informative baselines, for example a policy trained with reinforcement learning, can introduce excess variance error to the baseline, resulting in worse performance. 情報ベースラインを用いたモンテカルロ探索、例えば強化学習で訓練されたポリシーは、ベースラインに過剰な分散エラーをもたらし、結果としてパフォーマンスが低下する。 0.75
Finite-sample error bounds can provide a more principled stopping criteria for Monte Carlo search. 有限サンプル誤差境界はモンテカルロ探索のより原理的な停止条件を与えることができる。 0.64
In this work, we present empirical bounds on error probability for general Monte Carlo solvers. 本研究では,モンテカルロ一般解の誤差確率に関する経験的境界について述べる。 0.69
The proposed bound limits the probability that an action recommended by a convergent Monte Carlo search is worse than any other action considered in the search by a given margin. 提案する境界は、収束モンテカルロ探索によって推奨される動作が与えられたマージンによる探索で考慮される他の動作よりも悪い確率を制限する。 0.78
A corollary bound limits the probability that an action value estimate overestimates the true value by more than a given margin. 従属境界は、アクション値推定が真の値を所定のマージン以上過大に見積もる確率を制限する。 0.73
These bounds can be applied to any Monte Carlo method solving a non-stationary bandit problem or MDP that satisfys mild convergence conditions. これらの境界は、穏やかな収束条件を満たす非定常バンディット問題(MDP)を解くモンテカルロ法にも適用できる。 0.73
Unlike previously known bounds, the presented bounds can be numerically calculated at any point during search using known, empirical values. 既知境界とは異なり、提示された境界は既知の経験値を用いて探索中の任意の点で数値計算することができる。 0.58
They can then be used as a confidence measure for the returned recommendations or as a principled stopping criteria. その後、返却されたレコメンデーションの信頼度尺度や、原則化された停止基準として使用できる。
訳抜け防止モード: 返却されたレコメンデーションの信頼度尺度として使用できる。 または 原則的に停止基準として
0.67
Numerical experiments tested the tightness of the bounds on a multi-armed bandit and a discrete action space MDP. 数値実験では、マルチアームのバンディットと離散的なアクション空間 MDP 上の境界のきつくさを検証した。
訳抜け防止モード: マルチ武装バンディットにおける境界のきつくさに関する数値実験 そして、離散アクション空間 MDP である。
0.72
A simple, fixed-depth Monte Carlo sampler was tested on both problems and UCT-MCTS was additionally tested on the MDP. 両問題に対して単純な固定深度モンテカルロサンプリング装置を試験し, MDPではUTT-MCTSを試験した。 0.72
We examined the effect of various problem and solver configurations on bound tightness. 各種問題と解法の構成が拘束剛性に及ぼす影響について検討した。 0.57
Results show that the bounds generally hold with the bound gap decreasing with sample count. 以上の結果から, 境界は, 試料数とともに有界ギャップが減少する傾向が認められた。 0.56
2 Related Work Multi-armed bandit problems have been extensively studied by the statistics and learning communities [8]. 2 関連作業 マルチアームのバンディット問題は,統計と学習コミュニティによって広く研究されてきた [8]。 0.74
Many algorithms have been proposed to approximately solve the bandit problem and foundational algorithms, such as UCB1, have been extensively studied [9]. 帯域幅問題の解法として多くのアルゴリズムが提案され, UCB1 などの基礎アルゴリズムが広く研究されている[9]。 0.85
Similarly, many MCTS methods have been proposed to solve MDPs, with UCT being a well-studied foundational algorithm [6]. 同様に、多くのMCTS法が MDP を解くために提案されており、UDT はよく研究された基礎アルゴリズム [6] である。 0.67
Since their introduction, these algorithms have had several convergence guarantees and non-asymptotic performance bounds proved, often in terms of the true action value or other unknown parameters. 導入以来、これらのアルゴリズムはいくつかの収束保証と、真のアクション値や他の未知のパラメータの観点から証明された非漸近性能境界を持つ。 0.70
As new Monte Carlo algorithms are developed, the theoretical performance analysis similar to these foundational works tends to be presented [10]. 新しいモンテカルロアルゴリズムが開発されるにつれて、これらの基礎研究と同様の理論的性能解析が提示される傾向がある [10]。 0.79
Much of the analysis to-date has focused on the behavior of specific algorithms. これまでの分析の多くは、特定のアルゴリズムの振る舞いに焦点を当ててきた。 0.58
Shah, Xie, and Xu [10] present non-asymptotic analysis of UCT with improved regret-bounds, and additionally propose a modified, fixed-depth tree search with policy-improvement guarantees. Shah, Xie, Xu [10] は,UTTの非漸近的解析を行い,また,政策改善の保証を施した修正,固定深度木探索を提案する。 0.76
Similarly, James, Konidaris, and Rosman [11] analyze the effects of value function smoothness and baseline policies on UCT. 同様に、James, Konidaris, Rosman [11] は、値関数の滑らかさとベースラインポリシーが UCT に与える影響を分析する。 0.79
Prior work in statistical analysis of random processes provide foundational measures toward generally applicable non-asymptotic bounds. 確率過程の統計解析における先行研究は、一般に適用可能な非漸近境界に対する基礎的な措置を提供する。 0.54
Several prior works develop empirical Bernstein-type bounds based on sample variance. いくつかの先行研究はサンプル分散に基づく経験的ベルンシュタイン型境界を開発する。 0.52
Early work proved bounds for sums of independent, identically distributed random random variables based on sample mean and variance [12], [13]. 初期の研究は、サンプル平均と分散 [12], [13] に基づいて、独立で同一に分布するランダム変数の和の有界性を証明した。 0.80
Further work extended these ideas to functions over martingales [14], [15] with some restrictions. 更なる研究により、これらのアイデアはいくつかの制限付きでmartingales [14], [15] 上の関数に拡張された。 0.53
This work draws on the insights of these analyses to develop the proposed empirical bounds. この研究は、これらの分析の洞察に基づいて提案された経験的境界を開発する。
訳抜け防止モード: この研究はこれらの分析の洞察を 実験的な限界を 発展させるためです
0.70
3 Empirical Monte Carlo Bounds 3つのモンテカルロ境界 0.58
This section presents bounds on the sub-optimality of a Monte Carlo search. この節はモンテカルロ探索の準最適性に関する境界を示す。 0.66
The bound applies to searches over multi-armed bandits with non-stationary payout distributions and Markov decision problems (MDPs). この境界は、非定常的なペイアウト分布とマルコフ決定問題(MDPs)を持つ多武装帯の探索に適用される。 0.58
The bounds hold for any Monte Carlo method meeting the following two convergence conditions. 境界は以下の2つの収束条件を満たす任意のモンテカルロ法に対して成り立つ。 0.67
Convergence Conditions 1. Solver Convergence: The expected value of the search policy increases with the number of 収束条件 1. Solver Convergence: 検索ポリシーの期待値は,数の増加とともに増加する 0.80
searches, such that E[V n] ≥ E[V m] for n ≥ m. 2. n ≥ m に対して e[v n] ≥ e[v m] となるように探索する。 0.80
Positive Search Bias: The search samples actions with higher values more often, such that E[T (ai)] ≥ E[T (aj)], where T (a) gives the number of times a was sampled and Q(s, ai) ≥ Q(s, aj). E[T (ai)] ≥ E[T (aj)] では、T (a) がサンプリングされた回数と Q(s, ai) ≥ Q(s, aj) が与えられる。
訳抜け防止モード: ポジティブ検索バイアス : より高い値のアクションをより頻繁にサンプリングする検索バイアス E[T ( ai ) ] ≥ E[T ( aj ) ] T ( a ) は A がサンプリングされた回数を与えます そして Q(s , ai ) ≥ Q(s , aj ) である。
0.83
For MDPs, we additionally assume that the search simulates trajectories from a given starting state s to some potentially variable depth h and uses a baseline estimator to bootstrap the value of the MDPの場合、探索は与えられた開始状態sから潜在的に可変な深さhへの軌跡をシミュレートし、ベースライン推定器を用いて値のブートストラップを行う。 0.73
2 2 0.85
英語(論文から抽出)日本語訳スコア
remaining trajectory. Many bandit-based Monte Carlo Tree search solvers, such as the popular UCT [6] algorithm have been shown to satisfy these conditions. 残り軌道だ 一般的なUTT[6]アルゴリズムのような帯域幅に基づくモンテカルロ木探索解法は,これらの条件を満たすことが示されている。 0.65
We can define the set of actions considered in the Monte Carlo search to be a subset of the complete action space AT ⊆ A. モンテカルロ探索において考慮された作用の集合を、完全な作用空間 AT > A の部分集合として定義することができる。 0.61
The set of samples for action ai ∈ AT is represented as Ci ← ( ¯Q(1) , . 作用 ai ∈ AT に対するサンプルの集合は、Ci > ( , Q(1) , , ) と表される。 0.69
. . , ¯Q(n) ). . . と、Q(n) である。 0.81
The value estimate of action ai is then ¯Qi = 1|Ci| ¯qi. すると、作用 ai の値の見積もりは yQi = 1|Ci| yqi となる。 0.57
It is assumed that the sample values are bounded by some non-zero constant a almost surely as | ¯Q(k) Theorem 1. サンプル値は、ある非零定数 a で有界であると仮定し、ほぼ確実に | sq(k) の定理 1 と仮定する。 0.66
Let a Monte Carlo solver satisfy the convergence conditions for a problem with sample values bounded by b. モンテカルロソルバは、b で有界なサンプル値を持つ問題に対する収束条件を満たす。 0.64
For a search that returns action value estimates over two actions ¯Qi − ¯Qj = δ, the probability that the true optimal action value gap Qi − Qj ≤ − is no greater than 作用値を返す探索において、2つの作用について推定すると、真の最適作用値ギャップ Qi − Qj ≤ − がそれ以上の確率は存在しない。 0.78
| ≤ a ∀ i, k. は a ≤ i, k である。 0.64
(cid:80) ¯q∈Ci (cid:80) シュカーチ 0.50
i i i (1) 私は 私は 私は (1) 0.61
(2) The variance term is defined for bounded random variables as (2) 分散項は有界確率変数に対して定義される 0.82
exp + α (cid:17) (cid:16)−ninj(|δ +  − ζi − ζj|+)2 (cid:33)2 (cid:114)− ln α exp + α (cid:17) (cid:16)−ninj(|δ + シュイ − ジジ|+)2 (cid:33)2 (cid:114)− ln α 0.84
i + nj ˆσ2,α i + nj >σ2,α 0.82
2(ni ˆσ2,α 2(ni >σ2,α) 0.71
(cid:32) ) (cid:32) ) 0.82
j ˆσ2,α ← b2 j ~σ2,α ~ b2 0.74
n − 1 1 2 V n − 1 1 2 V 0.85
n + 1 b (cid:88) n + 1b (cid:88) 0.80
1 |Ci| where Vn is the sample variance over n samples and b is the sample range. 1 |Ci| Vn は n 個のサンプル上のサンプル分散であり、b はサンプル範囲である。 0.77
Taking the minimum of eq. eq の最小値を取る。 0.82
(4) over α gives the tightest bound. (4) 上の α は最も強い束縛を与える。 0.76
In the bandit setting, the bias term ζ ← 0, since the values are sampled directly from the true distributions. バンドイット設定では、値が真の分布から直接サンプリングされるため、バイアス項は「0」となる。 0.78
In the MDP setting, the error bound term ζ in corollary 1.1 is defined as MDP設定では、行数 1.1 の誤差境界項 > が定義される。 0.76
k ζ = γHk U k k ζ = γHk~Uk 0.87
(3) where k indexes the samples of Ci, Hk is the depth of the Monte Carlo rollout, γ ∈ [0, 1] is a discount k is an upper bound on the error of the baseline value estimate at the end of the trajectory. 3) k が ci のサンプルをインデックスし、hk がモンテカルロのロールアウトの深さ、γ ∈ [0, 1] がディスカウント k が軌道の最後に推定される基準値の誤差の上界である。 0.61
factor, and U k ← max(Qmax − ˆQk, ˆQk − Qmin), where ˆQk is the value of the baseline estimate at At worst, U the end of the trajectory k. The error is zero for trajectories reaching termination. 係数, および >U k > max(Qmax − >Qk, >Qk − Qmin) ここで >Qk は、最悪の場合、軌道 k の終点において基底線推定値である。
訳抜け防止モード: 因子, および >Uk > max(Qmax − >Qk, >Qk − Qmin ) ここでは、-Qk は、最悪の場合、ベースライン推定値である。 軌道 k の終点において、この誤差は終点に達する軌道に対してゼロである。
0.78
The presented bound is entirely empirical and requires no knowledge of unobserved parameters to compute. 提示された境界は完全に経験的であり、計算する未観測パラメータの知識は必要ない。 0.61
Intuitively, it provides a limit on how likely it is that action considered in a Monte Carlo search is better than another action with a higher estimated value. 直観的には、モンテカルロ探索で考慮される動作は、推定値の高い他のアクションよりも優れているという可能性の限界を与える。 0.73
The bound does not provide general guarantees on action optimality, for example in problems with continuous action spaces. 境界は、例えば連続作用空間の問題において、作用の最適性に関する一般的な保証を提供しない。 0.65
As can be seen, the probability decays exponentially with the number of trajectories sampled for the given action. ご覧の通り、確率は与えられた作用のためにサンプリングされた軌道の数で指数関数的に減少する。 0.60
For MDPs, the search-bias decreases with the depth H of each trajectory sample as γH. MDPの探索バイアスは各軌道試料の深さHをγHとして減少させる。 0.77
A useful corollary to corollary 1.1 gives the probability that an estimated action value is overestimated by more than  ≥ 0. 1.1への有用なコローナリーにより、推定されたアクション値が ~ ≥ 0 で過大評価される確率が与えられる。 0.69
Like theorem 1, the inequality of corollary 1.1 can be calculated using only known empirical values. 定理1のように1.1の非等式は既知の経験値のみを用いて計算できる。 0.62
Corollary 1.1. Let a Monte Carlo solver satisfy the convergence conditions for a problem with sample values bounded by b. 定員1.1。 モンテカルロソルバは、b で有界なサンプル値を持つ問題に対する収束条件を満たす。 0.55
For a search that returns action value estimate ¯Qi = qi, the probability that the true optimal action value is overestimated as ¯Qi − Qi ≥  is no greater than 作用値推定値 qi = qi を返す探索に対して、真の最適作用値が qi − qi ≥ として過大評価される確率はそれ以上ではない。 0.79
(cid:16)−ni(| − ζi|+)2 (cid:16)−ni(|)−i|+)2 0.70
(cid:17) exp (cid:17) exp 0.82
2ˆσ2,α i + α 2ˆσ2,α 私は + α 0.69
(4) where ni is the number of trajectories sampling ai, ˆσ2,α is an upper bound on the value variance with significance level α ∈ (0, 1), and ζ is an upper bound on the expected bias of the baseline value estimate. (4) i をサンプリングするトラジェクトリの数を ni とすると、sσ2,α は重要度 α ∈ (0, 1) の値分散上の上界であり、s はベースライン値推定の期待バイアス上の上界である。 0.76
|x|+ represents the max(0, x) function. x|+ は最大(0, x) 関数を表す。 0.87
Equation (4) only provides a meaningful bound for  > 0. 方程式 (4) は > 0 に対して有意な有界のみを与える。 0.74
3.1 Proofs This section provides a proof of theorem 1, which also proves corollary 1.1, which can be shown to be a special case. 3.1 証明 この節は定理 1 の証明を提供しており、特別な場合として示せる1.1 も証明している。 0.68
We first present several lemmas. 我々はまずいくつかの補題を提示する。 0.42
The first lemma presents a bound on the difference in expected error of action value estimates generated by a Monte Carlo search. 第1の補題はモンテカルロ探索によって生成された行動値推定の予測誤差の差に制限を与える。 0.77
3 3 0.85
英語(論文から抽出)日本語訳スコア
Lemma 1. Given a convergent Monte Carlo search over an MDP returning estimates ¯Qi and ¯Qj and true action values Qj ≥ Qi, the expected error is レマ1号。 収束モンテカルロ探索がmdpの帰納推定値 qi と qj と真作用値 qj ≥ qi 上で与えられると、期待誤差は期待される。 0.64
E[ ¯Qi − Qi] − E[ ¯Qj − Qj] ≤ 1 |Ci| E[ >Qi − Qi] − E[ >Qj − Qj] ≤ 1 |Ci| 0.90
γHk 0 k − 1 |Cj| γHk=0。 k − 1 |Cj| 0.65
γHl 0 l (5) γHl=0l (5) 0.78
where k and l index the samples of Ci and Cj respectively, and 0 estimate at the end of the trajectory. ここで、k と l はそれぞれ Ci と Cj のサンプルを指数付けし、軌道の終点における =0 を推定する。 0.69
i is the expected error of the baseline iはベースラインの期待誤差です 0.55
(cid:88) k (cid:88) k 0.82
(cid:88) l (cid:88) うーん 0.62
A proof of lemma 1 is given in section 3.3. 補題1の証明は、セクション3.3で与えられる。 0.66
The next lemma shows that an appropriate upper bound on the conditional likelihood of an estimator of an unknown parameter is also an upper bound on a probability of the parameter. 次の補題は、未知パラメータの推定器の条件付き可能性に関する適切な上限もパラメータの確率上の上限であることを示している。 0.77
Lemma 2. parameter with variance ¯σ2. 補題 2. ばらつきのあるパラメータ。 0.68
If the probability Let θ be a population parameter and let ¯θ be a potentially biased estimator of that もしその確率が θ を人口パラメータとし、θ をその偏りのある推定子とする。 0.77
P (¯θ ≥ a | θ = b) ≤ c(¯σ2) P( sθ ≥ a | θ = b) ≤ c( sσ2) 0.95
where c(¯σ2) is a function that increases monotonically with ¯σ2, then the inequality c( >σ2) は >σ2 で単調に増加する関数で、不等式は 0.73
P (θ ≥ b | ¯θ = a) ≤ c(¯σ2) P (θ ≥ b | >θ = a) ≤ c( >σ2) 0.95
also holds. Lemma 2 follows from the Bayesian Cramér-Rao inequality [16], [17], which, for appropriate priors, implies でもある。 Lemma 2はBayesian Cramér-Raoの不等式 [16], [17] から導かれる。
訳抜け防止モード: でもある。 Lemma 2 は Bayesian Cramér - Rao inequality [ 16 ] から続く。 [17 ] は、適切な事前のために、意味する
0.64
(8) for distributional parameter θ, estimator ¯θ, and data X. (8) 分布パラメータθ, 推定子θ, およびデータxについて。 0.88
The final lemma bounds the true variance of an expectation estimator around the sample variance. 最終補題は、サンプル分散の周りの期待推定子の真の分散を束縛する。 0.68
Lemma 3. Let ¯X = 1 n ¯σ2. 第3弾。 X = 1 n >σ2 とする。 0.57
Given a estimate ¯x = 1 n is bounded as x = 1 n の見積もりが与えられたとき、有界である 0.62
(cid:80)n i Xi be an estimator of the mean over n random variables with variance i (xi − ¯x)2, the variance (cid:80)n i Xi は、分散 i (xi − sx)2 を持つ n 個の確率変数の平均推定子である。 0.80
(cid:80)n (cid:80)n i xi ∼ Xi and sample variance Vn = 1 (cid:80)n (cid:80)n i xi > Xi and sample variance Vn = 1 0.94
Var[θ | X] ≤ Var[¯θ | X] Var[θ | X] ≤ Var[ >θ | X] 0.90
n (9) where b = maxi xi − mini xi is the range of the sample values and α ∈ (0, 1) is a significance level. n (9) ここで、b = maxi xi − mini xi はサンプル値の範囲であり、α ∈ (0, 1) は有意レベルである。 0.85
Lemma 3 follows from the sample variance penalty for empirical Bernstein bounds stated in theorem 10 of the work by Maurer and Pontil [12]. lemma 3 は、maurer と pontil [12] による業績の定理 10 に記載された経験的バーンスタイン境界に対するサンプル分散のペナルティから従う。 0.71
n − 1 n + V n − 1 n + V 0.85
¯σ2 ≤ b2 n ~σ2 ≤ b2 n 0.69
1 b 1 2 (cid:114)− ln α 1b 1 2 (cid:114)−lnα 0.78
(cid:33)2 (cid:32) (cid:33)2 (cid:32) 0.81
(6) (7) (10) (11) (12) (13) (6) (7) (10) (11) (12) (13) 0.85
(14) (15) 3.2 Proof of Theorem 1 (14) (15) 3.2 定理の証明 1 0.83
Proof. The proof begins by constructing a bound on the likelihood of search results as 証明。 証明は、検索結果の可能性の限界を構築することから始まる。 0.66
P(cid:0) ¯Qi − ¯Qj ≥ δ | Qj − Qi = (cid:1) =P(cid:0) ¯Qi − ¯Qj − E(cid:2) ¯Qi − ¯Qj =P(cid:0) ¯Qi − ¯Qj − E(cid:2) ¯Qi − ¯Qj ≤P(cid:0) ¯Qi − ¯Qj − E(cid:2) ¯Qi − ¯Qj ≤P(cid:0) ¯Qi − ¯Qj − E(cid:2) ¯Qi − ¯Qj p(cid:0) sqi − sqj ≥ δ | qj − qi = p(cid:0) = p(cid:0) sqi − sqj − e(cid:2) sqi − sqj = p(cid:0) sqj − e(cid:2) sqi − sqj ≤p(cid:0) sqi − sqj − e(cid:0) sqi − sqj ≤p(cid:0) sqi − sqj ≤p(cid:0) sqi − e(cid:0) sqi − sqj − e(cid:2) sqi − sqj ≤p(cid:0) sqi − sqj ≤p(cid:0) 0.35
(cid:3) ≥ δ − E(cid:2) ¯Qi − ¯Qj (cid:3)(cid:1) (cid:3) ≥ δ +  − E(cid:2) ¯Qi − Qi (cid:3) ≥ δ +  − (cid:88) (cid:3) ≥ δ +  − (cid:88) (cid:3) ≥ δ − E(cid:2) > Qi − > Qj (cid:3) (cid:3) (cid:3) ≥ δ + > − E(cid:2) > Qi − Qi (cid:3) ≥ δ + > − (cid:88) (cid:3) ≥ δ + > − (cid:88) 0.80
i∈Chi γHi0 伊東Chi γHi-0 0.41
γHiU i∈Chi γHi-U 伊東Chi 0.42
(cid:3) + E(cid:2) ¯Qj − Qj (cid:88) i − (cid:88) (cid:3) + e(cid:2) ,qj − qj (cid:88) i − (cid:88) 0.79
j∈Chj i + γHj 0 j jjchj i + γHj =0 j 0.68
(cid:3)(cid:1) (cid:1) (cid:1) (cid:3)(cid:1)(cid:1 )(cid:1) 0.72
γHj U j j∈Chj γHj >U j jjchj 0.58
where the conditional dependence term is omitted after eq. 条件依存という用語は eq後に省略されます 0.75
(10) for clarity. (10)明快である。 0.62
The inequality of eq. (13) follows from lemma 1. eqの不平等。 (13) は lemma 1 から従う。 0.71
The expected baseline estimator error 0 is not generally known, though its magnitude can be limited by a term U ≥ |0|. 期待されたベースライン推定誤差は一般には分かっていないが、その大きさは項 su ≥ |0| によって制限される。 0.57
Since the bound on error magnitude is applied symmetrically, the probability is only bounded by the worst case, resulting in eq. 誤差等級の境界は対称的に適用されるので、確率は最悪の場合のみ有界であり、結果として eq となる。 0.70
(14). We can use this term to construct a Chernoff-Hoeffding inequality bounding the sub-optimality as (14). この用語を使って、準最適性を束縛したチャーンオフ・ホッフィング不等式を構成できる。 0.68
P(cid:0)Qj − Qi ≥  | ¯Qi − ¯Qj = δ(cid:1) ≤ exp P(cid:0)Qj − Qi ≥ . . | . Qi − . Qj = δ(cid:1) ≤ exp 0.84
(cid:16)−2ninj(|δ +  − ζ|+)2 (cid:16)−2ninj(|δ+)2 0.92
(cid:17) ni ¯σ2 (cid:17) ニテ二 0.61
i + nj ¯σ2 j i + nj >σ2 j 0.77
4 4 0.85
英語(論文から抽出)日本語訳スコア
where ¯σ2 gives the variance of the value estimators. ここで σ2 は値推定子の分散を与える。 0.68
We apply the inequality of eq. eqの不等式を適用する。 0.63
(15) to bound the sub-optimality by applying lemma 2. (15) を補題 2 を適用して部分最適性に束縛する。 0.67
By applying the variance upper bound of lemma 3 to eq. 補題3の分散上限を eq に適用することにより。 0.72
(15) with the union bound, we arrive at ≤ exp (15) 結合が有界であれば ≤ exp に到達します 0.82
(cid:16)−2ninj(|δ +  − ζ|+)2 (cid:16)−2ninj(|δ+)2 0.92
(cid:17) + α (cid:17) + α 0.82
(16) ni ˆσ2,α (16) 対訳 σ2,α 0.69
i + nj ˆσ2,α i + nj >σ2,α 0.82
j which concludes the proof. j 証明を結論づけます 0.71
Corollary 1.1 can be proved for action ai by applying the above procedure to the special case where the values of aj are known to be 0. aj の値が 0 である特別の場合に対して、上記の手順を適用することで、作用 ai に対して1.1 を証明できる。 0.68
3.3 Proof of Lemma 1 3.3 Lemma 1 の証明 0.79
Proof. Define φ to be a policy that follows the Monte Carlo sampling strategy until a depth h and then follows the optimal policy. 証明。 φ を深さ h までモンテカルロサンプリング戦略に従うポリシーと定義し、その後最適なポリシーに従う。 0.65
Using this policy, we can define the expected error of an action value estimate to be このポリシーを用いて、期待されるアクション値の推定誤差を定義することができる。 0.77
¯vi − Qi E[ ¯Qi − Qi] = E(cid:104) 1 (cid:88) = E(cid:104) 1 (cid:88) γHiE(cid:104) (cid:88) (cid:88) 阿vi-Qi E[ >Qi − Qi] = E(cid:104) 1 (cid:88) = E(cid:104) 1 (cid:88) γHiE(cid:104) (cid:88) (cid:88) 0.66
i∈Ch i∈Ch i∈Ch イ・Ch イ・Ch イ・Ch 0.41
1 n = n n (cid:105) (cid:105) 1n = n n (cid:105)(cid:105) 0.81
(cid:105) = (cid:105) = 0.82
1 n i∈Ch γHi0 1n イ・Ch γHi-0 0.53
i + E[Qφ i − Qi] i + E[Qφ] i − Qi] 0.85
¯vi − Qφ i シュヴィ - Qφ 私は 0.63
+ E[Qφ i − Qi] +E[Qφ] i − Qi] 0.82
(ˆvi − vi) + E[Qφ (阿vi-vi) +E[Qφ] 0.76
i − Qi] (17) i − Qi] (17) 0.85
(18) (19) (20) (18) (19) (20) 0.85
(24) where vi and ˆvi are the true and estimated values at the end of the sample trajectory, respectively. (24) ここで、vi と svi はそれぞれサンプル軌道の終端の真の値と推定値である。 0.79
Intuitively, this is a decomposition of the expected error to the error of the baseline estimator and the expected error caused by the Monte Carlo sampling procedure. 直観的には、これはモンテカルロサンプリング手順によって生じる期待誤差とベースライン推定器の誤差と期待誤差の分解である。 0.69
Under the Monte Carlo convergence conditions, the negative sampling bias decays in expectation with increased samples and higher value actions are sampled more frequently, giving モンテカルロ収束条件下では、サンプルの増加と高い値作用により期待される負のサンプリングバイアス崩壊がより頻繁にサンプリングされ、それによって得られる。 0.66
(21) for Qj ≥ Qi. (21) qj ≥ qi について。 0.76
Using the definition in eq. eq の定義を使います。 0.84
(20) and the inequality in eq. (20) と eq の不等式 0.61
(21), we can write the difference in the expected error terms as (21) 期待誤差項の違いを次のように書くことができる。 0.82
0 ≥ E[Qφ j − Qj] ≥ E[Qφ 0 ≥ E[Qφ] j − Qj] ≥ E[Qφ] 0.91
i − Qi] E[ ¯Qi − Qi] − E[ ¯Qj − Qj] = i − Qi] E[ >Qi − Qi] − E[ >Qj − Qj] = 0.87
γHj 0 j + E[Qφ γHj =0 j + E[Qφ] 0.74
i − Qi] − E[Qφ i − Qi] − E[Qφ] 0.95
j − Qj] γHj 0 j j − Qj] γHj =0 j 0.78
(22) (23) (cid:88) ≤ (cid:88) (22) (23) (cid:88) ≤ (cid:88) 0.83
i∈Chi i∈Chi 伊東Chi 伊東Chi 0.41
i − (cid:88) i − (cid:88) i − (cid:88) i − (cid:88) 0.86
j∈Chj j∈Chj jjchj jjchj 0.49
γHi0 γHi0 γHi-0 γHi-0 0.42
which concludes the proof. 4 Experiments 証明を結論づけます 4つの実験 0.61
Experiments were conducted to evaluate the tightness of the presented bounds. 提案する境界の厳密性を評価する実験を行った。 0.70
We tested two problems: a simple multi-armed bandit and a grid-world MDP. 単純なマルチアームバンディットとグリッドワールドMDPの2つの問題を検討した。 0.60
We calculated the bounds under various conditions using a simple Monte Carlo estimator for both problems. 両問題を簡易モンテカルロ推定器を用いて種々の条件下で計算した。 0.70
For the MDP, we also tested MCTS with upper confidence tree (UCT) sampling. MDPでは,高信頼木(UCT)サンプリングによるMCTS試験も行った。 0.74
All testing was done in the Julia language using the POMDPs.jl framework [18]. すべてのテストは、POMDPs.jlフレームワーク[18]を使用して、Julia言語で実施された。 0.64
Minimization of the α terms in the bounds was done with Nelder-Meade optimization [19]. 境界におけるα項の最小化はnelder-meade optimization [19] によって行われた。 0.74
Each trial, the Monte Carlo solver draws n samples of actions from a discrete distribution over the complete action space. モンテカルロ解法は各試行において、完全な作用空間上の離散分布からn個の作用のサンプルを抽出する。 0.74
Distribution weights for each action wi are calculated from the softmax over the value estimates as 各アクションwiに対する分布重みは、値推定値よりもソフトマックスから算出される。 0.71
(cid:80) wi ← exp ¯Qiτ−1 i exp ¯Qiτ−1 (cid:80) wi は exp の Qiτ−1 i のexp の Qiτ−1 0.61
5 5 0.85
英語(論文から抽出)日本語訳スコア
(a) (b) Figure 1: Bandit Results: Figure (a) shows the error probability for the bandit problem. (a) (b) 図1: バンディットの結果: 図(a)は、バンディット問題のエラー確率を示しています。 0.82
Figure (b) shows the sub-optimality probability for the same. 図 (b) は、同じ部分最適化確率を示す。 0.83
In both figures, the x-axis gives the total number of samples in the search. どちらの図でも、x軸は検索中のサンプルの総数を与える。 0.74
Solid lines show the mean bound with one standard-error bars, and the dashed lines show the true values. 固形線は1つの標準エラーバーとの平均値を示し、破線は真の値を示す。 0.72
Curves for high and low payout variance are shown. 高ペイアウト分散と低ペイアウト分散の曲線を示す。 0.68
where τ is a temperature parameter, which was set to 10 for experiments in this work. ここでτは温度パラメータであり、実験のために10に設定された。 0.82
Actions that have not yet been sampled have qi ← ∞. 標本化されていない作用は qi ∞ である。 0.61
In the MDP setting, after sampling the first action, the remaining actions are selected according to an -greedy baseline policy, up to a specified depth h. Source code for the experiments is provided in the supplementary materials. MDP設定では、第1の動作をサンプリングした後、上記補助材料に実験用ソースコードを付与し、所定の深さhまで、残りの動作を選択する。
訳抜け防止モード: mdp設定では、第1のアクションをサンプリングした後、残余のアクションは−greedyベースラインポリシーに従って選択される。 補助材料には、所定の深さhまで実験用ソースコードが設けられている。
0.65
4.1 Multi-Armed Bandit 4.1マルチアームバンディット 0.57
The bandit problem had 10 arms, each with a Gaussian payout distribution. バンディット問題には10本の腕があり、それぞれにガウスの支払い分布があった。 0.52
The tests were run in episodes, with each episode having differently parameterized distributions. テストはエピソードで行われ、各エピソードは異なるパラメータ化された分布を持つ。 0.67
The payout mean values were sampled from a uniform distribution on [−1, 1]. 支払平均値は[−1, 1]上の均一分布からサンプリングされた。 0.77
Each payout distribution had the same variance σ2 each episode. 各配当分布は各エピソードで同じ分散σ2を有する。 0.74
To test the bound performance under low and high variance, runs were conducted with with payout variance set to 0.5 and 0.75. 低分散・高分散条件下でのバウンド性能をテストするために, 負荷分散を0.5, 0.75に設定した。 0.68
The bandit expected payouts were estimated with the Monte Carlo solver for varying numbers of samples n. For each episode, the error probability bound was calculated for the two actions with the highest estimated values. モンテカルロ解法を用いて,各エピソード毎に,最大推定値の2つの動作に対して誤差確率を算出した。
訳抜け防止モード: モンテカルロ・ソルバを用いて,各エピソード毎のサンプル数nを推定した。 推定値が最も高い2つの動作に対して誤差確率を計算した。
0.62
The sub-optimality bound was calculated for the best action for each sampling level and variance. 各サンプリングレベルとばらつきに対する最良の作用について, 準最適境界を算出した。 0.66
The margin was  = 0.1 for both experiments. 両実験のマージンは % = 0.1 であった。 0.64
We calculated the true rates of error and sub-optimality in excess of  across episodes. 各エピソードのエラー率とサブオプティマティリティを、全エピソードで s 以上で計算した。 0.50
The average upper bound calculated for each trial and one standard error bounds are plotted along with the true rate curves in fig. 試行ごとに算出された平均上限値と1つの標準誤差値とを、図中の真のレート曲線と共にプロットする。 0.73
1. The x-axis plots the total number of samples for the the search, not necessarily the samples over the measured action. 1. x軸は探索のためのサンプルの総数をプロットするが、必ずしも測定された動作上のサンプルをプロットする必要はない。
訳抜け防止モード: 1. x軸は、探索のためのサンプルの総数をプロットする。 必ずしも測定された行動の サンプルではない
0.84
As can be seen, both the error and sub-optimality bounds decay exponentially with the number of samples drawn. このように、誤差と準最適境界は、引き出されたサンプルの数と指数関数的に崩壊する。 0.67
The bound is fairly loose with a low number of samples, but decays exponentially and reaches near 0 gap at approximately 10,000 samples. 境界は低いサンプル数でかなり緩く、指数関数的に崩壊し、約10,000のサンプルで0の差近くに達する。 0.78
Higher payout variance increases both the true rates and the upper bound values for the error probability and sub-optimality. 高いペイアウト分散は、誤差確率と準最適性の真のレートと上限値の両方を増加させる。 0.74
4.2 Gridworld MDP 4.2 gridworld mdp 0.63
In the gridworld MDP task, an agent is required to navigate through a discrete, 2D world from a random initial position to a goal destination. グリッドワールドMDPタスクでは、エージェントがランダムな初期位置からゴール目的地までの離散的な2次元世界をナビゲートする必要がある。 0.74
There are two goal locations generating positive rewards of 10 and 3, and two penalty locations giving negative rewards of -10 and -5. 10と3の2つのゴールポイントと10と5の負の報酬を与える2つのペナルティポイントがある。 0.68
The episode terminates when the agent reaches any of the four reward-generating locations. このエピソードは、エージェントが4つの報酬発生場所のいずれかに到達すると終了する。 0.56
Each step, the agent takes an action to attempt to move in one of the four cardinal directions. 各ステップでは、エージェントは4つの基数方向の1つを移動させようとするアクションを取る。 0.74
The agent successfully moves in the intended direction with a probability of 0.7 and moves randomly otherwise. エージェントは0.7の確率で意図した方向に動き、ランダムに動かない。 0.74
The grid tested was 10 × 10. 試験対象は10×10。 0.55
The time discount was set to γ = 0.95. 時間割引は γ = 0.95 に設定された。 0.74
We used offline value iteration to learn a baseline policy and approximate optimal action values. オフラインの値を反復してベースラインポリシーを学習し、最適なアクション値を近似しました。
訳抜け防止モード: オフラインの値の反復を使って ベースラインポリシーと近似最適動作値とを学習する。
0.72
The offline solver terminated after an update step with a Bellman residual less than 10−6. オフラインソルバは、ベルマン残量10−6未満の更新ステップの後に終了する。 0.70
The simple Monte Carlo solver used an -greedy baseline policy select actions after the initial step. 単純なモンテカルロソルバは、最初のステップの後に、基本方針選択アクションを使用していた。 0.64
The bootstrap value estimates were generated by the baseline policy with additive uniform noise bounded between [−0.1, 0.1]. ブートストラップ値の推定値は, [-0.1, 0.1] 間に一様雑音を付加した基本方針により生成した。 0.64
We ran the tests with the solver searching to depths of 5, 10, and 25. 調査では,5,10,25の深さを探索した。 0.53
As with the bandit bandit (複数形 bandits) 0.57
6 6 0.85
英語(論文から抽出)日本語訳スコア
problem, we calculated the error and sub-optimality rates for the top performing actions. 問題として,上位行動に対する誤り率と準最適率を算出した。 0.65
The results are shown in fig. 結果は図に示されています。 0.72
2. (a) (b) 2. (a) (b) 0.85
Figure 2: Gridworld Simple MC Results: Figure (a) shows the error probability for the gridworld MDP with a simple MC solver. 図2: Gridworld Simple MC Results: Figure (a) は単純なMCソルバでグリッドワールドMDPのエラー確率を示す。 0.80
Figure (b) shows the sub-optimality probability for the same. 図 (b) は、同じ部分最適化確率を示す。 0.83
In both figures, the x-axis gives the total number of samples in the search. どちらの図でも、x軸は検索中のサンプルの総数を与える。 0.74
Solid lines show the mean bound with one standard-error bars, and the dashed lines show the true values. 固形線は1つの標準エラーバーとの平均値を示し、破線は真の値を示す。 0.72
Curves for searches to depth 5, 10, and 25 are shown. 深度5、10、25への探索曲線が示される。 0.62
As with the bandit results, both the error and sub-optimality bounds decay exponentially with the number of samples drawn. banditの結果と同様に、エラーとサブオプティリティの境界は、サンプルの数で指数関数的に減少する。 0.67
At low samples, the bounds are tighter for the MDP than for the bandit problem, due to the higher true error rates. 低いサンプルでは、真のエラー率が高いため、境界はバンドイット問題よりもmdpの方が厳密である。 0.62
Conversely, at 10,000 samples, the bounds are not as tight. 逆に、1万のサンプルでは、境界はそれほど厳密ではない。 0.50
The effects of leaf-node error are shown by the trends in the search depth, with deeper searches tending to produce tighter bounds as a result of the reduction of the magnitude of the ζ terms. リーフノード誤差の影響は探索深度の傾向によって示され、より深い探索は項の大きさの縮小の結果より厳密な境界を生み出す傾向がある。 0.66
We tested the tightness of the bounds on the popular MCTS-UCT algorithm, using the MCTS.jl implementation. 我々は、MCTS.jl実装を用いて、一般的なMCTS-UCTアルゴリズムにおける境界の厳密性を検証した。
訳抜け防止モード: MCTS-UTTアルゴリズムにおける境界の厳密性を検証した。 MCTS.jl の実装を使用する。
0.62
We tested the performance with max depth was set to 5, 10, and 25 steps for each search. 1回の検索で最大深度を5,10,25ステップに設定した。
訳抜け防止モード: 最大深度を5に設定してパフォーマンスをテストしました。 検索1回につき10ステップ25ステップ。
0.71
The UCT exploration constant was set to 1.0. UCT探査定数は1.0に設定された。 0.68
As with the simple solver, leaf node values were estimated by the baseline policy with additive uniform noise. 簡易解法と同様に,一様雑音を伴うベースラインポリシーにより葉ノード値を推定した。 0.75
The results are shown in fig. 結果は図に示されています。 0.72
3. The same trends can be observed in the MCTS results as in the simple Monte Carlo search results, however, the bounds are significantly looser at high sample counts in the MCTS tests. 3. MCTSの結果はモンテカルロの単純な検索結果と同様の傾向を示すが,MCTS試験では高試料数では境界が著しく緩くなっている。 0.79
This is likely due to the influence of several shallow searches early in the search leading to higher magnitude ζ terms. これは探索の初期にいくつかの浅い探索が影響し、より等級の語に繋がったためと考えられる。 0.60
In both results, the sample count of the action with the highest estimated value tended to be much higher than that of the second-highest. いずれの結果も,最も推定値の高いアクションのサンプル数は,第2位のアクションよりも遥かに高い傾向にあった。 0.80
These results suggest several adaptations to MCTS methods to improve expected error bounds. これらの結果から,MCTS法へのいくつかの適応が期待される誤差境界を改善することが示唆された。 0.46
For a given number of samples, tighter error bounds can be achieved when the sample counts of the compare actions are comparable. 与えられたサンプル数に対して、比較アクションのサンプルカウントが同等であれば、より厳密なエラー境界が得られる。 0.74
For situations where accurate action selection from a discrete set is important, this suggests that increased exploration at the end of search may improve error performance. 離散集合からの正確な行動選択が重要である状況では、探索終了時の探索の増加がエラー性能を向上させる可能性がある。 0.80
Deeper searches tend to result in better estimates than shallow searches. 深い検索は、浅い検索よりも良い推定結果をもたらす傾向がある。 0.64
This suggests modifications to either increase search depth or to more heavily weight samples from longer trajectories in the value estimate. これは、探索深度を増加させるか、値推定の長い軌道からより重いサンプルを得るよう修正することを示唆する。 0.65
5 Conclusions In this work, we presented empirical bounds on the error probability for convergent Monte Carlo solvers over non-stationary bandit problems and Markov decision processes. 結論5 本研究では,非定常バンディット問題とマルコフ決定過程に対する収束モンテカルロ解の誤差確率に関する実験的境界について述べる。 0.68
We demonstrated that these bounds hold for a multi-armed bandit and a discrete gridworld MDP. 我々は、これらの境界が多重武装のバンディットと離散グリッドワールド MDP で成り立つことを示した。 0.56
Results showed that the bounds are loose for low sample numbers, but decay exponentially as samples increase. その結果, 低試料数では境界は緩く, 試料の増加とともに指数関数的に崩壊した。 0.63
These bounds can serve as principled stopping criteria for Monte Carlo methods. これらの境界はモンテカルロ法の原理的停止基準として機能する。 0.60
We anticipate that these measures may be especially useful to methods that use an informed baseline such as offline policy improvement and performance verification of safety-critical systems. 我々は,これらの対策が,オフライン政策改善や安全クリティカルシステムの性能検証などの情報ベースラインを利用する手法に特に有用であると予想している。 0.71
The current work only tested these bounds for simple bandits and MDPs. 現在の作業は、単純なバンディットとmdpでこれらの境界をテストしただけだった。 0.47
Future work shall explore their performance in other, more complex tasks such as MCTS for partially observable MDPs [20]. 将来の作業は、部分可観測mdps[20]のためのmctsのような、他のより複雑なタスクでパフォーマンスを探求する。 0.59
7 7 0.85
英語(論文から抽出)日本語訳スコア
(a) (b) Figure 3: Gridworld UCT-MCTS Results: Figure (a) shows the error probability for the gridworld MDP with the UCT-MCTS solver. (a) (b) 図3: グリッドワールド UCT-MCTS 結果: 図aは、UDT-MCTS ソルバを用いたグリッドワールド MDP の誤差確率を示す。 0.82
Figure (b) shows the sub-optimality probability for the same. 図 (b) は、同じ部分最適化確率を示す。 0.83
In both figures, the x-axis gives the total number of samples in the search. どちらの図でも、x軸は検索中のサンプルの総数を与える。 0.74
Solid lines show the mean bound with one standard-error bars, and the dashed lines show the true values. 固形線は1つの標準エラーバーとの平均値を示し、破線は真の値を示す。 0.72
Curves for searches with maximum depth 5, 10, and 25 are shown. 最大深度5,10,25の探索曲線を示す。 0.58
Even with a moderate number of samples, the bounds were sometimes loose. 適度なサンプル数であっても、境界は時々緩くなっていた。 0.60
Future work will look to specialize the general form presented in this work to produce tighter bounds for specific algorithms. 今後の研究は、この研究で提示された一般的な形式を専門化し、特定のアルゴリズムのより厳密な境界を作り出すことを目指している。
訳抜け防止モード: 今後の作業は この研究で提示される一般的な形式を特殊化し、特定のアルゴリズムに対するより厳密な境界を作り出す。
0.59
The current work also only considered arithmetic mean estimators. 現在の研究は算術平均推定器も考慮している。 0.55
Future work will extend the bounds to more general estimators. 今後の作業は、より一般的な推定に限界を広げるでしょう。 0.50
Other forms of the presented bound shall be investigated to provide tighter bounds, possibly with more restrictive conditions. 提示された境界の他の形式は、おそらくより制限のある条件で、より厳密な境界を提供するために調査される。
訳抜け防止モード: 提示された境界の他の形態は,調査される より制限的な条件で、より狭い境界を提供する。
0.59
For example, several prior works have proved variants of the central limit theorem for non-stationary Markov chains [21]–[24]. 例えば、いくつかの先行研究は、非定常マルコフ連鎖 [21]–[24] に対する中心極限定理の変種を証明している。 0.75
Future work will investigate application of this to achieve tighter general bounds through the Berry-Esseen theorem [25], [26]. 今後の研究は、berry-esseen の定理 [25], [26] を通じてより厳密な一般境界を達成するためにこの応用を研究する。 0.59
References [1] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed. R.S. Sutton と A.G. Barto, Reinforcement Learning: An Introduction, 2nd ed を参照。 0.86
MIT Press, 2018, pp. MIT Press 2018年、p。 0.54
141–145. [2] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. P. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, “Mastering the game of go with deep neural networks and tree search,” Nature, vol. 141–145. [2] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. P. Lillicrap, M. Leach, K. Kavukoglu, T. Graepel, D. Hassabis, “Leach, K. Graepel, and D. Hassabis, “Mastering the game with Deep Neural Network and Tree search”, Nature, vol。 0.78
529, no. 7587, pp. 529年。 7587, pp。 0.66
484–489, 2016. 484–489, 2016. 0.84
[3] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. P. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, T. Graepel, and D. Hassabis, “Mastering the game of go without human knowledge,” Nature, vol. D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. P. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, T. Graepel, D. Hassabis, “Mastering the go of go without human knowledge”, Nature, vol. 0.98
550, no. 7676, pp. 550ドルだ 7676, pp。 0.63
354–359, 2017. 354–359, 2017. 0.84
[4] P. Cai, Y. Luo, A. Saxena, D. Hsu, and W. S. Lee, “LeTS-drive: Driving in a crowd by learning P. Cai, Y. Luo, A. Saxena, D. Hsu, W.S. Lee, “LeTS-drive: Driving in a crowd by learn” 0.93
from tree search,” in Robotics: Science and Systems, 2019. と、robotics: science and systems, 2019に書いている。 0.53
[5] C. Paxton, V. Raman, G. D. Hager, and M. Kobilarov, “Combining neural networks and tree search for task and motion planning in challenging environments,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2017. C. Paxton, V. Raman, G. D. Hager, M. Kobilarovは、2017年のIEEE/RSJ International Conference on Intelligent Robots and Systems(IROS)で、“ニューラルネットワークを結合し、課題のある環境でタスクと動作計画のツリー検索”を行った。 0.80
[6] L. Kocsis and C. Szepesvári, “Bandit based Monte-Carlo planning,” in European Conference 6]l. kocsisとc. szepesvári, "bandit based monte-carlo planning" in european conference 0.79
[7] on Machine Learning (ECML), 2006. [7] On Machine Learning (ECML) 2006年。 0.83
J. Audibert, R. Munos, and C. Szepesvári, “Exploration-exploita tion tradeoff using variance estimates in multi-armed bandits,” Theoretical Computational Science, vol. J. Audibert, R. Munos, C. Szepesvári, “Exploration-Exploita tion tradeoff using variance estimates in multi-armed bandits”, Theory Computational Science, vol。 0.89
410, no. 19, pp. 410 だめだ pp. 19。 0.66
1876–1902, 2009. 1876–1902, 2009. 0.84
[8] T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” Advances in 8] t. l. lai and h. robbins, "漸近的に効率的な適応割り当て規則" の進歩 0.82
Applied Mathematics, vol. 6, no. 数学を応用する。 6、ノー。 0.68
1, pp. 4–22, 1985. 1、p。 4–22, 1985. 0.74
[9] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit P. Auer, N. Cesa-Bianchi, P. Fischer, “Finite-time analysis of the multiarmed bandit” 0.86
problem,” Journal of Machine Learning Research, vol. とjournal of machine learning research, vol. は書いている。 0.65
47, no. 2–3, pp. 47だ 2-3, pp。 0.47
235–256, 2002. 235–256, 2002. 0.84
8 8 0.85
英語(論文から抽出)日本語訳スコア
[10] D. Shah, Q. Xie, and Z. Xu, “Non-asymptotic analysis of Monte Carlo tree search,” in Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), 2020, pp. D. Shah, Q. Xie, Z. Xu, “on-asymptotic analysis of Monte Carlo tree search” in Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS, 2020, pp。 0.78
31–32. [11] S. James, G. D. Konidaris, and B. Rosman, “An analysis of Monte Carlo tree search,” in AAAI 31–32. S. James, G. D. Konidaris, B. Rosman, “An Analysis of Monte Carlo tree search” in AAAI 0.74
Conference on Artificial Intelligence (AAAI), 2017, pp. 人工知能学会(AAAI)、2017年。 0.44
3576–3582. 3576–3582. 0.71
[12] A. Maurer and M. Pontil, “Empirical Bernstein bounds and sample-variance penalization,” in 12] a. maurer と m. pontil, in "empirical bernstein bounds and sample-variance penalization" 0.82
Conference on Learning Theory (COLT), 2009. 学習理論会議(COLT)2009年。 0.69
[13] A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. E. Schapire, “Contextual bandit algorithms with supervised learning guarantees,” in International Conference on Artificial Intelligence and Statistics (AISTATS), vol. A. Beygelzimer, J. Langford, L. Li, L. Reyzin, R. E. Schapire, “Contextual bandit algorithm with supervised learning guarantees” in International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 0.82
15, 2011, pp. 2011年15月15日、p。 0.61
19–26. [14] T. Peel, S. Anthoine, and L. Ralaivola, “Empirical Bernstein Inequality for Martingales : 19–26. 14] T. Peel, S. Anthoine, L. Ralaivola, “Empirical Bernstein inequality for Martingales? 0.71
Application to Online Learning,” 2013. 2013年 - オンライン学習科を開設。 0.76
HAL: hal-00879909. HAL: hal-00879909。 0.77
[15] Z. Zhang, J. Yang, X. Ji, and S. S. Du, “Variance-aware confidence set: Variance-dependent bound for linear bandits and horizon-free bound for linear mixture MDP,” Computing Research Repository, 2021. arXiv: 2101.12745. Z. Zhang, J. Yang, X. Ji, S. S. Du, “Variance-aware confidence set: Variance-dependent bound for linear bandits and horizon-free bound for linear mix MDP”, Computing Research Repository, 2021. arXiv: 2101.12745. 0.96
[16] P. Tichavsky, C. Muravchik, and A. Nehorai, “Posterior Cramér-Rao bounds for discrete-time nonlinear filtering,” IEEE Transactions on Signal Processing, vol. P. Tichavsky, C. Muravchik, A. Nehorai, “Posterior Cramér-Rao bounds for discrete-time nonlinear filtering”, IEEE Transactions on Signal Processing, vol。 0.82
46, no. 5, pp. 46、ノー。 5, pp。 0.78
1386–1396, 1998. 1386–1396, 1998. 0.84
[17] E. Aras, K. Lee, A. Pananjady, and T. A. Courtade, “A family of Bayesian Cramér-Rao bounds, and consequences for log-concave priors,” in IEEE International Symposium on Information Theory (ISIT), 2019, pp. E.Aras, K. Lee, A. Pananjady, T. A. Courtade, “A family of Bayesian Cramér-Rao bounds, and results for log-concave priors” in IEEE International Symposium on Information Theory (ISIT), 2019, pp. 0.86
2699–2703. 2699–2703. 0.71
[18] M. Egorov, Z. N. Sunberg, E. Balaban, T. A. Wheeler, J. K. Gupta, and M. J. Kochenderfer, “POMDPs.jl: A framework for sequential decision making under uncertainty,” Journal of Machine Learning Research, vol. M. Egorov, Z. N. Sunberg, E. Balaban, T. A. Wheeler, J. K. Gupta, M. J. Kochenderfer, “POMDPs.jl: シーケンシャルな意思決定のためのフレームワーク。 0.66
18, 26:1–26:5, 2017. 18, 26:1–26:5, 2017. 0.63
J. A. Nelder and R. Mead, “A simplex method for function minimization,” Computer Journal, vol. J。 A. NelderとR. Meadは“関数の最小化のためのシンプルな方法”だ。 0.75
7, no. 4, pp. 7位はノー。 4, pp。 0.75
308–313, 1965. 308–313, 1965. 0.84
[19] [20] D. Silver and J. Veness, “Monte-Carlo planning in large POMDPs,” in Advances in Neural [19] D. Silver and J. Veness, “Monte-Carlo planning in large POMDPs” in Progresss in Neural 0.81
Information Processing Systems (NIPS), 2010. 情報処理システム(NIPS)、2010年。 0.78
[21] A. A. Markov, “Investigations of general experiments connected by a Markov chain,” Collected [21]A。 A. Markov, “Markov鎖で接続された一般実験の研究” 収集 0.78
Works, pp. 465–509, 1951. pp. 作品。 465–509, 1951. 0.74
[22] R. L. Dobrushin, “Central limit theorem for nonstationary Markov chains,” Theory of Proba- 22] r. l. dobrushin, “central limit theorem for nonstationary markov chains” proba- 0.70
bility & Its Applications, vol. 1, no. 能力と応用性。 1・・ 0.44
1, pp. 65–80, 1956. 1、p。 65–80, 1956. 0.74
[23] M. Sinn and B. Chen, “Central limit theorems for conditional Markov chains,” in International 23]m.シンとb.チェン、国際における「条件付きマルコフ連鎖の中央極限定理」 0.74
Conference on Artificial Intelligence and Statistics (AISTATS), 2013, pp. 人工知能・統計学会(aistats)2013年。 0.45
554–562. [24] A. Arlotto and J. M. Steele, “A central limit theorem for temporally nonhomogenous Markov chains with applications to dynamic programming,” Mathematics of Operations Research, vol. 554–562. A. Arlotto と J. M. Steele, “A central limit theorem for temporally nonhomogenous Markov chains with application to dynamic programming”, "Mathematics of Operations Research, vol。 0.74
41, no. 4, pp. 41、ノー。 4, pp。 0.77
1448–1468, 2016. 1448–1468, 2016. 0.84
[25] A. C. Berry, “The accuracy of the Gaussian approximation to the sum of independent variates,” [25]A.C.ベリー,「独立変数の和に対するガウス近似の精度」 0.63
Transactions of the American Mathematical Society, vol. アメリカ数学会(American Mathematical Society)の略。 0.64
49, no. 1, pp. 49、ノー。 1、p。 0.70
122–136, 1941. 122–136, 1941. 0.84
[26] C.-G. Esseen, “On the Liapunoff limit of error in the theory of probability,” Arkiv for matematik, [26]C.-G. Esseen, “On the Liapunoff limit of error in the theory of probability”, Arkiv for matematik, 0.91
astronomi och fysik, A: 1–19, 1942. Astronomi och fysik, A: 1-19, 1942. 0.88
9 9 0.85
                   ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。