論文の概要、ライセンス

# (参考訳) 多重重要度サンプリングによる保守的最適政策最適化 [全文訳有]

Conservative Optimistic Policy Optimization via Multiple Importance Sampling ( http://arxiv.org/abs/2103.03307v1 )

ライセンス: CC BY 4.0
Achraf Azize and Othman Gaizi(参考訳) 強化学習(rl)は,アタリゲームのプレイやgoのゲーム解決といった難しい問題を,統一的なアプローチで解決することができる。 しかし、現代のディープRLアプローチは、まだ現実世界のアプリケーションでは広く使われていない。 理由の1つは、既存の(すでに稼働している)ベースラインポリシーと比較して、中間実行ポリシーのパフォーマンスに対する保証がないことである。 本論文では,政策最適化問題における保守的な探索を解くオンラインモデルフリーアルゴリズムを提案する。 提案されたアプローチの後悔は、離散パラメータ空間と連続パラメータ空間の両方に対して $\tilde{\mathcal{O}}(\sqrt{T})$ で有界であることを示した。

Reinforcement Learning (RL) has been able to solve hard problems such as playing Atari games or solving the game of Go, with a unified approach. Yet modern deep RL approaches are still not widely used in real-world applications. One reason could be the lack of guarantees on the performance of the intermediate executed policies, compared to an existing (already working) baseline policy. In this paper, we propose an online model-free algorithm that solves conservative exploration in the policy optimization problem. We show that the regret of the proposed approach is bounded by $\tilde{\mathcal{O}}(\sqrt{T})$ for both discrete and continuous parameter spaces.
公開日: Thu, 4 Mar 2021 20:23:38 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 r a M 4 ] G L . 1 2 0 2 r a m 4 ] g l である。 0.78
s c [ 1 v 7 0 3 3 0 . s c [ 1 v 7 0 3 3 0 ] である。 0.80
3 0 1 2 : v i X r a 3 0 1 2 : v i X r a 0.85
Conservative Optimistic Policy Optimization via Multiple Importance 複数重要度による保守的最適政策最適化 0.64
Sampling Achraf Azize サンプリング Achraf Azize 0.76
Othman Gaizi achraf.azize@polytec hnique.edu オスマン・ガイジ achraf.azize@polytec hnique.edu 0.47
othman.gaizi@polytec hnique.edu othman.gaizi@polytec hnique.edu 0.59
Ecole Polytechnique Ecole Polytechnique 0.85
Abstract Reinforcement Learning (RL) has been able to solve hard problems such as playing Atari games or solving the game of Go, with an unified approach. 概要 強化学習(Reinforcement Learning, RL)は、アタリゲームや囲碁の問題解決といった難題を統一的なアプローチで解決することができる。 0.60
Yet modern deep RL approaches are still not widely used in real-world applications. しかし、現代のディープRLアプローチは、まだ現実世界のアプリケーションでは広く使われていない。 0.60
One reason could be the lack of guarantees on the performance of the intermediate executed policies, compared to an existing (already working) baseline policy. 理由の1つは、既存の(すでに稼働している)ベースラインポリシーと比較して、中間実行ポリシーのパフォーマンスに対する保証がないことである。 0.73
In this paper, we propose an online model free algorithm that solves conservative exploration in the policy optimization problem. 本稿では,政策最適化問題における保守的探索を解決するオンラインモデルフリーアルゴリズムを提案する。 0.84
We show that the regret of the proposed approach is bounded by ˜O( T) for both discrete and continuous parameter spaces. 提案手法の後悔は,離散パラメータ空間と連続パラメータ空間の両方に対して,o(t) で区切られていることを示す。 0.72
√ 1. Introduction The goal of reinforcement learning (Sutton and Barto, 1998) is to learn optimal policies for sequential decision problems, by optimizing a cumulative future reward signal. √ 1. 序論 強化学習(Sutton and Barto, 1998)の目的は、累積的未来報酬信号の最適化により、逐次決定問題に対する最適ポリシーを学ぶことである。 0.84
Policy optimization (PO) is a class of RL algorithms that models explicitly the policy (behaviour) of an agent as a parametric mapping from states to actions. ポリシー最適化 (PO) は、エージェントのポリシー(振る舞い)を状態から行動へのパラメトリックマッピングとして明示的にモデル化するRLアルゴリズムのクラスである。 0.86
This class is usually suited for continuous tasks, where the states and actions are modeled as real numbers. このクラスは通常、状態と動作が実数としてモデル化される連続的なタスクに適合する。 0.79
While the problem of finding an optimal policy with the least amount of interactions with the environment is very important and has been widely studied in the PO literature, the problem of controlling the performance of the agent during learning is still a challenge. 環境との相互作用を最小限に抑えた最適な政策を見つけるという問題は非常に重要であり、PO文献で広く研究されているが、学習中のエージェントのパフォーマンスを制御する問題は依然として課題である。 0.80
This online policy optimization is extremely relevant when an agent is unable to learn before being deployed to the real world (e.g recommendation system). このオンラインポリシー最適化は、エージェントが現実世界にデプロイされる前に学習できない場合(例えばレコメンデーションシステム)に極めて重要となる。 0.79
In this online setting, the agent needs to trade-off exploration and exploitation while interacting with the environ- このオンライン環境では、エージェントは環境と対話しながら探索と搾取をトレードオフする必要がある。
訳抜け防止モード: このオンライン設定では、エージェントは取引する必要があります。 環境と相互作用する−
0.65
1 ment. The agent is willing to give up rewards for actions improving his knowledge of the environment. 1 メント エージェントは、環境に関する彼の知識を改善する行動に対する報酬を喜んであきらめます。 0.68
Therefore, there is no guarantee on the performance of policies generated by the algorithm, especially in the initial phase where the uncertainty about the environment is maximal. したがって、特に環境の不確実性が最大である初期段階では、アルゴリズムが生成したポリシーの性能を保証することは不可能である。 0.78
This is a major obstacle that prevents the application of RL in domains where hard constraints (e g , on safety or performance) are present. これは、厳格な制約(例えば安全性や性能)が存在するドメインにおけるRLの適用を防止する大きな障害である。 0.77
Examples of such domains are digital marketing, healthcare, finance and robotics. そのような領域の例は、デジタルマーケティング、ヘルスケア、金融、ロボティクスです。 0.66
For a vast number of domains, it is common to have a known and reliable baseline policy that is potentially suboptimal but satisfactory. 膨大な数のドメインに対しては、潜在的に最適だが満足のいく、既知で信頼できるベースラインポリシーを持つことが一般的です。
訳抜け防止モード: 膨大な数のドメインでは 潜在的に最適ではあるが満足できる、既知の信頼性の高いベースラインポリシーを持つ。
0.76
Therefore, for applications of RL algorithms, it is important that are guaranteed to perform at least as well as the existing baseline. したがって、RLアルゴリズムの適用のためには、少なくとも既存のベースラインと同様に実行することが保証されることが重要です。 0.74
This setting has been studied in multi-armed bandits (Wu et al (2016)), and also very well defined in the RL case (Garcelon et al (2020a)). この設定は、マルチアームバンドイット(Wu et al (2016))で研究され、RLの場合(Garcelon et al (2020a))で非常によく定義されている。 0.67
In this paper, we first summarize algorithmic ideas from Papini et al (2019), formalize the problem of Conservative Policy Optimization, propose algorithms that solve this problem in both discrete and compact parameter space and finally show that those algorithms yield a sublinear regret ˜O( 2. 本稿では、まず、Papini et al (2019) のアルゴリズム的アイデアを要約し、保守的政策最適化の問題を形式化し、離散的かつコンパクトなパラメータ空間においてこの問題を解決するアルゴリズムを提案し、最終的にこれらのアルゴリズムがサブ線形後悔(英語版)を生じることを示す。 0.72
Preliminaries 2.1. プリミティブ2.1。 0.57
The Policy Optimization Problem In this section, we will use the same formalisation of policy optimization introduced by Papini et al (2019). 本節の政策最適化問題は、papini et al (2019) によって導入された政策最適化の形式化と同じものである。 0.73
Let X ⊆ Rd be the arm set and (Ω,F , P) a probability space. X {\displaystyle X} を腕集合とし、(X,F , P) を確率空間とする。 0.74
Let {Zx : Ω → Z | x ∈ X} be a set of continuous random vectors parametrized by X , with common sample space Z ⊆ Rm. Zx : Ω → Z | x ∈ X} を X によってパラメトリケートされた連続ランダムベクトルの集合とし、共通サンプル空間 Z を Rm とする。 0.91
We denote with px the probability density function of Zx. px は Zx の確率密度関数を表す。 0.67
Finally, let f : Z → R be a bounded payoff function, and µ(x) = Ez∼px[ f (z)] its expectation under px. 最後に、f : Z → R を有界なペイオフ函数とし、μ(x) = Ez\px[f(z)] を px の下で期待する。 0.84
For each iteration t = 0, . 各反復 t = 0, に対して。 0.77
. . , T , we select an arm xt, draw a sample zt from pxt , and observe payoff f (zt), up to horizon . . , t , アーム xt を選択し, サンプル zt を pxt から描画し, ペイオフ f (zt) を水平線まで観測する。 0.81
T). √ T)。 √ 0.81
英語(論文から抽出)日本語訳スコア
Conservative Optimistic Policy Optimization via Multiple Importance Sampling Nk(cid:88) i=1 Nk(cid:88) i=1の多重値サンプリングによる保守的最適政策最適化 0.62
µ(xt) max x0,...,xT∈X μ(xt) 最大 x0, ..., xT∈X 0.84
Ezt∼pxt [ f (zt)] = max x0,...,xT∈X Ezt\pxt [ f (zt)] = max x0, ...,xT∈X 0.94
Figure 1. The Policy Optimisation problem formalization T(cid:88) H. The goal is to maximize the expected total payoff: t=0 図1。 政策最適化問題の定式化 T(cid:88) H. 目標は、期待される総支払額を最大化することである: t=0 0.69
T(cid:88) (1) t=0 In action-based PO, X corresponds to the parameter space Θ of a class of stochastic policies {πθ : θ ∈ Θ}, set T of possible Z to the trajectories (τ = h=0 R(sh, ah) =(cid:80)H−1 reward R(τ) =(cid:80)H−1 [s0, a0, s1, a1, . T(cid:88) (1) t=0 アクションベース PO において、X は確率的ポリシーのクラス {πθ : θ ∈ s}, 可能な Z の T を軌跡 (τ = h=0 R(sh, ah) = (cid:80)H−1 reward R(τ) = (cid:80)H−1 [s0, a0, s1, a1, , . . .) に対応する。 0.83
. . , sH−1, aH−1]), px to the density pθ over trajectories induced by policy πθ, and f (z) to the cumulated h=0 rh+1. . . sH−1, aH−1]), px はポリシー πθ によって誘導される軌道上の密度 pθ へ、f(z) は累積 h=0 rh+1 へ向けられる。 0.80
In parameter-based PO, X corresponds to the hyperparameter space Ξ of a class of stochastic hyperpolicies {νξ : ξ ∈ Ξ}, Z to the cartesian product Θ × T , px to the joint distribution pξ(θ, τ) := νξ(θ)pθ(τ), and f (z) to the cumulated reward R(τ). パラメータベース po において、x は確率的超政治の類 {ν × t , px に対して直積積 θ × t , px に対して、合同分布 p/(θ, τ) := ν/(θ)pθ(τ), f(z) は累積報酬 r(τ) に対応する。
訳抜け防止モード: パラメータベース po において、x は確率的超政治のクラス { ν\ : \\\\\ } の超パラメータ空間 θ × t に対応し、z はデカルト積 θ × t に対応する。 px からジョイント分布 p\(θ, τ ) : = ν\(θ)pθ(τ ) へ そして f ( z ) を累積報酬 r(τ ) に割り当てる。
0.75
Both cases are summarized in figure 1. どちらのケースも図1にまとめる。 0.67
The peculiarity of this framework, compared to the classic MAB one, is the special structure existing over the arms. この枠組みの特異性は、古典的なMABと比べ、腕の上に存在している特別な構造である。 0.74
In particular, the expected payoff µ of different arms is correlated thanks to the stochasticity of px on a common sample space Z. 特に、異なるアームの期待されたペイオフ μ は、共通のサンプル空間 Z 上の px の確率性により相関する。 0.74
In the following, we will use multiple importance sampling to exploit this correlation and guarantee efficient exploration. 以下に、この相関を利用して効率的な探索を保証するために、複数の重要なサンプリングを行う。 0.56
2.2. Robust Multiple Importance Sampling Estimation Importance sampling is a technique that allows estimating the expectation of a function under some target or proposal distribution with samples drawn from a different distribution, called behavioral. 2.2. ロバスト多重重要度サンプリング推定 重要度サンプリングは、あるターゲットまたは提案分布の下で関数の期待を、異なる分布から抽出されたサンプルで推定する手法である。 0.76
Let P and Q be probability measures on a measurable space (Z,F , such that P (cid:28) Q (i.e., P is absolutely continuous w.r.t. P と Q を測度空間 (Z,F) 上の確率測度とし、P (cid:28) Q (すなわち P は絶対連続 w.r.t である。 0.86
Q). Let p and q be the densities of P and Q, respectively, w.r.t. Q)。 p と q をそれぞれ P と Q の密度、w.r.t とする。 0.79
a reference measure, and the importance q . 参照尺度、および重要度q。 0.55
Given a bounded function f : Z → R, weight ωP/Q = p and a set of i.i.d. 有界函数 f : Z → R が与えられると、重量 ωP/Q = p と i.i.d の集合が与えられる。 0.67
outcomes z1, ..., zN sampled from Q, the importance sampling estimator of µ := Ez∼P[ f (z)] is: N(cid:88) (cid:98)µIS := ωP/Q(zi) f (zi) iid∼Q[(cid:98)µIS ] = µ. i=1 which is an unbiased estimator, i.e., E zi Multiple importance sampling is a generalization of the importance sampling technique which allows samples drawn from several different behavioral distributions to be used for the same estimate. 結果 z1, ..., zN は Q からサンプリングされ、μ := Ez'P[ f (z)] の重要サンプリング推定器は N(cid:88) (cid:98)μIS := ωP/Q(zi) f (zi) iid'Q[(cid:98)μIS ] = μ.i=1 であり、これは偏りのない推定器である。
訳抜け防止モード: 結果 z1, ..., zN は Q からサンプリングされ、μ : = Ez\P [ f ( z ) ] の重要サンプリング推定子は N(cid:88 ) ( cid:98)μIS : = ωP / Q(zi ) f ( zi ) iid\Q[(cid:98)μIS ] = μ. i=1 となる。 E zi 多重重要サンプリングは重要サンプリング手法の一般化である 複数の異なる行動分布から引き出されたサンプルを、同じ推定に使用することができる。
0.88
Let Q1, . . . Q1にしよう。 . . 0.84
, QK be all probability , QK がすべて確率である 0.80
1 N (2) 2 (3) 1N (2) 2 (3) 0.83
(4) 1 N min f (zik) (4) 1N 分 f (複数形 fs) 0.69
˘µBH := K(cid:88) k=1 μBH := K(cid:88) k=1 0.79
1 ˘µIS := N Nk(cid:88) K(cid:88) i=1 k=1 1 μIS := N Nk(cid:88) K(cid:88) i=1 k=1 0.73
measures over the same probability space as P, and P (cid:28) Qk for k = 1, . P と同じ確率空間上の測度と、k = 1 に対する P (cid:28) Qk である。 0.85
. . , K. Given Nk i.i.d. . . , K. given Nk i.i.d. 0.78
samples from each Qk, the Balance Heuristic Multiple Importance Sampling (MIS) estimator is: (cid:98)µBH := (cid:80)K p(zik) j=1 N jq j(zik) which is also an unbiased estimator of µ. 各Qkからのサンプルは、バランスヒューリスティック多重重要サンプリング(MIS)推定器です:(cid:98)μBH := (cid:80)K p(zik) j=1 N jq j(zik)またμの偏りのない推定器です。 0.77
Recently it has been observed that, in many cases of interest, the plain estimators 2 and 3 present problematic tail behaviors, preventing the use of exponential concentration inequalities. 近年, 多くの場合において, 偏差推定器2, 3が問題的テール挙動を示し, 指数関数的濃度不等式の使用を妨げていることが観察されている。 0.68
A common heuristic to address this problem N(cid:88) consists in truncating the weights : min{M, ωP/Q(zi)} f (zi) i=1 where M is a threshold to limit the magnitude of the imporM,  f (zik) tance weight. この問題 n(cid:88) に対処する一般的なヒューリスティックは、重み: min{m, ωp/q(zi)} f (zi) i=1 である。
訳抜け防止モード: この問題に対処する一般的なヒューリスティック(英語版) N(cid:88 ) は、重み付け min{M, ωP / Q(zi ) } f ( zi ) i=1 である。 M は、不規則な M の等級を制限するしきい値であり、tance weight は f ( zik ) である。
0.70
Similarly, for the multiple importance sampling case, restricting to the BH, we have: (cid:80)K p(zik) N j N q j(zik) j=1 Clearly, since we are changing the importance weights, we introduce a bias term, but, by reducing the range of the estimate, we get a benefit in terms of variance. 同様に、BHに制限された多重重要サンプリングケースでは、次のものがあります: (cid:80)K p(zik)N j N q j(zik) j=1 明らかに、重要重みを変更しているので、バイアス項を導入しますが、見積もりの範囲を減らすことで、分散の点で利益を得ます。 0.75
Intuitively, we can allow larger truncation thresholds M as the number of samples N increases. 直感的には、サンプル n の数が増加するにつれて、より大きな切断しきい値 m を許容できる。 0.59
The results from Papini et al (2019) state that, when using an adaptive threshold depending on N, we are able to reach exponential concentration: with at least probability 1 − δ, we have: ˘L(δ) ≤ µ ≤ ˘U(δ) (cid:33) d2(P(cid:107)Φ) log( 2  1 (cid:32)√ with: δ ) ˘U(δ) = ˘µBH + (cid:107) f(cid:107)∞ 2 N (cid:33) d2(P(cid:107)Φ) log( 2  1 (cid:32)√ and δ ) 1 ˘L(δ) = ˘µBH − (cid:107) f(cid:107)∞ 2 2 + N 3 (cid:90) (cid:2)ωP/Φ(z)(cid:3) + 1 (cid:1)2 dΦ = Varz∼Φ (cid:0)ωP/Φ such that: d2(P(cid:107)Φ) = K(cid:88) Z N j Q j is a mixture model Φ = N j=1 (cid:18) Nd2(P(cid:107)Φ) (cid:19) 1 and finally ˘µBH is the truncated balance heuristic estimator 2 with N =(cid:80)K as defined in 5, using Nk i.i.d. The results from Papini et al (2019) state that, when using an adaptive threshold depending on N, we are able to reach exponential concentration: with at least probability 1 − δ, we have: ˘L(δ) ≤ µ ≤ ˘U(δ) (cid:33) d2(P(cid:107)Φ) log( 2  1 (cid:32)√ with: δ ) ˘U(δ) = ˘µBH + (cid:107) f(cid:107)∞ 2 N (cid:33) d2(P(cid:107)Φ) log( 2  1 (cid:32)√ and δ ) 1 ˘L(δ) = ˘µBH − (cid:107) f(cid:107)∞ 2 2 + N 3 (cid:90) (cid:2)ωP/Φ(z)(cid:3) + 1 (cid:1)2 dΦ = Varz∼Φ (cid:0)ωP/Φ such that: d2(P(cid:107)Φ) = K(cid:88) Z N j Q j is a mixture model Φ = N j=1 (cid:18) Nd2(P(cid:107)Φ) (cid:19) 1 and finally ˘µBH is the truncated balance heuristic estimator 2 with N =(cid:80)K as defined in 5, using Nk i.i.d. 0.89
samples from each Qk and MN = j=1 Nk log( 1 δ ) 各QkおよびMN = j=1 Nk log(1 δ )からのサンプル 0.94
2 + 4 3 (5) 2 + 4 3 (5) 0.85
(6) (7) (6) (7) 0.85
英語(論文から抽出)日本語訳スコア
err 翻訳エラー 0.00
英語(論文から抽出)日本語訳スコア
Conservative Optimistic Policy Optimization via Multiple Importance Sampling 多重重要度サンプリングによる保守的最適政策最適化 0.66
1: Input: xb, µb, (δt)T 2: Draw sample z0 ∼ pxb and observe f (z0) t=1 ˇBt ←(cid:80)t−1 3: for t = 1, . 1: Input: xb, μb, (δt)T 2: Draw sample z0 > pxb and observed f (z0) t=1 >Bt >(cid:80)t−1 3: for t = 1, 0.89
. . , T do Select arm xt ∈ arg maxx∈X ˇU(x, δt) 4: i=0 ˇLt(xi, δt) + ˇLt(xt, δt)− (1− α)(t + 1)µ(xb) 5: if ˇBt ≥ 0 then 6: Draw sample zt ∼ pxt and observe f (zt) 7: else 8: Draw sample zt ∼ pxb and observe f (zt) 9: end if 10: 11: end for Algorithm 1: Conservative OPTIMIST . . , t do select arm xt ∈ arg xt ∈ arg maxx ∈ xx su(x, δt) 4: i=0 slt(xi, δt) + slt(xt, δt)− (1− α)(t + 1)μ(xb) 5: if sbt ≥ 0 then 6: draw sample zt s pxt and observe f (zt) 7: else 8: draw sample zt s pxb and observe f (zt) 9: end if 10: 11: end for algorithm 1: end for end for conservative optimist 0.87
that verify that the budget is positif), then take the most optimistic arm from this set. 予算が正当であると確認する) そして、このセットから最も楽観的な腕を取ります。 0.65
This strategy yields more reward while still being conservative. この戦略は保守的である間より多くの報酬をもたらします。 0.59
Figure 2 (taken from Garcelon et al (2020b) ) shows an example to build the intuition for this. 図2(Garcelon et al (2020b)から取得)は、この直感を構築する例を示しています。 0.77
The pseudo-code for it is in Algorithm 2 1: Input: xb, µb, (δt)T 2: Draw sample z0 ∼ pxb and observe f (z0) t=1 ˇBt(x) =(cid:80)t−1 (cid:110) (cid:111) 3: for t = 1, . 擬似コードは、アルゴリズム2 1: 入力: xb, μb, (δt)T 2: サンプルz0を描画し、f(z0) t=1 ×Bt(x) =(cid:80)t−1 (cid:110) (cid:111) 3: for t = 1 である。 0.88
. . , T do i=0 ˇLt(xi, δt)+ ˇLt(x, δt)−(1−α)(t+1)µ(xb) 4: Ct = x ∈ X : ˇBt(x) ≥ 0 5: Select arm xt ∈ arg maxx∈Ct ˇU(x, δt) 6: Draw sample zt ∼ pxt and observe f (zt) 7: 8: end for Algorithm 2: Improved Conservative OPTIMIST . . , T do i=0 >Lt(xi, δt)+ >Lt(x, δt)−(1−α)(t+1)μ(xb) 4: Ct = x ∈ X : >Bt(x) ≥ 0 5: Select arm xt ∈ arg maxx⋅Ct >U(x, δt) 6: Draw sample zt > pxt and observed f (zt) 7: 8: end for Algorithm 2: Improved conservative OPTIMIST 0.88
The optimization step (line 4 in 1 or lines 5 and 6 in 3) may be very difficult when X is not discrete as ˇU(x, δt) is nonconvex and non-differentiable. 最適化ステップ(1 の行 4 または5 の行 6 または 3 の行 6 )は、X が非凸かつ微分不可能であるため X が離散でないときは非常に困難である。 0.80
Global optimization methods could be applied at the cost of giving up theoretical guarantees. グローバルな最適化手法は理論的な保証を放棄するコストで適用できる。 0.82
In practice, this direction may be beneficial, but instead, like proposed by Papini et al (2019), we could adapt to the compact case by using a general discretization method. 実際、この方向は有益かもしれないが、papini et al (2019) が提案したように、一般的な離散化法を用いてコンパクトケースに適応することができた。 0.64
The key intuition is to make the discretization progressively finer. 鍵となる直観は、離散化を徐々に微調整することである。 0.45
The pseudocode for this variant is: 1: Input: xb, µb, (δt)T t=1, discretization schedule (τt)T 2: Draw sample z0 ∼ pxb and observe f (z0) t=1 ˇBt(x) =(cid:80)t−1 3: for t = 1, . 1: Input: xb, μb, (δt)T t=1, discretization schedule (τt)T 2: Draw sample z0 > pxb and observed f (z0) t=1 >Bt(x) = (cid:80)t−1 3: for t = 1, 0.85
. . , T do i=0 ˇLt(xi, δt)+ ˇLt(x, δt)−(1−α)(t+1)µ(xb) (cid:110) (cid:111) 4: Discretize X with a uniform grid ˜Xt of τd t points 5: ˜Ct = x ∈ ˜Xt : ˇBt(x) ≥ 0 6: Select arm xt ∈ arg maxx∈ ˜Ct ˇU(x, δt) 7: Draw sample zt ∼ pxt and observe f (zt) 8: 9: end for Algorithm 3: Improved Conservative OPTIMIST 2 . . , T do i=0 >Lt(xi, δt)+ >Lt(x, δt)−(1−α)(t+1)μ(xb) (cid:110) (cid:111) 4: X を一様格子 >Xt of τd t points 5: >Ct = x ∈ >Xt : >Bt(x) ≥ 0 6: Select arm xt ∈ arg maxx(x, δt) 7: Draw sample zt > pxt and observed f(zt) 8: End for Algorithm 3: Improved Conservative OPTIST 2: 9: End for Algorithm 3: Improved Conservative OPTIST 2: 9: End 0.82
4 ∆t be the total regret with ∆t = 4 t = の完全後悔である。 0.63
Figure 2. The OPTIMIST arm in blue does not satisfy the conservative condition, thus Alogithm 1 will play the basline action. 図2。 青のオプティミズムの腕は保守的な条件を満たさないので、アロジテム1はベースライン作用をする。 0.68
However, arm2 and arm3 are considered ”safe arm” . しかし、arm2とarm3は"safe arm"と見なされている。 0.68
And the Algorithm 2 will choose arm2; which is still conservative, and yields less regret than the baseline (arm chosen by Alogithm 1) Let Regret(T) = (cid:80)T 5. そして、アルゴリズム2はArm2を選びます。これはまだ保守的で、ベースライン(Alogithmによって選択されたアーム)よりも後悔が少なくなります。
訳抜け防止モード: そしてアルゴリズム2は、まだ保守的なarm2を選択する。 ベースラインよりも後悔が少なくなるのです Alogithm 1 (複数形 Alogithm 1s) Regret(T ) = ( cid:80)T 5 とする。
0.73
Regret Analysis µ(x(cid:63)) − µ(xt) and x(cid:63) ∈ arg maxx∈X µ(x). Regret Analysis μ(x(cid:63)) − μ(xt) and x(cid:63) ∈ arg maxx∈X μ(x)。 0.95
i=0 In the following, we will show that Algorithm 1 yields sublinear regret under some mild assumptions (same assumptions as in Papini et al (2019)). i=0 以下では、アルゴリズム1がいくつかの軽度仮定(papini et al (2019) と同じ仮定)の下で部分線形な後悔を与えることを示す。 0.66
The proofs combine techniques from Papini et al (2019) and Wu et al (2016) and are reported in Appendix . この証明はpapini et al (2019) と wu et al (2016) の技術を組み合わせており、付録 で報告されている。 0.61
First, we need the following assumption on the Renyi divergence: Assumption 3. まず、Renyiの発散について以下の仮定が必要である。 0.54
We suppose that the 2-R´enyi divergence is uniformely bounded: sup (cid:80)t−1 x0,...,xT∈X with Φt = 1 k=0 pxk t 5.1. sup (cid:80)t−1 x0, ...,xT∈X は、t = 1 k=0 pxk t 5.1 である。 0.75
Discrete arm set The case of the discrete arm set (|X| = K ∈ N), besides being convenient for the analysis, is also of practical interest: Even in applications where X is naturally continuous (e g , robotics), the set of solutions that can be actually rithm 1 achieves a regret ˜O(cid:16)√ tried in practice may sometimes be constrained to a discrete, reasonably small, set. 離散アーム集合 離散アーム集合 (|X| = K ∈ N) の場合も、解析に便利であるだけでなく、実用上の関心事である: X が自然連続である場合(例えば、ロボット工学)でさえ、実際にリズム 1 となる解の集合は、実際に試みられるような後悔の念 (O(cid:16) は、離散的、合理的に小さい、集合に制約されることがある。 0.75
In this simple setting, AlgoTheorem 4. この簡単な設定では、AlgoTheorem 4 です。 0.67
With probability 1 − δ, Algorithm 1 with con- 確率 1 − δ で、アルゴリズム 1 - con- 0.83
d2(pxt(cid:107)Φt) := v < ∞ d2(pxt(cid:107) ∞) := v* < ∞ 0.83
(16) (cid:17) (16) (cid:17) 0.82
T : T : 0.85
英語(論文から抽出)日本語訳スコア
(17) (18) (20) (21) (cid:105) 1 2 (17) (18) (20) (21) (cid:105) 1 2 0.90
Figure 3. Implementation of OPTIMIST, Conservative OPTIMIST, UCRL, CUCRL on the inventory problem 図3。 在庫問題に対するOPTIMIST, 保守型OPTIMIST, UCRL, CUCRLの実装 0.76
Conservative Optimistic Policy Optimization via Multiple Importance Sampling fidence schedule δt = 6δ t−1(cid:88) t2π2K , satisfies the following: µ(xi) ≥ (1 − α)tµ(xb) ∀t ∈ {1, . 複数の重要度をサンプリングするフィデンススケジュール δt = 6δ t−1(cid:88) t2π2k による保守的楽観的政策最適化は、以下のとおりである。
訳抜け防止モード: 多重要度サンプリングフィデンススケジュールδt = 6δt−1(cid:88 ) t2π2 k による保守的楽観的政策最適化 μ(xi ) ≥ ( 1 − α)tμ(xb ) かつ t ∈ { 1 である。
0.82
. . , T + 1} i=0 √ (cid:107) f(cid:107)∞ ∆b 4KL Regret(T) ≤ ∆b + 2 LT + + αµb αµb (cid:16)√ (cid:16)√ (cid:17) (cid:17) with L = (a + b)2v[2 log(T) + log( π2K 3δ )], a = (cid:107) f(cid:107)∞ and b = (cid:107) f(cid:107)∞ 2 + 1 2 + 4 3 3 √ This yields a ˜O( T) regret. . . cid:107) f(cid:107)∞ = (cid:107) f(cid:107)∞ = (cid:107)f(cid:107)f (cid:107)∞ and b = (cid:107)f(cid:107)∞ 2 + 1 2 + 4 3 \(cid:107)∞ 2 + 1 2 + 4 3 {\displaystyle \cid:16)\ (cid:17) (cid:17) with L = (a + b)2v\[2 log(T) + log(π2K 3δ )], a = (cid:107)f(cid:107)f (cid:107)∞ 2 + 1 2 3 \。
訳抜け防止モード: . . ,t + 1 } i=0 , (cid:107 ) f(cid:107)∞ , b 4kl regret(t ) ≤ ,b + 2 lt + + αμb αμb ( cid:16) , ( cid:17 ) ( cid:17 ) with l = ( a + b)2v][2 log(t ) + log ( π2 k 3δ ) ],,,, a = (cid:107 ) f(cid:107)∞ であり、b = (cid:107 ) f(cid:107)∞ 2 + 1 2 + 4 3 3 である。
0.86
5.2. Compact arm set We consider the more general case of a compact arm set X. 5.2. コンパクトアーム集合 コンパクトアーム集合 X のより一般的な場合を考える。 0.68
We assume that X is entirely contained in a box [−D, D]d, with D ∈ R+. X は D ∈ R+ の箱 [−D, D]d に完全に含まれていると仮定する。 0.88
We also need the following assumption on the expected payoff: Assumption 5. また、期待される報酬について以下の仮定も必要です。 0.53
The expected payoff µ is Lipschitz continuous, i.e., there exists a constant P > 0 such that, for every (cid:12)(cid:12)(cid :12)µ(x) − µ(x(cid:48)) (cid:12)(cid:12)(cid :12) ≤ P (cid:13)(cid:13)(cid :13)x − x(cid:48)(cid:13)(ci d:13)(cid:13)1 x, x(cid:48) ∈ X : (19) (cid:25)d(cid:33) and discretization (cid:32) Theorem 6. 期待のペイオフ μ はリプシッツ連続であり、すなわち、すべての (cid:12)(cid:12)(cid :12)(cid:12)μ(x) − μ(x(cid:48)) (cid:12)(cid:12) ≤ p (cid:13)(cid:13)x − x(cid:48)(cid:13)(ci d:13)(cid:13)(cid:13 )1 x, x(cid:48) ∈ x : (19) (cid:25)d(cid:33) および離散化 (cid:32) 定理 6 に対して、定数 p > 0 が存在する。 0.80
Under Assumptions 3 and 5, Algorithm 3 with (cid:24) (cid:109) (cid:108) 6δ confidence schedule δt = 1 t2π2 t 1+ 2 t 1 guarantees, with probability at least schedule τt = 2 1 − δ: t−1(cid:88) µ(xi) ≥ (1 − α)tµ(xb) ∀t ∈ {1, . 仮定3と5では、 (cid:24) (cid:109) (cid:108) 6δ 信頼スケジュールδt = 1 t2π2 t 1+ 2 t 1 が保証され、少なくとも確率 τt = 2 1 − δ: t−1(cid:88) μ(xi) ≥ (1 − α)tμ(xb) は保証される。 0.81
. . , T + 1} i=0 √ (cid:107) f(cid:107)∞ ∆b 8L(cid:48) Regret(T) ≤ ∆b + 2 L(cid:48)T + (cid:104)(cid:16) (cid:17) + αµb αµb with L(cid:48) = ((a + b)v 1 log(T) + d log(2) + log( π2 2 + d 3δ) 2  2 (cid:16)√ (cid:16)√ (cid:17) (cid:17) +PDd)2 , Algorithm 3 achieves a regret ˜O(cid:16) (cid:17) a = (cid:107) f(cid:107)∞ and b = (cid:107) f(cid:107)∞ 2 + 1 3 √ T d : Unfortunately, the time required for optimization is exponential in arm space dimensionality d. 6. . . cid:107) f(cid:107) ∞ yb 8L(cid:48) Regret(T) ≤ yb + 2 L(cid:48)T + (cid:104)(cid:16) (cid:17) + αμb αμb with L(cid:48) = ((a + b)v 1 log(T) + d log(2) + log(π2 2 + d 3δ) 2 πd:16) ) (cid:16) ) (cid:17) (cid:17) +PDd) 2 , アルゴリズム3は、不動的な空間において、再帰的O(cid:17) +PDd(cid:16) を達成する。
訳抜け防止モード: . . ,T + 1 } i=0 > ( cid:107 ) f(cid:107)∞ >b 8L(cid:48 ) Regret(T ) ≤ >b + 2 L(cid:48)T + ( cid:104)(cid:16 ) ( cid:17 ) + αμb αμb with L(cid:48 ) = ( ( ( a + b)v 1 log(T ) + d log(2 ) + log ( π2 2 + d 3δ ) 2 sh 2 ( cid:16) = ( cid:17 ) (cid:17 ) + PDd)2, アルゴリズム3は (cid:17 ) ( cid:107 ) a = ( cid:107 ) f(cid:107)∞ そして b = ( cid:107 ) f(cid:107)∞ 2 + 1 3 > T d : 残念ながら 最適化に要する時間は 腕の空間次元 d. 6で指数関数的です
0.85
Experiments In this section, we evaluate Algorithm 1 compared to CUCRL (Garcelon et al (2020a)) on the stochastic inventory control problem (Puterman (1994), Sec. 実験 この節では,確率的在庫管理問題 (Puterman (1994), Sec) におけるCUCRL (Garcelon et al (2020a)) と比較してアルゴリズム1を評価する。 0.83
3.2.1): at the beginning of each month t, a manager has to decide the number of items to order (maximum capacity M = 6 in order 3.2.1 毎月の t の初めに、マネージャは注文するアイテムの数(最大容量 M = 6 の順)を決定する必要がある。 0.87
to satisfy a uniform random demand when taking into account ordering and inventory maintenance costs. 順序および在庫の維持費を考慮に入れるとき均一ランダムな要求を満たすため。 0.82
The optimal policy belongs to the set of thresholds policies characterized by parameters (σ, Σ) where Σ is the target stock and σ is the capacity threshold. 最適ポリシーは、パラメータ(σ, Σ)によって特徴づけられるしきい値ポリシーの集合に属し、Σはターゲットストック、σはキャパシティしきい値である。 0.85
As a baseline, we decided to take the threshold policy (σ, Σ) = (4, 4), while the optimal one verifies (σ(cid:63), Σ(cid:63)) = (3, 6). ベースラインとして、しきい値ポリシー (σ, Σ) = (4, 4) をとることに決め、最適の政策は (σ(cid:63), Σ(cid:63)) = (3, 6) を検証する。 0.80
Experiments are run for T = 10000 time steps and a conservative level α = 0.1, and results displayed in figure 3 are averaged over 20 realizations. t = 1000 の時間ステップと保存レベル α = 0.1 の実験が行われ、図 3 で示される結果は20以上の実現を平均する。 0.81
As expected, we can see that the CUCRL algorithm converges a little bit slower than UCRL due to the conservative constraint restricting a free exploration of the environment. 予測されたように、CUCRLアルゴリズムは環境の自由な探索を制限する保守的な制約のため、UCRLよりも少し遅く収束する。 0.77
However, OPO-MIS (Optimistic Policy Optimization with Multiple Importance Sampling) adapted from https://github.com/W olfLo/optimist performs really poorly with a linear regret worse than the baseline. しかし、https://github.com/W olfLo/optimistから適応されたOPO-MIS(Optimistic Policy Optimization with Multiple Importance Sampling)は、ベースラインよりも悪い線形後悔で本当に貧弱に動作します。 0.63
This is essentially explained by the authors choice to design linear actor policies in their implementation of the method which is clearly not suitable for this particularly non-linear inventory problem (as the optimal policy is a threshold one). これは、特に非線形在庫問題(最適なポリシーがしきい値であるため)に明らかに適さない方法の実装において、線形アクターポリシーを設計することを選択する著者によって本質的に説明されます。 0.77
Nonetheless, adding the conservative constraint with COPO-MIS 1 (Conservative Optimistic Policy Optimization with Multiple Importance Sampling) enables to not diverge much from the baseline policy and yields a quite similar regret, showing that the conservative constrain is well respected when using 1, and justifying the necessity to add safety constraints when the learning algorithm (OPTIMIST) fails to find a good policy. それにもかかわらず、COPO-MIS 1(Conservative Optimistic Policy Optimization with Multiple Importance Smpling)に保守的制約を加えることで、基本方針からあまり逸脱せず、また、その保守的制約が1を使用する際によく尊重されていることを示し、学習アルゴリズム(OPTIMIST)が良い政策を見つけられなかった場合に安全的制約を加える必要性を正当化する。 0.77
7. Conclusion In this work, we have studied the problem of conservative exploration in policy optimization using MAB techniques. 7. 結論 本稿では,MAB 技術を用いた政策最適化における保守的探索の問題について検討した。 0.78
We have used algorithmic ideas from Papini et al (2019) to propose an online model free algorithm that solves the papini et al (2019) のアルゴリズムを用いたオンラインモデルフリーアルゴリズムの提案を行った。 0.69
2 + 4 3 5 2 + 4 3 5 0.85
英語(論文から抽出)日本語訳スコア
Conservative Optimistic Policy Optimization via Multiple Importance Sampling 多重重要度サンプリングによる保守的最適政策最適化 0.66
problem of conservative exploration in RL as defined in Garcelon et al (2020a), both the action-based and the parameter-based exploration frameworks, and for both discrete and continuous parameter spaces. Garcelon et al (2020a)で定義されるRLにおける保守的な探索の問題、アクションベースおよびパラメータベースの探索フレームワーク、および離散的および連続的なパラメータ空間の両方について。 0.76
We have proved sublinear regret bounds for Conservative OPTIMIST under assumptions that are easily met in practice. 我々は,実際に容易に達成できる前提条件の下で,保守的OPTIMISTに対するサブ線形後悔境界を証明した。 0.54
The empirical evaluation on the inventory problem showed that the proposed algorithm respect effectively the conservative constraint. 在庫問題に対する実証的な評価により,提案アルゴリズムは保守的制約を効果的に尊重することを示した。 0.63
However, since the parametrization of the policies (linear policies) in the implementation of Papini et al (2019) was not adapted to the inventory case, OPTIMIST failed to reach a good policy. しかしながら、papini et al(2019)の実施における政策(線形政策)のパラメトリゼーションは在庫問題に適応していなかったため、オプティミストは良い政策に到達できなかった。 0.75
Future work should focus on finding more efficient parametrization of the policies in the code implementation, but also ways to perform effectively optimization in the infinite-arm setting. 今後の作業は、コード実装におけるポリシーのより効率的なパラメトリズを見つけることだけでなく、無限アーム設定で効果的な最適化を実行する方法にも焦点をあてるべきである。 0.62
References Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Evrard Garcelon、Mohammad Ghavamzadeh、Alessandro Lazaric、Matteo Pirottaなどを参照。 0.70
Conservative exploration in reinforcement learning. 強化学習における保守的探究 0.67
In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1431–1441. Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Tceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Volume 108 of Proceedings of Machine Learning Research, page 1431–1441 0.87
PMLR, 26–28 Aug 2020a. PMLR 26-28 Aug 2020a。 0.81
URL http://proceedings.m lr.press/ v108/garcelon20a.htm l. URL http://proceedings.m lr.press/ v108/garcelon20a.htm l 0.41
Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Evrard Garcelon、Mohammad Ghavamzadeh、Alessandro Lazaric、Matteo Pirotta。 0.65
Improved algorithms for conservative exploration in bandits, 2020b. 盗賊の保存的探索のためのアルゴリズムの改善。 0.59
Matteo Papini, Alberto Maria Metelli, Lorenzo Lupo, and Marcello Restelli. Matteo Papini、Alberto Maria Metelli、Lorenzo Lupo、Marcello Restelli。 0.67
Optimistic policy optimization via multiple importance sampling. 複数の重要サンプリングによる最適政策最適化。 0.71
In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4989–4999. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, Volume 97 of Proceedings of Machine Learning Research, page 4989–4999. 0.88
PMLR, 09–15 Jun 2019. PMLR, 09-15 Jun 2019 0.90
URL http://proceedings.m lr.press/v97/ papini19a.html. URL http://proceedings.m lr.press/v97/ papini19a.html 0.41
Martin L. Puterman. マーティン・l・プターマン 0.48
Markov Decision Processes: Discrete Stochastic Dynamic Programming. Markov Decision Processes: Discrete Stochastic Dynamic Programming。 0.80
John Wiley & Sons, Inc., New York, NY, USA, 1994. John Wiley & Sons, Inc., New York, NY, USA, 1994。 0.82
ISBN 0471619779. ISBN 04716 19779。 0.88
Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesv´ari. Yifan Wu、Roshan Shariff、Tor Lattimore、Csaba Szepesv ́ari。 0.73
Conservative bandits, 2016. 2016年、保守派。 0.66
6 6 0.85
英語(論文から抽出)日本語訳スコア
Appendix (cid:80)t If the arm is never chosen, Tk(T) = 0 If it i=0 is at least chosen once, let t be the last time xk has been chosen (xk = xt), by 28 we have: 付録 (cid:80)t アームが選択されない場合、Tk(T) = 0 少なくとも一度は i=0 が選択された場合、t を xk が選択された最後の時間 (xk = xt) とします。 0.79
(cid:49)xt=xk. (cid:49)xt=xk。 0.68
A. Proof of Theorem 4 µ(x) ∈(cid:104) ˇLt(x, δt), ˇUt(x, δt) (cid:105) ∀x ∈ X ∀t ∈ {1, . A。 定理の証明 4 μ(x) ∈(cid:104) slt(x, δt), sut(x, δt) (cid:105) sx ∈ x st ∈ {1, 。 0.78
. . , T} Proof. . . , T} 証明。 0.80
With probability 1 − δt : (22) ˇµt(x)−µ(x) ∈(cid:2)−aβt(x, δt), bβt(x, δt)(cid:3) ∀x ∈ X ∀t ∈ {1, . 確率 1 − δt : (22) sμt(x)−μ(x) ∈(cid:2)−aβt(x, δt), bβt(x, δt)(cid:3) で表される。 0.91
. . , T} To ease notation, we will rewrite 22 as: (cid:16)√ (cid:17) (cid:16)√ (cid:17) (cid:19) 1 (cid:18) d2(px(cid:107)Φt) log( 2 with a := (cid:107) f(cid:107)∞ and b := (cid:107) f(cid:107)∞ 2 + 1 2 + 4 and 3 3 δt ) 2 βt(x, δt) := F =(cid:84)K (cid:84)T (cid:8)ˇµt(xk) − µ(xk) ∈(cid:2)−aβt(x, δt), bβt(x, δt)(cid:3)(cid:9) t We take: t=1 k=1 (cid:8)ˇµt(xk) − µ(xk) ∈(cid:2)−aβt(x, δt), bβt(x, δt)(cid:3)(cid:9)  K(cid:91) t2π2K , we have: P(F) With δt = 6δ T(cid:91) = 1 − P T(cid:88) t=1 k=1 ≥ 1 − K T(cid:88) δt t=1 6δ ≥ 1 − K t2π2K t=1 ≥ 1 − δ since(cid:80)T t2 ≤(cid:80)∞ 1 t=1 t=1 If xt is an arm chosen by OPTIMIST, with probability 1− δ we have: : ∆t = µ(x(cid:63)) − µ(xt) ≤ ˇµt(x(cid:63)) + aβt(x(cid:63), δt) − µ(xt)  d2(px(cid:107)Φt) log( 2  1 ≤ ˇµt(xt) + aβt(xt, δt) − µ(xt) 2 ≤ (a + b)βt(xt, δt) = (a + b) 2 log(t) + log( π2K  1 δt t 3δ ) 2 ≤ (a + b)v 1 2 log(T) + log( π2K  1 2  t 3δ ) 2 ≤ (a + b)v (cid:114) 1 2  t L ≤ t with L = (a + b)2v[2 log(T) + log( π2K 3δ )] Now, we will try to find a bound on the number of times a sub-optimal arm k has been chosen till T: Tk(T) = . . , T} To ease notation, we will rewrite 22 as: (cid:16)√ (cid:17) (cid:16)√ (cid:17) (cid:19) 1 (cid:18) d2(px(cid:107)Φt) log( 2 with a := (cid:107) f(cid:107)∞ and b := (cid:107) f(cid:107)∞ 2 + 1 2 + 4 and 3 3 δt ) 2 βt(x, δt) := F =(cid:84)K (cid:84)T (cid:8)ˇµt(xk) − µ(xk) ∈(cid:2)−aβt(x, δt), bβt(x, δt)(cid:3)(cid:9) t We take: t=1 k=1 (cid:8)ˇµt(xk) − µ(xk) ∈(cid:2)−aβt(x, δt), bβt(x, δt)(cid:3)(cid:9)  K(cid:91) t2π2K , we have: P(F) With δt = 6δ T(cid:91) = 1 − P T(cid:88) t=1 k=1 ≥ 1 − K T(cid:88) δt t=1 6δ ≥ 1 − K t2π2K t=1 ≥ 1 − δ since(cid:80)T t2 ≤(cid:80)∞ 1 t=1 t=1 If xt is an arm chosen by OPTIMIST, with probability 1− δ we have: : ∆t = µ(x(cid:63)) − µ(xt) ≤ ˇµt(x(cid:63)) + aβt(x(cid:63), δt) − µ(xt)  d2(px(cid:107)Φt) log( 2  1 ≤ ˇµt(xt) + aβt(xt, δt) − µ(xt) 2 ≤ (a + b)βt(xt, δt) = (a + b) 2 log(t) + log( π2K  1 δt t 3δ ) 2 ≤ (a + b)v 1 2 log(T) + log( π2K  1 2  t 3δ ) 2 ≤ (a + b)v (cid:114) 1 2  t L ≤ t with L = (a + b)2v[2 log(T) + log( π2K 3δ )] Now, we will try to find a bound on the number of times a sub-optimal arm k has been chosen till T: Tk(T) = 0.87
t2 = π2 1 6 . t2 = π2 1 6 . 0.92
(23) (24) (25) (23) (24) (25) 0.85
(26) (27) (28) (26) (27) (28) 0.85
) 2 = = ∆t (29) ) 2 = = ? (29) 0.74
L ∆k Tk(T) ≤ t ≤ L 2 ∆t The regret can be written as: T(cid:88) Regret(T) = T(cid:88) t=0 ∆t + Tb(T)∆b t=1,t∈ST with ST = {t ∈ {1, . 略称は「L」。 tk(t) ≤ t ≤ l 2 {\displaystyle t(cid:88) regret(t) = t(cid:88) t=0\t + tb(t)\b t=1,t)\st with st = {t ∈ {1, } と書くことができる。 0.49
. . , T} : xt (cid:44) xb} the set of times where xb), Tk(T) =(cid:80)T chosen till time T, and Tb(T) =(cid:80)T the OPTIMIST action was chosen (at t=0 we always choose (cid:49)xt=xk the number of times the arm k was t=0 (cid:49)xt=xb the number of t=0 time the baseline arm was chosen till times T. With probability 1 − δ, we have: T(cid:88) (cid:114) ∆t T(cid:88) t=1,t∈ST ≤ t=1,t∈ST √ √ ≤ 2 T L . . , T} : xt (cid:44) xb} ( xb), Tk(T) =(cid:80)T (cid:88) T (cid:88) T (cid:T) =(cid:80) T OPTIMIST アクションが選択されたとき、常に (cid:49) xt=xk (cid:49) xt=xb) 腕 k が t=0 (cid:49) xt=xb の回数 t=0 の回数 T までの時間 t=0 の回数 T の確率 1 − δ に対して、T(cid:88) (cid:114) t T(cid:88) t=1,t⋅ST ≤ ≤ T ≤ T 2 である。 0.84
L t If ∆b = 0 then the theorem holds trivially; we therefore assume that ∆b > 0 and find an upper bound for Tb(T). L t b = 0 のとき、定理は自明に保たれ、それゆえ、b > 0 と仮定し、tb(t) の上限を求める。 0.75
Let τ = max{t ≤ T | xt = xb} be the last round in which the default arm is played. τ = max{t ≤ T | xt = xb} をデフォルトの腕が演奏される最後のラウンドとする。 0.80
Since F holds and ˇU(xb, δt) = µb < µ∗ < maxi θi(t), it follows that xb is never the OPTIMIST choice and the default arm was only played because ˇBτ < 0: K(cid:88) Tk(τ) ˇL(xk, δt)+Tb(τ−1)µ(xb)−(1−α)(τ+1)µ(xb) < 0 we replace τ =(cid:80)K k=1,xk(cid:44)xb (30) k=1,xk(cid:44)xb Tk(τ)+Tb(τ−1) in this inequality F が F を保持して μb < μ∗ < maxi θi(t) となると、xb は OPTIMIST の選択ではないので、デフォルトのアームは K(cid:88) Tk(τ) >L(xk, δt)+Tb(τ−1)μ(xb)−(1−α)(τ+1)μ(xb) < 0 が τ =(cid:80)K k=1,xk(cid:44)xb(30) k=1,xk(cid:44)xb(τ)+Tb(τ−1) であるからである。 0.91
7 7 0.85
英語(論文から抽出)日本語訳スコア
t 1 2  2 t 1 2  2 0.83
) (cid:17) ) (cid:17) 0.82
Tk(τ) S k √ Tk(τ) 略称はSk。 0.67
+ PDd√ t (cid:24) 6δ t 1+ + PDD t (cid:24) 6δ t 1+ 0.73
1 2 t2π2 with L(cid:48) = 1 2 t2π2 L(cid:48) = 0.72
and δt = (cid:17) δt = (cid:17) 0.78
(cid:108) (cid:109) t 1 2 2 + d 2 (cid:108) (cid:109) t 1 2 2 + d 2 0.92
Conservative Optimistic Policy Optimization via Multiple Importance Sampling and rearrange, we have then: K(cid:88) (cid:16) αTb(τ − 1)µ(xb) (cid:32) < (1 − α)µ(xb) + (1 − α) µ(xb) − ˇL(xk, δt) Tk(τ) k=1,xk(cid:44)xb K(cid:88) ≤ (1 − α)µ(xb)+ Tk(τ) ((1 − α) µ(xb) − µk + (a + b)βτ(xk, δτ)) (cid:114) L  (1 − α) µ(xb) − µk + K(cid:88) k=1,xk(cid:44)xb ≤ (cid:107) f(cid:107)∞ + K(cid:88) (cid:112) Tk(τ) k=1,xk(cid:44)xb ≤ (cid:107) f(cid:107)∞ + LTk(τ) akTk(τ) + K(cid:88) k=1,xk(cid:44)xb ≤ (cid:107) f(cid:107)∞ + k=1,xk(cid:44)xb with S k = akTk(τ) + to ease notation. Conservative Optimistic Policy Optimization via Multiple Importance Sampling and rearrange, we have then: K(cid:88) (cid:16) αTb(τ − 1)µ(xb) (cid:32) < (1 − α)µ(xb) + (1 − α) µ(xb) − ˇL(xk, δt) Tk(τ) k=1,xk(cid:44)xb K(cid:88) ≤ (1 − α)µ(xb)+ Tk(τ) ((1 − α) µ(xb) − µk + (a + b)βτ(xk, δτ)) (cid:114) L  (1 − α) µ(xb) − µk + K(cid:88) k=1,xk(cid:44)xb ≤ (cid:107) f(cid:107)∞ + K(cid:88) (cid:112) Tk(τ) k=1,xk(cid:44)xb ≤ (cid:107) f(cid:107)∞ + LTk(τ) akTk(τ) + K(cid:88) k=1,xk(cid:44)xb ≤ (cid:107) f(cid:107)∞ + k=1,xk(cid:44)xb with S k = akTk(τ) + to ease notation. 0.97
We have two cases: ak > 0 or ak ≤ 0. ak > 0 または ak ≤ 0 の2つのケースがある。 0.85
If ak > 0: then µk < (1 − α) µ(xb) so arm k is suboptimal and by 29, we have: Tk(τ) ≤ Tk(T) ≤ L ∆k (because ak ≤ ∆k). ak > 0 ならば μk < (1 − α) μ(xb) なので、アーム k は極小であり、29 までには Tk(τ) ≤ Tk(T) ≤ L {\displaystyle Tk(τ))} が成立する。 0.81
≤ 2L S k ≤ ak √ ∆k If ak ≤ 0: S k = akTk(τ) + LTk(τ) ≤ − L 4ak by using ax2 + bx ≤ − b2 4a when a ≤ 0. ax2 + bx ≤ − b2 4a を用いて ak ≤ 0: S k = akTk( ) + LTk( ) ≤ − L 4ak とすると、 ak ≤ 0 は ax2 + bx ≤ − b2 4a である。 0.89
We can combine both by taking: 2L max(∆k, ∆b − ∆k) (µb ≥ 0 and max(∆k, ∆b − ∆k) ≥ ∆b 2 ). 2l max(g, b − sk) (μb ≥ 0 と max(m, b − sk) ≥ sb 2 ) を取ることで両方を組み合わせることができる。 0.71
Finally, we have: Tb(T) = Tb(τ − 1) + 1 4KL ≤ 1 + α∆bµb 最後に、Tb(T) = Tb(τ − 1) + 1 4KL ≤ 1 + α\bμb 0.89
(eq (64) from Papini et al (2019), with P the Lipshitz constant) (cid:25)d(cid:33) , we have: By replacing τt = (cid:105) 1 (cid:104)(cid:16) 1 log(T) + d log(2) + log( π2 ∆t ≤ (a + b)v 3δ) 2 2 (cid:114) √  L(cid:48) = t (a + b)v (cid:35) 1 2 + PDd (32) In order to reuse the steps from the proof of Theorem 4, we need an independent discretization that does not depend on t (otherwise the number of arm at the end is exponential in T which breaks the regret). (eq (64) from Papini et al (2019) with P the Lipshitz constant) (cid:25)d(cid:33) , We have by replace st = (cid:105) 1 (cid:104)(cid:16) 1 log(T) + d log(2) + log( π2 st ≤ (a + b)v 3δ) 2 2 2 (cid:114) (cid:114) s L(cid:48) = t s(a + b)v (cid:35) 1 2 + PDd (32) Theorem 4の証明からのステップを再利用するには、tに依存しない独立した離散化が必要です。 0.81
(cid:8)x ∈ X : µ(x(cid:63)) − µ(x) ≤ (cid:9) (for a fixed  > 0 chosen such To simplify the analyse, we will break the compact arm X into two regions (or ’big’ arms): A first one where which is just(cid:8)x ∈ X : µ(x(cid:63)) − µ(x) > (cid:9) that 30 could be exactly split into two terms), that contains the best arm, and a second region (suboptimal ’big’ arm) Now, we can reususe the same steps from the previous proof, with two ’big’ arms, one optimal, and the other suboptimal. (cid:8)x ∈ x : μ(x)x ∈ x : μ(x(cid:63)) − μ(x) ≤ s(cid:9) (解析を単純化するために選択された固定された s > 0 に対して) コンパクトアーム x を 2 つの領域(または ’big' アーム)に分解する。
訳抜け防止モード: (cid:8)x ∈ x : μ(x(cid:63 ) ) − μ(x ) ≤ s(cid:9 ) ( 解析を単純化するために選択された固定 s > 0 に対して)。 まず、(cid:8)x ∈ x : μ(x(cid:63 ) ) − μ(x ) > s(cid:9 ) であり、30 は正確に2つの項に分割できる)。 そこには最高のアームと、第2の領域(optimal ’ big ’ arm)が含まれている。 前の証明と同じステップを2つの大きな腕で再利用できます。 1つは最適で もう1つは最適です
0.79
The same steps work exactly, with the only difference is having the new L(cid:48) rather than L and K = 2. 同じステップが正確に機能し、唯一の違いは、LとK = 2ではなく、新しいL(cid:48)を持つことです。 0.77
The regret is then: Regret(T) ≤ ∆b + 2 後悔は次の通りである。 Regret(T) ≤ >b + 2 0.78
log(T) + d log(2) + log( π2 3δ log(T) + d log(2) + log(π2 3δ) 0.99
LTk(τ) and ak = (1 − α) µ(xb) − µk LTk(τ) と ak = (1 − α) μ(xb) − μk 0.89
(cid:107) f(cid:107)∞ ∆b αµb (cid:107) f(cid:107)∞ ×b αμb 0.73
(cid:34)(cid:32) 2 + (cid:34)(cid:32) 2 + 0.81
= L 4(∆b+αµb−∆k) = L 4b+αμb−*k) 0.71
+ 8L(cid:48) αµb + 8L(cid:48)αμb 0.74
(cid:107) f(cid:107)∞ αµb (cid:107) f(cid:107)∞ αμb 0.74
+ √ L(cid:48)T + + √ L(cid:48)T+ 0.87
(33) (cid:3) (33)(cid:3) 0.85
(cid:33) d 2 (cid:33) d2 0.75
S k ≤ ≤ 4L ∆b S k ≤ ≤4L。 0.78
L ∆k 2 + L ∆k 略称は「L」。 2+L/k 0.50
2 so then: To conclude, the regret can be bounded with probability 1 − δ by: では2つです 結論として、後悔は確率 1 − δ によって境界づけられる。 0.64
Regret(T) ≤ 2 Regret(T) ≤ 2 0.85
LT + ∆b + √ LT + ×b + √ 0.80
(cid:107) f(cid:107)∞ ∆b αµb (cid:107) f(cid:107)∞ ×b αμb 0.73
+ 4KL αµb (cid:3) + 4KL αμb (cid:3) 0.74
B. Proof of Theorem 6 Proof. B。 Theorem 6 Proofの証明。 0.77
The only difference in this case is that 28 becomes: (31) この場合の唯一の違いは、28が: (31) 0.78
∆t ≤ (a + b)βt(xt, δt) + t ≤ (a + b)βt(xt, δt) + 0.88
PDd τt 8 PDd τt 8 0.87
                 ページの最初に戻る

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