論文の概要、ライセンス

# (参考訳) 帯域フィードバックを用いた制約付き最適化のためのリアプノフ法 [全文訳有]

A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback ( http://arxiv.org/abs/2106.05165v1 )

ライセンス: CC BY 4.0
Semih Cayci, Yilin Zheng, Atilla Eryilmaz(参考訳) オンライン広告、契約採用、および無線スケジューリングを含む幅広いアプリケーションにおいて、コントローラは、各アクションによってランダムに消費される利用可能なリソースに対する厳格な予算制約と、意思決定に重要な運用上の制限を課す確率的可能性制約によって制約される。 本研究では、各アクションが未知の共同分布からランダムな報酬、コスト、ペナルティを返し、意思決定者は、総コストにb$、時間平均ペナルティに確率的制約を課す予算制約の下で、総報酬を最大化することを目的としている。 我々は、Lyapunov最適化手法に基づく新しい低複雑さアルゴリズムである${\tt LyOn}$を提案し、それが$O(\sqrt{B\log B})$ regretおよび$O(\log B/B)$ constraint-violation を達成することを証明した。 計算コストの低い${\tt LyOn}$の急激な性能境界は、リアプノフに基づくアルゴリズム設計手法が制約付き帯域最適化問題を解くのに有効であることを示唆している。

In a wide variety of applications including online advertising, contractual hiring, and wireless scheduling, the controller is constrained by a stringent budget constraint on the available resources, which are consumed in a random amount by each action, and a stochastic feasibility constraint that may impose important operational limitations on decision-making. In this work, we consider a general model to address such problems, where each action returns a random reward, cost, and penalty from an unknown joint distribution, and the decision-maker aims to maximize the total reward under a budget constraint $B$ on the total cost and a stochastic constraint on the time-average penalty. We propose a novel low-complexity algorithm based on Lyapunov optimization methodology, named ${\tt LyOn}$, and prove that it achieves $O(\sqrt{B\log B})$ regret and $O(\log B/B)$ constraint-violation . The low computational cost and sharp performance bounds of ${\tt LyOn}$ suggest that Lyapunov-based algorithm design methodology can be effective in solving constrained bandit optimization problems.
公開日: Wed, 9 Jun 2021 16:12:07 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 1 2 0 2 n u J 0.85
9 ] G L . 9 ] G L。 0.81
s c [ 1 v 5 6 1 5 0 sc [ 1 v 5 6 1 5 0 0.68
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
A Lyapunov-Based Methodology for Constrained lyapunovに基づく制約付き手法 0.81
Optimization with Bandit Feedback バンディットフィードバックによる最適化 0.70
Semih Cayci ∗ Semih Cayci ∗ 0.85
Yilin Zheng† Yilin Zhengó 0.71
Atilla Eryilmaz† Atilla (複数形 Atillas) 0.36
scayci@illinois.edu scayci@illinois.edu 0.78
zheng.1443@osu.edu 1443@osu.edu 0.71
eryilmaz.2@osu.edu eryilmaz.2@osu.edu 0.59
Abstract In a wide variety of applications including online advertising, contractual hiring, and wireless scheduling, the controller is constrained by a stringent budget constraint on the available resources, which are consumed in a random amount by each action, and a stochastic feasibility constraint that may impose important operational limitations on decision-making. 概要 オンライン広告、契約採用、および無線スケジューリングを含む幅広いアプリケーションにおいて、コントローラは、各アクションによってランダムに消費される利用可能なリソースに対する厳格な予算制約と、意思決定に重要な運用上の制限を課す確率的可能性制約によって制約される。 0.60
In this work, we consider a general model to address such problems, where each action returns a random reward, cost, and penalty from an unknown joint distribution, and the decision-maker aims to maximize the total reward under a budget constraint B on the total cost and a stochastic constraint on the time-average penalty. 本研究は,各行動が未知の共分散からランダムな報酬,コスト,ペナルティを返し,意思決定者が総コストに対する予算制約bと時間平均ペナルティに対する確率的制約の下で総報酬を最大化することを目的としている。 0.64
We propose a novel low-complexity algorithm based on Lyapunov optimization methodology, named LyOn, and prove that it achieves O(√B log B) regret and O(log B/B) constraint-violation . Lyapunov 最適化手法をLyOn と呼ぶ新しい低複雑性アルゴリズムを提案し,このアルゴリズムが O(\B log B) の後悔と O(log B/B) の制約違反を実現することを証明した。 0.73
The low computational cost and sharp performance bounds of LyOn suggest that Lyapunovbased algorithm design methodology can be effective in solving constrained bandit optimization problems. LyOnの低計算コストと急激な性能境界は、Lyapunovに基づくアルゴリズム設計手法が制約付き帯域最適化問題の解決に有効であることを示唆している。 0.71
1 Introduction Multi-armed bandits (MAB) have been predominantly used to model the exploration-andexplo itation problems since its inception [26, 19, 5]. はじめに マルチアーム・バンディット (MAB) は, [26, 19, 5] の開始以来, 探索・探索問題のモデル化に主に用いられている。 0.62
As a consequence of the universality of the dilemma, bandit algorithms have found a broad range of applications from medical trials and adaptive routing to server allocation [8]. ジレンマの普遍性の結果、バンディットアルゴリズムは、医学的試行錯誤や適応的なルーティングからサーバ割り当てまで、幅広い応用を見出した[8]。 0.57
In many applications of interest, the controller is required to satisfy multiple constraints while achieving the optimal expected total reward under a given finite budget. 多くの応用において、コントローラは与えられた有限予算の下で最適な総報酬を達成しつつ、複数の制約を満たす必要がある。 0.67
To take one example, in fair resource allocation problems, such as task scheduling or contractual hiring, each arm (e g , a user or a social group) must receive at least a given fraction of the total budget (e g , total time) while maximizing the total reward. 一例として、タスクスケジューリングや契約採用などの公平な資源配分問題において、各アーム(例えば、ユーザまたは社会グループ)は、合計報酬を最大化しつつ、予算全体の少なくとも一割(例えば、合計時間)を受け取らなければならない。 0.75
Other examples from diverse domains, such as wireless resource allocation, online advertising, etc., also take this form (see Section 2 for more discussion). 無線リソース割り当てやオンライン広告などの多様なドメインからの例もこの形式を踏襲している(詳細は第2節を参照)。 0.75
In order to solve fundamental learning applications such as these, a fast and effective constrained bandit optimization framework is required. このような基本的な学習アプリケーションを解決するためには、高速かつ効果的な制約付き帯域最適化フレームワークが必要である。 0.69
This motivates us in this paper to formulate and solve the following budget-constrained bandit problem in a stochastic setting. そこで,本稿では,以下の予算制約付きバンディット問題を確率的に解くことを動機付けている。 0.62
Each arm pull takes a random and arm-dependent resource (e g time, energy, etc.) 各アームプルはランダムでアームに依存したリソース(例えば時間、エネルギーなど)を取る。 0.71
from the budget, and the decision-making process continues until the total consumed resource exceeds a given budget B > 0. 予算から総消費資源が所定の予算 B > 0 を超えるまで、意思決定プロセスは継続される。 0.70
At the end of each arm pull, the controller receives a random reward and a random penalty. 各アームプルの終了時に、コントローラはランダムな報酬とランダムなペナルティを受け取る。 0.66
The objective of the controller is to maximize the expected total reward subject to an inequality constraint on the average penalty per unit resource consumption. コントローラの目的は、単位資源消費当たりの平均ペナルティに対する不等式制約の対象となる総報酬を最大化することである。 0.75
∗Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 †Department of Electrical and Computer Engineering, The Ohio State University, Columbus, OH 43210 Equal contribution from S. Cayci and Y. Zheng. イリノイ大学アーバナ・シャンペーン校(university of urbana-champaign, urbana, il 61801, department of electrical and computer engineering, the ohio state university, columbus, oh 43210)のコーディネート科学研究所。
訳抜け防止モード: イリノイ大学アーバナ校 ∗Coordinated Science Laboratory Urbana, IL 61801 >Department of Electrical and Computer Engineering, the Ohio State University (英語) コロンバス OH 43210 S. Cayci と Y. Zheng の貢献。
0.78
Preprint. Under review. プレプリント。 レビュー中。 0.63
英語(論文から抽出)日本語訳スコア
1.1 Main Contributions In this work, we tackle the aforementioned general constrained optimization problem with bandit feedback, and propose a novel Lyapunov-based design methodology to develop efficient algorithms that achieve sharp convergence results. 1.1主な貢献 本研究では,先述した一般制約最適化問題にバンディットフィードバックを用いて取り組み,鋭い収束結果を得る効率的なアルゴリズムを開発するための新しいリアプノフ設計手法を提案する。 0.75
Our main contributions can be summarized as follows: 私たちの主な貢献は以下のとおりである。 0.67
• General model: We consider a generic constrained bandit optimization problem (in Section 2), which: (i) incorporates random costs for each action; (ii) is subject to a stringent budget (knapsack) constraint; and (iii) has stochastic feasibility constraints as required by many applications. • 一般モデル: 一般的な制約付き帯域最適化問題(第2節)について考察する: (i) アクションごとにランダムなコストを組み込む; (ii) 厳しい予算(knapsack) 制約を受ける; (iii) 多くのアプリケーションで要求される確率的実現可能性制約を持つ。 0.88
• Lyapunov methodology for bandit optimization: Based on a Lyapunov-drift minimization technique from stochastic control, we design novel low-complexity bandit algorithms with provably sharp convergence properties. • lyapunov method for bandit optimization: 確率制御によるlyapunov-drift最小化手法に基づいて, 鋭い収束特性を有する新しい低複素バンディットアルゴリズムを設計する。 0.88
This approach suggests a general design methodology (outlined in Section 3) that can be utilized in other constrained bandit optimization scenarios. このアプローチは、他の制約付き帯域最適化シナリオで使用できる一般的な設計手法(第3節に概説)を提案する。 0.82
• Analysis techniques: We also employ new analysis techniques (in Section 5) for the reward maximization problem subject to stochastic and knapsack constraints based on a combination of renewal theory, stochastic control, and bandit optimization. • 解析手法: また,リニューアル理論,確率制御,およびバンドイット最適化の組み合わせに基づく,確率およびクナプサック制約を考慮した報酬最大化問題に対して,新たな解析手法(第5節)を用いる。 0.83
1.2 Related Work Knapsack-constrained bandit problem was considered in [3], where the objective of the controller is to maximize the expected total reward under a stringent budget constraint. 1.2関連作品 Knapsack-Constrained bandit problem was considered in [3], where the objective of the controller is to maximum the total reward under a stringent budget constraints。 0.74
The au- thors proposed a learning algorithm with O(√B) problem-independent regret. 阿 thors氏はo(\b)問題非依存の後悔を持つ学習アルゴリズムを提案した。 0.45
Bandit algorithms with O(log(B)) problem-dependent regret bounds were proposed under various extensions of the knapsack-constrained bandit models [9, 30, 29, 10, 27]. O(log(B))問題依存的再帰境界を持つ帯域アルゴリズムは,knapsack制約付き帯域モデル [9, 30, 29, 10, 27] の様々な拡張の下で提案された。 0.77
These works differ from ours in that, while the controller is constrained by stringent knapsack constraints, stochastic feasibility constraints are not accommodated. これらの作業は我々のものと異なり、コントローラは厳密なknapsack制約によって制約されるが、確率的実現可能性制約は許容されない。 0.57
As an extension of [3], bandit problem with stochastic feasibility constraints was considered in [1], 3] の拡張として,確率的実現可能性制約を伴うバンドイット問題を[1] で検討した。 0.64
and a UCB-type algorithm with O(√B) regret and O(1/√B) constraint-violation was proposed. また, UCB-type Algorithm with O(\B) regret and O(1/\B) constraint-violation was proposed。 0.80
This setting was extended to episodic Markov decision processes in [24], and similar order results for regret and constraint-violation were obtained. この設定は[24]のエピソディックマルコフ決定プロセスに拡張され、後悔と制約違反に対する同様の順序結果が得られた。 0.72
In these models, each action incurs a unit cost. これらのモデルでは、各アクションはユニットコストを伴います。 0.69
Furthermore, the proposed algorithms in [1] have high computational complexity as they require solving convex optimization problems at each stage. さらに [1] における提案アルゴリズムは,各段階における凸最適化問題を解く必要があるため,計算複雑性が高い。 0.81
Our model accommodates random cost, which is subject to a knapsack constraint, in addition to the stochastic feasibility constraint. 我々のモデルは、確率的実現可能性制約に加えて、knapsack制約を受けるランダムコストに対応している。 0.71
More importantly, we develop computationally-efficient iterative algorithms based on Lyapunov optimization theory. さらに,リアプノフ最適化理論に基づく計算効率の高い反復アルゴリズムを開発した。 0.70
Lyapunov optimization methods have been widely used in stochastic network optimization and queueing systems (see [22, 21, 12] and references therein). リアプノフ最適化法は確率ネットワーク最適化や待ち行列システムで広く使われている( [22, 21, 12] を参照)。
訳抜け防止モード: リアプノフ最適化法は確率的ネットワーク最適化や待ち行列システムに広く用いられている([22]参照)。 21 , 12 ]および参照。
0.84
This methodology was later used in convex optimization problems [31] with known gradients. この手法は後に既知の勾配を持つ凸最適化問題[31]で用いられた。 0.71
In these approaches, a predominant assumption is that the random system state is known to the controller prior to its decision, therefore the existing methods do not work for online learning setting where the controller does not have the system state or the system statistics before making a decision. これらのアプローチでは、ランダムなシステム状態がその決定の前にコントローラに知られており、既存の手法は決定を行う前にコントローラがシステム状態やシステム統計を持っていないオンライン学習環境では機能しない、という仮定が主流である。 0.78
Lyapunov optimization methods were first used in the context of online learning in [11], where the goal of the controller is to maximize the total utility as a function of each arm’s time-average reward subject to a knapsack constraint under delayed experts feedback. lyapunovの最適化手法は、[11]においてオンライン学習の文脈で最初に使用された。コントローラーの目的は、遅延した専門家のフィードバックの下でナップサック制約を受ける各アームの時間平均報酬の関数としての全効性を最大化することである。 0.69
Our work extends [11] in that we consider bandit feedback and also incorporate stochastic feasibility constraints in this paper. 本論文では,帯域幅のフィードバックを考慮し,確率的実現可能性の制約を取り入れた[11]。 0.63
Another recent work, which utilizes Lyapunov-drift methods for online learning, [20] studies the online-dispatching with resource constraints and multiple-choice bandit feedback. 20] オンライン学習におけるlyapunov-drift法を活用したもうひとつの研究は、リソース制約とマルチチョースバンディットフィードバックによるオンライン分散の研究である。 0.70
Our work substantially differs from this work in that we incorporate knapsack budget constraints and random costs per arm selection. 私たちの仕事は、クナプサック予算の制約とアーム選択当たりのランダムなコストを組み込むことで、この作業と実質的に異なる。
訳抜け防止モード: 私たちの仕事は、その仕事とは大きく異なる。 我々はknapsackの予算制約と 腕選択のランダムコストを組み込んでいます
0.62
2 Constrained Reward Maximization Problem with Bandit Feedback 2 バンディットフィードバックを伴う制限付き報酬最大化問題 0.70
We consider a finite-armed bandit problem with K > 1 arms, and the set of arms denoted by K = {1, 2, . K > 1 の腕を持つ有限腕バンディット問題と K = {1, 2, で表される腕の集合を考える。
訳抜け防止モード: K > 1 の腕を持つ有限武装バンディット問題を考える。 そして、腕の集合は K = { 1, 2,} で表される。
0.74
. . , K}. . . k である。 0.74
If arm k is chosen at nth epoch, it incurs a cost of Xn,k, yields a reward of Rn,k, and returns a penalty of Yn,k, where the outcome of the joint random vector (Xn,k, Rn,k, Yn,k) is learned via bandit feedback at the end of each arm decision. 第n期でarm kが選択されると、xn,kのコストがかかり、rn,kの報酬が得られ、n,kのペナルティが返され、各arm決定の最後にバンディットフィードバックによって合同ランダムベクトル(xn,k,rn,k,yn,k)の結果が学習される。
訳抜け防止モード: アーム k が n 番目のエポックで選択された場合、Xn, k のコストがかかる。 Rn, k の報酬を受け取り、Yn のペナルティを返す。 k は、結合ランダムベクトル (Xn,) の結果である。 k, Rn, k, Yn, k ) は各腕決定の最後にバンドイットフィードバックによって学習される。
0.77
We assume that the random process ランダムなプロセスは 0.47
2 2 0.85
英語(論文から抽出)日本語訳スコア
{(Xn,k, Rn,k, Yn,k) : n ≥ 1} is independent and identically distributed over n, and independent across different arms for all k ∈ K. For simplicity, we assume that Xn,k, Rn,k, Yn,k ∈ [0, 1] for all n, k, which can be easily extended to general sub-Gaussian random variables by using the same techniques used in this paper. xn,k, rn,k, yn,k) : n ≥ 1} は n 上で独立かつ同一に分布し、すべての k ∈ k に対して異なる腕をまたいで独立である。
訳抜け防止モード: { (Xn, k, Rn, k, Yn, k) : n ≥ 1 } は独立であり、n 上に同じ分布する。 すべての k ∈ K に対して異なる腕で独立している。 Xn, k, Rn, k, Yn, すべての n, k に対して k ∈ [ 0, 1 ] これは、この論文で使われているのと同じ手法を用いて、ガウス確率変数に容易に拡張できる。
0.88
The controller has a total budget B > 0 at the beginning of the process, and tries to maximize the expected cumulative reward under time-average constraints on the penalties by sampling the arms wisely under this budget constraint. コントローラはプロセスの始めに総予算b > 0 を持ち、この予算制約の下で腕を巧みにサンプリングすることにより、ペナルティの時間平均制約下での累積報酬を最大化しようとする。 0.71
We first introduce the policy space. まずポリシーの分野を紹介します。 0.69
Definition 1 (Causal Policy). 定義1(因果政策)。 0.63
Let π be a policy that yields a sequence of arm pulls {I π Under π, the history until epoch n is the following filtration: π を π の下でアームプル {i π の列を与える方針とし、エポック n が次の濾過となるまでの歴史を次のように述べる。 0.69
n ∈ K : n ≥ 1}. n ∈ K : n ≥ 1} である。 0.90
F π n = σ({(I π f π n = σ({(i π)) 0.95
j , Xj,k, Rj,k, Yj,k) : I π j , Xj,k, Rj,k, Yj,k) : I π 0.85
j = k, 1 ≤ j ≤ n}), j = k, 1 ≤ j ≤ n}) である。 0.93
(1) n = k} ∈ F π (1) n = k} ∈ F π 0.85
where σ(Z) denotes the sigma-field of a random variable Z. ここで σ(z) は確率変数 z のシグマ場を表す。 0.74
We call an algorithm π causal if π is non-anticipating, i.e., {I π The set of all causal policies is denoted as Π. アルゴリズム π {\displaystyle π} が予測的でない場合、すなわち {i π} はすべての因果ポリシーの集合を π と表記する。 0.81
We denote the variables at epoch n under policy π as X π . ポリシー π の下でのエポック n における変数を X π と表す。 0.70
The total cost incurred in n epochs under an causal n = Xn,I π policy π ∈ Π is a controlled random walk which is defined as Sπ i . 因果 n = xn,i π ポリシー π ∈ π の下で n 個のエポックに生じる総コストは、制御されたランダムウォークであり、これは sπ i と定義される。 0.67
The decision process under a policy π continues until the budget B is depleted. 政策 π の下での決定過程は、予算 b が枯渇するまで続く。 0.75
We assume that the reward corresponding to the final epoch during which the budget is depleted is gathered by the controller. 我々は、予算が枯渇した最終時代に対応する報酬がコントローラによって収集されたと仮定する。 0.67
Thus, the total number of pulls under π is a random variable that is defined as follows: したがって、π の下にあるプルの総数は、次のように定義されるランダム変数である。 0.72
n−1 for all k, n. すべての k に対して n−1 である。 0.65
n = Yn,I π n = Yn,I π 0.85
n = Rn,I π n = Rn,I π 0.85
i=1 X π and Y π i=1 X π そして Y π 0.80
, Rπ n n n , Rπ n n n 0.86
N π(B) = infnn ≥ 1 : Sπ N π(B) = infnn ≥ 1 : Sπ 0.92
n =Pn n > Bo. n = Pn > Bo。 0.78
Note that the total number of pulls N π(B) is a stopping time adapted to the filtration {(F π Accordingly, the cumulative reward under a policy π can be written as follows: プル数 N π(B) はフィルター {(F π) に適合する停止時間であるため、ポリシー π の下での累積報酬は次のように記述できる。 0.68
n ) : n ≥ 0}. n ) : n ≥ 0} である。 0.87
Then, we can write the generic problem formulation considered in this paper as follows: 次に,本論文で考察した一般的な問題定式化を次のように記述する。 0.62
REWπ(B) = N π(B)Xn=1 REWπ(B) = N π(B)Xn=1 0.95
Rπ n. max Rπ n。 マックス 0.80
π ∈ Π  E[REWπ(B)], π ∈ Π  E[REWπ(B)], 0.80
subject to: E" 1 B 対象:「E」1。 B 0.78
N π(B)Xn=1 N π(B)Xn=1 0.92
Y π Definition 2 ((Pseudo) Regret and constraint-violation ). Yπ 定義2(Pseudo) 規則と制約違反。 0.59
Let πOpt be the solution of (4) and OPT(B) = E[REWπOpt(B)]. πOpt を (4) と OPT(B) = E[REWπOpt(B)] の解とする。 0.84
For any causal policy π ∈ Π and a budget B > 0 level, the (pseudo) regret, REGπ(B), and constraint-violation , Dπ(B), are defined as follows: あらゆる因果ポリシー π ∈ π および予算 B > 0 レベルに対して、(擬)後悔、REGπ(B)、制約違反、Dπ(B) は次のように定義される。 0.73
REGπ(B) = OPT(B) − E[REWπ(B)], REGπ(B) = OPT(B) − E[REWπ(B)], 0.85
Dπ(B) = E" 1 Dπ(B) = E" 1 0.94
B The objective of this paper is to design low-complexity bandit algorithms that are guaranteed to give a low regret and a vanishing constraint-violation level that decays rapidly with the budget level B, in the absence of any statistical knowledge on the costs, rewards, and penalties. B 本研究の目的は, 費用, 報酬, ペナルティに関する統計的な知識を欠くことなく, 低い後悔と, 予算レベルbで急速に崩壊する, 消滅する制約違反レベルを保証できる低複雑度バンディットアルゴリズムを設計することである。 0.83
The generic problem (4) has numerous applications in communications, control, operations research and management, whereby optimal decision-making under data scarcity and uncertainty is common. 一般的な問題(4)は、コミュニケーション、制御、オペレーションの研究、管理に多くの応用があり、データ不足と不確実性の下での最適な意思決定が一般的である。 0.58
Next, we provide a detailed application in wireless scheduling in next generation networks, and refer the reader to Appendix A for other example applications for contractual hiring, and online advertising. 次に、次世代ネットワークにおける無線スケジューリングの詳細なアプリケーションを提供し、契約採用やオンライン広告などの応用例として、読者をAppendix Aに参照する。 0.79
Application to Next Generation Wireless Scheduling with Quality-of-Service Guarantees: Next-generation wireless technologies are required to serve a highly dynamic population of users with stringent quality-of-service (QoS) guarantees (such as low delay [18]) over ultra-high frequency bands with nontraditional statistical and temporal characteristics [25]. サービス品質保証による次世代無線スケジューリングへの応用: 非線形統計・時間特性を有する超高周波数帯に対して、サービス品質保証(QoS)の厳しい保証(低遅延[18]など)を有するユーザの高い動的人口に対応するために、次世代無線技術が必要である。 0.79
As such, existing estimation and allocation techniques that rely strongly on persistent users and slowly-changing nature and known statistical models of channel conditions are no longer suitable for use in this new ultrawideband communication paradigm. このように、この新しい超広帯域通信パラダイムでは、持続的ユーザとゆっくりと変化する性質と既知のチャネル条件の統計モデルに強く依存する既存の推定と割り当て技術がもはや適していない。 0.79
The controller is required to learn how to optimize the throughput subject to QoS guarantees by using the ARQ (bandit) feedback received after each transmission. コントローラは、送信後に受信したARQ(bandit)フィードバックを使用して、QoS保証対象のスループットを最適化する方法を学ぶ必要がある。 0.69
3 (2) (3) (4) 3 (2) (3) (4) 0.85
(5) n# ≤ c. n# − c. N π(B)Xn=1 (5) n# ≤ c.\ n# − c. n π(b)xn=1 0.88
Y π 0.65
英語(論文から抽出)日本語訳スコア
This calls for the design of time/energy-constrai ned point-to-point communication solutions over K parallel memoryless channels with unknown and diverse statistical characteristics. これは、未知で多様な統計特性を持つk並列メモリレスチャネル上の時間/エネルギー制約のあるポイント・ツー・ポイント通信ソリューションの設計を求める。 0.57
In particular, each connection starts with a total time or energy budget of B units. 特に、各接続はBユニットの総時間またはエネルギー予算から始まる。 0.70
The transmission of nth packet over the kth channel consumes a random amount of Xn,k resource (e g , transmission time or energy), yields a reward (e g , throughput) Rn,k and incurs a penalty Yn,k upon completion of transmission. kthチャネル上のn番目のパケットの送信は、ランダムな量のXn,kリソース(eg,送信時間またはエネルギ)を消費し、送信完了時に報酬(eg,スループット)Rn,kを出力し、ペナルティYn,kを発生させる。 0.78
In this context, Yn,k is a generic penalty that will be used in modeling time-average quality-of-service guarantees. この文脈では、yn,kは一般的なペナルティであり、サービス品質保証の時間平均化に使用される。 0.58
As an example, consider delay-constrained communication, where the arriving packets should be transmitted in a timely manner. 例えば、到着したパケットをタイムリーに送信する遅延制約のある通信を考える。
訳抜け防止モード: 例えば、遅延 - 制約のある通信、どこで 到着したパケットは タイムリーに送信されるべきです
0.69
Then, for a given deadline level d ∈ [0, 1], we let Yn,k = I{Xn,k > d}, which counts the number of packets that are delayed for more than d time units. すると、与えられた期限レベル d ∈ [0, 1] に対して、yn,k = i{xn,k > d} とし、これは d 時間単位以上遅延するパケットの数を数える。 0.71
For a given time or energy budget B and a quality-of-service constraint c, the optimization problem (4) leads to throughput maximization subject to a guarantee on the time-average number of delayed packets. 所定の時間またはエネルギー予算Bとサービス品質制約cに対して、最適化問題(4)は、遅延パケットの時間平均数の保証を受けるスループットを最大化する。 0.80
Note that many other QoS criteria, such as the fraction of dropped packets, can be modeled in a similar manner, which implies the generality of this approach. ドロップパケットの分数など他の多くのQoS基準も同様にモデル化できることに注意し、このアプローチの一般性を示している。 0.69
3 Outline of the Lyapunov-Based Design Methodology and Main Results 3 リャプノフに基づく設計方法論の概要と主な結果 0.81
In this work, we develop a low-complexity online algorithm for solving the generic constrained reward maximization problem (4) by employing a Lyapunov-drift minimization methodology. 本研究では,lyapunov-drift最小化手法を用いて,一般制約付き報酬最大化問題(4)を解決するための低複雑さオンラインアルゴリズムを開発した。 0.70
Since this methodology may be of independent value, in this section we provide an outline of its main steps along with an informal discussion of the key results we obtained under them. この方法論は独立した価値を持つ可能性があるので、この節では、主要なステップの概要と、それらに基づいて得られた主要な結果について非公式に議論する。 0.50
(i) Characterization of the Asymptotically-Optim al Stationary Randomized Oracle: Noting that finding the optimal policy πOpt for (4) is PSPACE-hard, in Section 4 we propose a stationary randomized policy π∗ in Definition 4 that achieves (see Proposition 1) O(1) regret and O(1/B) constraint-violation gap. i) asymptotically-optim al stationary randomized oracle: (4) の最適なポリシー πopt を見つけることはpspace-hardであり、第4節では、(命題1) o(1) regret と o(1/b) 制約違反ギャップを達成するための定義 4 における定常ランダム化ポリシー π∗ を提案する。 0.83
This proves that the stationary policy is asymptotically optimal as the budget B goes to infinity. これは、固定政策が漸近的に最適であることを証明している。 0.52
Our Lyapunov-based policy design, developed in Section 5, are broken into the following two steps: 第5節で開発されたリャプノフの政策設計は、以下の2つの段階に分けられる。
訳抜け防止モード: Lyapunov-based policy design, developed in Section 5 以下の2つのステップに分けられます
0.80
n} that is updated as: Qπ n} を次のように更新する。 0.73
(ii) Offline Lyapunov-Drift-Minim izing Policy Design: We first consider in Section 5.1 the ‘offline’ setting with known reward, cost, and penalty statistics. (ii)オフラインlyapunov-drift-minim izing policy design: 第5.1節では、既知の報酬、コスト、ペナルティ統計を備えた‘オフライン’の設定を初めて検討した。 0.56
There, we introduce a virtual queue {Qπ n}, with a design choice δ ∈ [0, c), which keeps track of the constraint-violation level under policy π over decisions n ≥ 1. そこで、決定 n ≥ 1 上のポリシー π の下で制約違反レベルを追跡する設計選択 δ ∈ [0, c] を持つ仮想キュー {qπ n} を導入する。 0.73
Then, under this queue dynamics, we propose a quadratic Lyapunov drift-minimizing policy πLyOff in Definition 6 that achieves (cf. 次に、このキューダイナミクスの下で、(cf) を達成する定義6における2次リアプノフドリフト最小化ポリシーπlyoffを提案する。 0.62
Proposition 2) O((δ + 1/V )B) regret and O(V /B − δ) constraintviolation gap, where V > 0 is a design parameter. 命題 2) o((δ + 1/v )b) 後悔と o(v /b − δ) 制約違反ギャップ、ここで v > 0 は設計パラメータである。 0.82
With the particular selection of V = Θ(√B) and δ = Θ(1/√B), we can guarantee O(√B) regret and O(1/B) constraint-violation guarantees for πLyOff. V と δ の特定の選択により、πLyOff に対する O(/B) の後悔と O(1/B) の制約違反を保証することができる。 0.68
n+1 = max{0, Qπ n+1 = max{0, Qπ 0.86
n + Y π n − (c − δ)X π n + Y π n − (c − δ)X π 0.85
(iii) Online Lyapunov-Drift-Minim izing Policy Design: Then, in Section 5.2, we return to the original ‘online’ setting with unknown statistics, and develop a low-complexity empirical Lyapunovdrift minimizing policy πLyOn that integrates confidence bounds of proposed empirical estimator with the queueing dynamics from the offline case. (iii)オンラインlyapunov-drift-minim izing policy design: 第5.2節では、未知の統計を持つ元の「オンライン」設定に戻り、オフラインケースから経験的推定器の信頼境界と待ち行列のダイナミクスを統合する、低複雑さな経験的lyapunovdriftミニミゼーションポリシーπlyonを開発する。 0.69
Then, the main result of the paper (cf. その後、紙の主な結果(cf。 0.66
Theorem 1) establishes that πLyOn achieves O(√B log B + B(1 + δ log B)/V + Bδ + K log B) regret and O(K log B/B + V /B − δ) constraint-violation level. Theorem 1) は πLyOn が O(\B log B + B(1 + δ log B)/V + Bδ + K log B) の後悔と O(K log B/B + V /B − δ) 制約違反レベルを達成することを証明している。 0.81
With the particular selection of design paO(K log B/B) constraint-violation guarantees for πLyOn. πLyOnに対して、特定の設計paO(K log B/B)制約違反を保証する。 0.62
rameters as V = Θ(√B log B) and δ = Θ(plog B/B), we guarantee O(√B log B) regret and v = θ(\b log b) および δ = θ(plog b/b) としてのラメータは、o(\b log b) の後悔と後悔を保証する。 0.64
The online analysis is especially complicated by the fact that the cumulative reward and penalty processes form stopped and controlled random walks. オンライン分析は特に、累積報酬とペナルティのプロセスが停止してランダムウォークを制御するという事実によって複雑である。 0.62
To address the associated challenge, we combine techniques from renewal theory and Martingale concentration inequalities [28] to find a high probability upper bound for N π(B). 関連する課題に対処するために, 再更新理論とマルティンゲール濃度不等式 [28] の手法を組み合わせて, n π(b) に対して高い確率上限を求める。 0.75
Additionally, for the online policy with unknown statistics, we carefully integrate empirical concentration inequalities [9] with hitting time analysis for Martingales [14] as well as Lyapunov drift analysis [22] to bound REWπ(B) and Dπ(B). さらに,未知統計を持つオンライン・ポリシーでは,martingales [14] と lyapunov drift analysis [22] のバウンド rewπ(b) と dπ(b) に対するヒット時間解析と,経験的濃度不等式 [9] を慎重に統合する。 0.80
4 4 0.85
英語(論文から抽出)日本語訳スコア
4 Asymptotically-Optim al Stationary Randomized Oracle Design 4 漸近的最適定常ランダム化オラクル設計 0.66
The optimization problem described in Section 2 is a variant of the unbounded knapsack problem, and it is known that similar stochastic control problems are PSPACE-hard [3, 23]. 第2節で述べた最適化問題は、非有界クナップサック問題の変種であり、同様の確率制御問題は pspace-hard [3, 23] であることが知られている。 0.67
As a tractable benchmark, in this section, we consider approximation algorithms with provably good performance. 本節では,抽出可能なベンチマークとして,優れた性能を有する近似アルゴリズムについて検討する。 0.67
Definition 3 (Reward Rate and Penalty Rate). 定義3(リワードレートとペナルティレート)。 0.67
Consider a stationary randomized policy π = π(p) for a given probability mass function p = (p1, p2, . 与えられた確率質量関数 p = (p1, p2, ) に対する定常ランダム化ポリシー π = π(p) を考える。 0.88
. . , pK), which takes action k with probability pk independent from the history. . . (pk) は、確率 pk が履歴から独立して作用 k を取る。 0.79
Then, under π(p), the reward rate and penalty rate are defined as: そして、π(p) の場合、報酬率とペナルティ率は次のように定義される。 0.69
r(p) = Pk∈K pkE[R1,k] Pk∈K pkE[X1,k] r(p) = Pk-K pkE[R1,k] Pk-K pkE[X1,k] 0.77
, y(p) = Pk∈K pkE[Y1,k] Pk∈K pkE[X1,k] , y(p) = Pk・K pkE[Y1,k] Pk・K pkE[X1,k] 0.81
, (6) Intuitively, if an arm is chosen persistently according to the stationary randomized policy π(p) until the budget B > 0 is depleted, the cumulative reward becomes r(p)B +o(B) and cumulative penalty becomes y(p)B + o(B). , (6) 直感的には、予算 B > 0 が枯渇するまで、固定ランダム化ポリシー π(p) に従ってアームが永続的に選択されると、累積報酬は r(p)B + o(B) となり、累積ペナルティは y(p)B + o(B) となる。 0.83
Moreover, whenever E[R2 1,k] < ∞ (trivially true for bounded random variables), the additive o(B) term is O(1) in both cases by Lorden’s inequality [2]. さらに、E[R2 1,k] < ∞ (有界確率変数に対して自明に真) であるとき、加法的 o(B) 項はローレンの不等式 [2] による両方の場合 O(1) である。 0.76
1,k] < ∞ and E[Y 2 1,k] < ∞ と e[y 2 0.80
In the following, we prove that a stationary randomized policy achieves O(1) optimality gap with constraint-violation vanishing at a rate of O(1/B). 定常ランダム化政策がO(1)最適性ギャップを達成し,O(1/B)の速度で制約違反が消滅することを証明する。 0.72
Definition 4 (Optimal Stationary Randomized Policy, π∗). 定義 4 (Optimal Stationary Randomized Policy, π∗)。 0.70
Let p∗ be the solution to the following optimization problem: p∗ を次の最適化問題の解とする。 0.80
where ∆K is the K-dimensional probability simplex. K-次元確率は単純である。 0.73
The optimal stationary randomized policy, denoted by π∗, pulls arm k with probability p∗k independently at each epoch until the budget is depleted: P(I π∗ 最適定常ランダム化ポリシーは π∗ で表され、予算が枯渇するまで各エポックにおいて独立に確率 p∗k を持つ arm k を引き出す。 0.78
(B). n = k) = p∗k, for all n ≤ N π∗ (B)。 n = k) = p∗k, for all n ≤ N π∗ 0.85
max p∈∆K {r(p), マックス p) K {r(p) 0.69
subject to: y(p) ≤ c} . 対象: y(p) ≤ c} である。 0.64
The main result of this section is the following proposition, which implies that π∗ is a good approximation algorithm for πOpt for B > 0. この節の主な結果は次の命題であり、これは π∗ が b > 0 に対する πopt のよい近似アルゴリズムであることを意味する。 0.82
Proposition 1 (Optimality Gap for π∗). 命題1(π∗ の最適ギャップ)。 0.53
For the optimal static policy π∗ for any given B > 0, the following regret and constraint-violation gap results hold: 任意の b > 0 に対して最適な静的ポリシー π∗ に対して、以下の後悔と制約違反ギャップの結果が成り立つ。 0.61
REGπ∗ (B) = O(1), REGπ∗ (B)=O(1) 0.61
Dπ∗ (B) = O(cid:16) 1 B(cid:17). Dπ∗ (B) = O(cid:16) 1 B(cid:17) 0.76
Therefore, π∗ is asymptotically optimal, i.e. したがって π∗ は漸近的に最適である。 0.75
limB→∞ REGπ∗ Proof. limB→∞ REGπ∗ 証明。 0.57
The proof of Proposition 1 can be found in Appendix C. 命題 1 の証明は Appendix C で見ることができる。 0.69
(B)/B = 0 and limB→∞ Dπ∗ (B)/B = 0 およびlimB→∞ Dπ∗ 0.75
(7) (B) = 0. (7) (b) = 0 である。 0.84
In the next section, we will introduce a learning algorithm to achieve the performance of the optimal stationary randomized policy with low regret and constraint-violation . 次の節では、後悔や制約違反の少ない最適な定常ランダム化ポリシーの性能を達成するための学習アルゴリズムについて紹介する。 0.71
5 Algorithm Design Based on Empirical Lyapunov Drift Minimization 経験的リアプノフドリフト最小化に基づくアルゴリズム設計 0.54
In the previous section, we proved that the stationary randomized policy π∗ achieves the optimality in offline setting with small optimality gap and constraint-violation , which implies it can be used as a benchmark for the design and analysis of learning algorithms. 前節では、定常ランダム化ポリシ π∗ が、最小限の最適性ギャップと制約違反を持つオフライン環境での最適性を証明し、学習アルゴリズムの設計と解析のベンチマークとして使用できることを示す。 0.80
By using this, we will develop a dynamic learning algorithm based on the Lyapunov-drift-minim ization approach. これを用いて,Lyapunov-drift-mini mizationアプローチに基づく動的学習アルゴリズムを開発する。 0.88
For details about this dynamic optimization approach in offline setting, see [21, 22]. オフライン設定でのこの動的最適化アプローチの詳細は [21, 22] を参照してください。 0.82
We refer to Section 1.2 for the detailed discussion of the differences from related works in this space. この分野の関連作品との相違に関する詳細な議論については、第1.2節を参照。 0.58
We make two mild assumptions that are needed for the development and analysis of our design: Assumption 1 (ǫ-Slater Condition). 我々は、我々の設計の開発と分析に必要な2つの軽微な仮定を下記のように作成する。
訳抜け防止モード: 2つの控えめな仮定をしました 設計の展開と分析に必要である : 仮定 1 ( 〜 - slater condition )
0.77
There exists an arm k ∈ K such that E[Yn,k − cXn,k] ≤ −ǫ for some ǫ > 0. 腕 k ∈ K が存在して、E[Yn,k − cXn,k] ≤ − がある > 0 に対して成立する。 0.83
We assume that either ǫ or a positive lower-bound on it is known. 我々は、その上で s または正の下界が知られていると仮定する。 0.62
To see that Assumption 1 is reasonable, note that for feasibility, either all arms should satisfy E[Yn,k − cXn,k] = 0 for all k or Assumption 1 should hold, otherwise the constraint cannot be satisfied. 仮定 1 が妥当であることを示すためには、すべての腕がすべての k に対して e[yn,k − cxn,k] = 0 を満たすか、仮定 1 が成り立つか、制約を満たさないかに注意する。
訳抜け防止モード: 仮定 1 が妥当であることを示すには。 実現可能性については、両腕ともE[Yn]を満たすべきである。 k − cXn, k ] = 0 for all k or Assumption 1 should hold。 そうでなければ 制約は満たせない
0.76
Since E[Yn,k − cXn,k] = 0, ∀k ∈ K is a trivial case, Assumption 1 is satisfied in almost all applications. E[Yn,k − cXn,k] = 0 であるから、E[Yn,k − cXn,k] = 0 は自明な場合であり、仮定 1 はほとんど全ての応用において満足する。
訳抜け防止モード: E[Yn, k − cXn, k ] = 0 である。 K は自明な場合である。 仮定1は、ほぼ全てのアプリケーションで満たされる。
0.78
5 5 0.85
英語(論文から抽出)日本語訳スコア
E[Y1,k] Assumption 2 (Bounded Moments). E[Y1,k] 仮定2(境界付きモーメント)。 0.80
For all arms k ∈ K, assume maxk maxk mink E[X1,k] ≥ µmin > 0. すべての腕 k ∈ K に対して、maxk maxk mink E[X1,k] ≥ μmin > 0 とする。 0.88
We assume that a lower bound of µmin and upper bounds on rmax, ymax are known. 我々は、μmin の下限と rmax, ymax 上の上限が知られていると仮定する。 0.82
E[X1,k] ≤ ymax < ∞. E[X1,k] ≤ ymax < ∞。 0.90
In addition, assume σ2 = maxk∈K E(cid:2)(cid:0)Y1,k − cX1,k(cid:1)2(cid:3) < 1, and さらに、σ2 = maxkhtmlk e(cid:2)(cid:0)y1,k − cx1,k(cid:1)2(cid:3) < 1 と仮定する。 0.77
E[X1,k] ≤ rmax < ∞ and E[X1,k] ≤ rmax < ∞ および 0.91
E[R1,k] This assumption is reasonable because otherwise the optimization problem in (4) would become either trivial or unsolvable. E[R1,k] この仮定は理にかなっている、なぜなら (4) の最適化問題は自明か未解決になるからである。 0.80
5.1 Offline Lyapunov-Drift Minimizing Policy LyOff Design 5.1 オフラインリアプノフドリフト政策LyOff設計 0.61
First, we consider the Lyapunov optimization methods in the offline setting with known first-order statistics by closely following [22], while improving the results for finite-time performance by using the drift results in [14]. まず, [22] に近づき, [14] にドリフト結果を用いることで, 有限時間性能の向上を図りながら, 既知の1次統計量を持つオフライン環境でのリアプノフ最適化手法を検討する。 0.82
As a measure of constraint-violation under a causal policy π ∈ Π, we define the variables Qπ 因果ポリシー π ∈ π の下での制約違反の尺度として、変数 Qπ を定義する。
訳抜け防止モード: 制約の尺度として、因果ポリシー π ∈ π による違反 変数 qπ を定義する
0.77
n recursively as follows: n は次のように再帰する。 0.49
Qπ n+1 = maxn0, Qπ Qπ n+1 = maxn0, Qπ 0.75
n + Y π no, n − (c − δ)X π n + Y π No, n − (c − δ)X π 0.84
(8) n+1 ∈ F π (8) n+1 ∈ F π 0.85
where Q0 = 0 and δ ∈ [0, c) is a fixed parameter that controls the tightness of the constraint. ここで Q0 = 0 と δ ∈ [0, c) は制約の厳密性を制御する固定パラメータである。 0.83
Note that Qπ n}n implies that the constraint is satisfied. Qπ n}n は制約が満たされることを意味することに注意。 0.71
The key metric for decision-making is the Lyapunov drift-plus-penalty ratio, which is defined in the following definition. 意思決定の鍵となる指標は、次の定義で定義されるリャプノフドリフトプラスペナルティ比である。 0.67
Definition 5 (Lyapunov Drift-plus-Penalty Ratio). 定義5(Lyapunov Drift-plus-Penalty Ratio)。 0.72
For any given V > 0, under a causal policy π, the Lyapunov drift-plus-penalty ratio is defined as follows: 任意の V > 0 に対して、因果ポリシー π の下で、リャプノフのドリフトプラスペナルティ比は次のように定義される。 0.59
n for all n since π is causal. π が因果であるからである。 0.55
Intuitively, the stability of {Qπ 直観的には、Qπの安定性 0.71
Ψn(Qπ n) = −V ψn(qπ) n) = −V 0.81
E[Rπ E[X π E[Rπ E[X π] 0.90
n|F π n|F π n|F π n|F π 0.65
n−1] n−1] + Qπ n n−1] n−1] + Qπ n 0.80
E[Y π E[X π E[Y π E[X π] 0.91
n |F π n|F π n |F π n|F π 0.78
n−1] n−1] . n−1] n−1] . 0.75
(9) For any stationary randomized policy π(pn), with pn ∈ Fn−1, the Lyapunov drift-plus-penalty ratio becomes: (9) 任意の定常ランダム化ポリシー π(pn) に対し、pn ∈ fn−1 は lyapunov drift-plus-penalty ratio となる。 0.77
Ψn(Qπ(pn) ψn(qπ(pn)) 0.77
n ) = −VPK PK n ) = −VPK PK 0.92
k=1 pn,kE[Rn,k] k=1 pn,kE[Xn,k] k=1 pn,kE[Rn,k]k=1 pn,kE[Xn,k] 0.96
+ Qπ(pn) n PK PK + Qπ(pn) n PK PK 0.92
k=1 pn,kE[Yn,k] k=1 pn,kE[Xn,k] k=1 pn,kE[Yn,k]k=1 pn,kE[Xn,k] 0.96
. (10) Intuitively, in the offline setting where all first-order moments are known, a stationary randomized policy π(pn) that minimizes (10) over all probability distributions in every epoch n, achieves a near-optimal trade-off between the cumulative reward and constraint-violation determined by the parameter V > 0 [22]. . (10) 直感的には、すべての一階のモーメントが知られているオフライン環境では、各エポック n における全ての確率分布に対して (10) を最小化する定常ランダム化ポリシー π(pn) が、パラメータ V > 0[22] で決定される累積報酬と制約違反の間のほぼ最適トレードオフを達成する。 0.81
In the following, we outline this result in the offline setting, which will guide us in developing the online algorithm in Section 5.2. 以下に、この結果をオフライン設定で概説し、第5章2節でオンラインアルゴリズムの開発について紹介する。 0.75
Definition 6 (Offline Lyapunov-Drift-Minim izing Distribution). 定義6 (Offline Lyapunov-Drift-Minim izing Distribution)。 0.72
For any n, let q∗n be defined as follows: 任意の n に対して、q∗n を次のように定義する。 0.53
q∗n ∈ arg min p∈∆K q∗n ∈ arg min p~nK 0.65
Ψn(Qπ(p) n ψn(qπ(p)) n 0.81
). (11) The problem in (11) is an optimization problem over ∆K , the K-dimensional probability simplex, which is computationally complex and can be solved by using algorithmic techniques in [22]. ). (11) (11) の問題は、[22] のアルゴリズム技術を用いて計算的に複雑であり、解ける K-次元確率の単純さである K-次元上の最適化問題である。 0.84
However, as it is shown in Proposition 5 in Appendix D, the optimal solution in our K-armed bandit setting is deterministic given the history Fn−1. しかし、 Appendix D の命題 5 で示されるように、我々の K 武装バンディット設定における最適解は、歴史 Fn−1 を考えると決定論的である。
訳抜け防止モード: しかし、付録dの命題5に示すように、 k-武装バンディット設定における最適解は、履歴 fn−1 を考えると決定論的である。
0.68
This allows us to define the offline Lyapunov-Drift Minimizing Policy πLyOff as in Algorithm 1. これにより、Ryapunov-Drift最小化ポリシー πLyOff をアルゴリズム1で定義できる。 0.78
Intuition: The policy πLyOff makes a balanced choice between the reward maximization and satisfying the constraints. 直観:ポリシー πLyOff は報酬の最大化と制約を満たすためのバランスのとれた選択をする。 0.71
For small Qn, the controller selects the arm kn with the highest drift-plus-penalty ratio so as to maximize the expected total reward under the budget constraints. 小さなqnの場合、コントローラは予算制約下での期待総報酬を最大化するために、最もドリフトプラスペナルティ比の高いarm knを選択する。 0.59
If Qn is large, then it means the constraint has been violated considerably, thus kn is selected so as to reduce the penalty rate and hence violation level. Qnが大きければ、制約がかなり違反していることを意味するので、knはペナルティレートを下げ、したがって違反レベルを下げるために選択される。 0.64
Next, we prove finite-time performance bounds for πLyOff. 次に、πLyOff に対する有限時間性能境界を証明する。 0.59
Proposition 2 (Performance Bounds for πLyOff). 命題2(πLyOffのパフォーマンス境界)。 0.57
Suppose that Assumption 1 and Assumption 2 hold with positive ǫ, σ2, rmax and µmin. 仮定 1 と仮定 2 が正の σ2, rmax, μmin で成り立つと仮定する。 0.73
Then, given the budget B, for any V > 0 and δ ∈ [0, c), the regret and constraint-violation levels under πLyOff satisfy: すると、予算 B が与えられたとき、任意の V > 0 および δ ∈ [0, c) に対して、πLyOff の下での後悔と制約-違反レベルが満たされる。 0.61
REGπLyOff(B) = O σ2B REGπLyOff(B) = O σ2B 0.78
V µ2 min δrmaxB ǫµ2 V μ2 ミン δrmaxbはμ2である。 0.57
min !, + DπLyOff(B) = O(cid:16) 1 ミン! + DπLyOff(B) = O(cid:16) 1 0.68
B + V rmax Bµminǫ − B + V rmax Bμmin 0.84
δ µmin(cid:17). δ μmin (cid:17)。 0.79
(12) 6 (12) 6 0.85
英語(論文から抽出)日本語訳スコア
Specifically, for V = v0√B and δ = δ0/√B with some design parameters δ0 > 0, v0 > 0, we have 具体的には、いくつかの設計パラメータ δ0 > 0, v0 > 0 の v = v0 と δ = δ0/\b に対して、 0.69
REGπLyOff(B) = O(cid:16)√B(cid:17), REGπLyOff(B) = O(cid:16) = B(cid:17) 0.80
DπLyOff(B) = O(cid:16) 1 B(cid:17) DπLyOff(B) = O(cid:16) 1 B(cid:17) 0.84
(13) Proof. The proof of Proposition 2 can be found in Appendix D.1. (13) 証明。 命題2の証明は Appendix D.1 で見ることができる。 0.72
Proposition 2 establishes the fact that πLyOff achieves O(√B) regret and O(1/B) constraintviolation for a time-horizon B given the first-order statistics E[Xn,k], E[Rn,k], E[Yn,k] for all arms k ∈ K. The πLyOff policy will serve as a guide for our online learning algorithm, introduced next. 命題2は、πLyOff が全腕 k ∈ K に対して第一次統計量 E[Xn,k], E[Rn,k], E[Yn,k] を与えられた時間-水平 B に対する O(\B) 後悔と O(1/B) 制約を達成しているという事実を証明している。 0.64
Algorithm 1 LyOff Algorithm アルゴリズム1 LyOffアルゴリズム 0.68
Algorithm 2 LyOn Algorithm アルゴリズム2 LyOnアルゴリズム 0.69
1: Input: B, K, c, V, δ, 2: 3: Initialize Q0 = 0, cost = 0, n = 1 4: while cost ≤ B do 1: Input: B, K, c, V, δ, 2: 3: Initialize Q0 = 0, cost = 0, n = 1 4: while cost ≤ B do 0.87
E[X1,k], E[R1,k], E[Y1,k] E[X1,k], E[R1,k], E[Y1,k] 0.89
Ψn(k, Qn) = −V E[R1,k] E[X1,k] + Qn kn = arg mink∈K Ψn(k, Qn) Select arm kn. シュン(k, Qn) = −V E[R1,k] E[X1,k] + Qn kn = arg mink(K )n(k, Qn) Select arm kn。 0.93
Observe Xn, Rn, Yn. Xn, Rn, Yn を観測する。 0.82
5: E[Y1,k] E[X1,k] 5: E[Y1,k]E[X1,k] 0.91
Qn+1 = max(cid:8)0, Qn+Yn−(c−δ)Xn(cid:9) Qn+1 = max(cid:8)0, Qn+Yn−(c−δ)Xn(cid:9) 0.71
cost = cost + Xn. コスト = コスト + Xn。 0.73
n = n + 1. n = n + 1 である。 0.86
6: 7: 8: 9: 10: 11: 12: end while 6: 7: 8: 9: 10: 11: 12: end while 0.85
1: Input: B, K, c, α, V, δ, β0, µmin 2: Initialize Q0 = 0, cost = 0, n = 1 1:入力: B, K, c, α, V, δ, β0, μmin 2:初期化 Q0 = 0, コスト = 0, n = 1 0.92
5: while cost ≤ B do 5: ≤ B のコストである。 0.83
µmin(cid:1)(cid:7) times. μmin (cid:1) (cid:7) times。 0.75
3: Select each arm(cid:6)β0 log(cid:0) 2B 4: Update n, cost,bΓn(k, Qn) (eq. 3: 各アーム(cid:6)β0 log(cid:0) 2B 4: Update n, cost,b'n(k, Qn) (eq) を選択する。 0.80
(16)). kn = arg mink∈K(cid:8)bΓn(k, Qn)(cid:9) Qn+1 = max(cid:8)0, Qn+Yn−(c−δ)Xn(cid:9) UpdatebΓn(k, Qn) (eq. (16)). kn = arg mink(K(cid:8, Qn)(cid:9) Qn+1 = max(cid:8)0, Qn+Yn−(c−δ)Xn(cid:9) Updateb\n(k, Qn) (eq)。 0.84
(16)). 6: 7: 8: 9: 10: 11: 12: end while (16)). 6: 7: 8: 9: 10: 11: 12: end while 0.85
Select arm kn. arm kn を選択します。 0.59
Observe Xn, Rn, Yn. Xn, Rn, Yn を観測する。 0.82
cost = cost + Xn. コスト = コスト + Xn。 0.73
n = n + 1. n = n + 1 である。 0.86
5.2 Online Lyapunov-Drift Minimizing Policy LyOn Design 5.2 オンラインリアプノフドリフト政策LyOn設計 0.64
A strong assumption in πLyOff was the a priori knowledge of the first-order statistics for all variables. πlyoff の強い仮定は、すべての変数に対する一階統計の事前知識である。 0.70
Recall that in the learning problem, we do not have this knowledge. 学習問題では、私たちはこの知識を持っていません。 0.77
Instead, we must work with estimations by using the observed outcomes from bandit type feedback to learn the optimal decision. 代わりに、バンド型フィードバックの観測結果を用いて最適決定を学習し、見積もりを行なわなければならない。 0.72
Furthermore, like all exploration-exploita tion problems, the online exploration is a crucial component of the learning problem here as well. さらに、すべての探索・探索問題と同様に、オンライン探索もここでの学習問題の重要な要素である。 0.64
Optimizing this trade-off with low regret and constraint-violation is particularly challenging in this setting due to the knapsack-type budget constraints from random costs, as well as the random penalties in the constraint. 低い後悔と制約違反でこのトレードオフを最適化することは、ランダムなコストによるknapsack型の予算制約と、制約のランダムな罰則により、この設定において特に難しい。 0.61
In this section, we will design and analyze the LyOn Algorithms by combining tools from renewal theory, stochastic control, as well as bandit optimization to address these challenges for optimal learning. 本稿では,リニューアル理論,確率制御,帯域最適化といったツールを組み合わせてLyOnアルゴリズムの設計と解析を行い,これらの課題を最適学習のために解決する。 0.85
Strategy: Our strategy will be to approximate the Lyapunov drift-plus-penalty ratio Ψn in equation (41) by using the empirical estimates for the first-order statistics. 戦略:1次統計量に対する経験的推定値を用いて,式(41)におけるリアプノフのドリフトプラスペナルティ比 ψn を近似する。 0.73
In order to encourage online exploration, we will use confidence bounds so that the index at the end will be a high-probability lower bound for Ψn. オンラインの探索を促進するために、最後にある指数が ψn に対して高い確率下限となるよう、信頼度境界を用いる。 0.71
The following definitions will be needed to define the online algorithm. オンラインアルゴリズムを定義するには、以下の定義が必要である。 0.73
Definition 7 (Confidence Radius). 定義7 (Confidence Radius)。 0.74
For any n ≥ 1 and arm k ∈ K, let I π n (k) = {t ∈ [1, n] : I π t = k}, T π t = k} be the number of pulls for arm k under a policy π in the first n epochs. 任意の n ≥ 1 およびアーム k ∈ K に対して、I π n (k) = {t ∈ [1, n] : I π t = k}, T π t = k} を、最初の n のエポックにおけるポリシー π の下でのアーム k のプル数とする。 0.85
For a given α > 0, the confidence radius for arm k is defined as: 与えられた α > 0 に対して、arm k の信頼半径は次のように定義される。 0.72
I{I π t=1 I{I π t=1。 0.66
n (k)| = Pn n (k)| = Pn 0.85
k (n) = |I π . k (n) = |I π 。 0.84
radk(n, α) =q 2α log(n) radk(n, α) =q 2α log(n) 0.98
Tk(n) To ensure the confidence radius is small enough, we have an initial exploration phase that is controlled by a parameter β0 which depends on ǫ, ymax, and µmin. Tk(n) 信頼半径が十分に小さいことを保証するため、初期探索フェーズがあり、パラメータ β0 によって制御されるが、これは s, ymax, μmin に依存する。 0.80
Specifically, we set β0 = 32α(1+ymax)2 具体的には、β0 = 32α(1+ymax)2 とする。 0.62
. µ2 minǫ2 For a subset of indices S ⊂ N and a stochastic process {Zn : n ∈ N}, letbES[Z] = 1 . µ2 ミン2 指数 S > N の部分集合と確率過程 {Zn : n ∈ N} に対して、letbES[Z] = 1 である。 0.74
be the empirical mean estimator. 経験的平均推定値である。 0.61
Then, the empirical reward rate and empirical penalty rate under policy π after n epochs are defined as: そして、nエポック後の政策πにおける経験的報酬率と経験的ペナルティ率を次のように定義する。 0.58
|S|Pt∈S Zt, n,k = bEI π brπ bEI π S|Pt~S Zt n,k = bEI π brπ bEI π 0.72
n (k)[Rk] n (k)[Xk] n (k)[Rk]n (k)[Xk] 0.73
, and byπ n,k = bEI π bEI π , πによって n,k = bEI π bEI π 0.75
7 n (k)[Yk] n (k)[Xk] 7 n (k)[Yk]n (k)[Xk] 0.79
, k ∈ K. (14) , k ∈ K。 (14) 0.84
英語(論文から抽出)日本語訳スコア
Definition 8 (Empirical Lyapunov Drift-Plus-Penalty Ratio). 定義8(Lyapunov Drift-Plus-Penalty Ratio)。 0.79
Let Qπ n be the variable evolving under π as in (8). Qπ n を (8) のように π の下で進化する変数とする。 0.77
Then, the empirical Lyapunov drift-plus-penalty ratio at epoch n is defined as follows: 次に、エポックnにおける経験的リアプノフドリフトプラスペナルティ比を次のように定義する。 0.53
where V > 0 is a design parameter. ここで v > 0 は設計パラメータである。 0.90
Define the empirical lower confidence bound forbΨn(k, Qπ n−1(k)[Xk] # n(1 +byπ bEI π 経験的低信頼境界 forb\n(k, Qπ n−1(k)[Xk] # n(1 +byπ bEI π を定義する。 0.76
bΨn(k, Qπ n ·byπ n) − radk(n − 1, α)" V (1 +brπ bEI π bn(k, Qπ n ·byπ n) − radk(n − 1, α)" V(1 +brπ bEI π) 0.94
n) = bΨn(k, Qπ n) = bn(k, Qπ 0.94
n) = −V ·brπ n) = −V ·brπ 0.78
With these definitions, the online Lyapunov-Drift Minimizing Algorithm LyOn is defined in Algorithm 2. これらの定義により、Lyapunov-Drift Minimizing Algorithm LyOnはアルゴリズム2で定義される。 0.82
bΓn(k, Qπ n−1,k) n−1(k)[Xk] bn(k, Qπ) n−1,k)n−1(k)[Xk] 0.88
n−1,k + Qπ n−1,k + Qπ 0.78
n−1,k) n−1,k, n−1,k) n−1,k。 0.82
n) as Qπ + (15) n) Qπ + (15) 0.76
(16) Remark 1. Before we analyze it, we make the following observations about the LyOn Algorithm. (16) 備考1。 解析する前に、LyOnアルゴリズムについて以下の観察を行う。 0.67
1. Lyon is an extremely low-complexity, iterative algorithm, whereby in every step a simple update is performed. 1. Lyonは非常に複雑で反復的なアルゴリズムであり、各ステップで簡単な更新が行われる。 0.84
2. The index to be minimized in (16) is a high-probability lower bound for Ψn(k, QπLyOn given the available data F πLyOn the face of uncertainty. 2. (16) で最小化される指数は、不確実性に直面した利用可能なデータ f πlyon に対して ψn(k, qπlyon) に対して高い確率下限である。 0.72
3. If I πLyOn n = k, then at least one of the following must be true: a) High confidence for arm k, large rk and small QπLyOn and small yk. 3. I πLyOn = k であれば、次の少なくとも 1 つが真でなければならない: a) 腕 k 、大きな rk 、小さな QπLyOn および小さな yk に対する高い信頼。 0.84
c) Low confidence for arm k. As such, the LyOn Algorithm incentivizes online exploration by choosing arms with very low confidence. c) arm k に対する信頼度が低いため、lyon アルゴリズムは、非常に低い信頼度で腕を選択することによって、オンライン探索をインセンティブ化する。 0.60
). Thus, n−1 , the algorithm makes an optimistic drift-minimizing arm selection in ). したがって、n−1 では、アルゴリズムは楽観的なドリフト最小アーム選択を行う。 0.69
. b) High confidence for arm k, large QπLyOn . b) arm k, large qπlyon に対する高い信頼度 0.81
n n n 4. The LyOn Algorithm extends the UCB-BwI Algorithm proposed in [10] to the non-trivial and useful cases with stochastic feasibility constraints. n n n 4. LyOn Algorithm は[10] で提案された UCB-BwI Algorithm を確率的実現可能性制約を持つ非自明かつ有用なケースに拡張する。 0.82
Note that QπLyOn n = 0 if there is no constraint, thus the LyOn Algorithm reduces to the UCB-BwI Algorithm. QπLyOn = 0 で制約がなければ、LyOn Algorithm は UCB-BwI Algorithm に還元される。 0.74
Theorem 1 (Performance Bounds for πLyOn). Theorem 1 (πLyOnのパフォーマンス境界)。 0.76
Suppose that Assumption 1 and Assumption 2 hold with positive ǫ, σ2, rmax, ymax, and µmin. 仮定 1 と仮定 2 が正の π, σ2, rmax, ymax, μmin を持つとする。 0.73
Then, for any V > 0 and δ ∈ [0, c), the regret and constraint-violation levels under πLyOn satisfy: すると、任意の V > 0 および δ ∈ [0, c) に対して、πLyOn の下での後悔と制約-違反レベルが満たされる。
訳抜け防止モード: すると、任意の v > 0 と δ ∈ [ 0, に対して c ) 後悔と制約 - πlyon による違反レベル:
0.78
REGπLyOn (B) = O rmax√B log B REGπLyOn (B) = O rmax\B log B 0.81
µ2 min +(cid:16) σ2 + ymax + δ log B µ2 ミン +(cid:16) σ2 + ymax + δ log B 0.74
V µ2 min + DπLyOn(B) = O y2 V μ2 ミン + DπLyOn(B) = O y2 0.77
maxK log B ǫ2µ2 maxK log B >2μ2 0.68
minB + V rmax Bµminǫ − minB + V rmax Bμmin 0.84
δrmax ǫµ2 δrmax (複数形 δrmaxs) 0.32
min(cid:17)B + µmin!, min(cid:17)B + μmin! 0.93
δ y2 maxK log B δ y2 maxK log B 0.92
min !, ǫ2µ2 (17) ミン! ǫ2µ2 (17) 0.55
(18) Specifically, for V = v0√B log B and δ = δ0plog B/B with some design parameters δ0 > 0, v0 > (18) 具体的には、V = v0\B log B と δ = δ0plog B/B に対して、いくつかの設計パラメータ δ0 > 0, v0 > 0.76
0, we have REGπLyOn(B) = O(cid:16)pB log B(cid:17), 0です REGπLyOn(B) = O(cid:16)pB log B(cid:17) 0.63
B (cid:17) DπLyOn (B) = O(cid:16) K log B B (cid:17) DπLyOn (B) = O(cid:16) K log B 0.87
Theorem 1 implies that πLyOn achieves O(√B log B) regret and O(K log B/B) constraint-violation for a time horizon B while learning the first order statistics under a bandit feedback. 定理 1 は、πLyOn が、バンドイットフィードバックの下で第1次統計学を学習しながら、時間地平線 B に対する O(\B log B/B) の後悔と O(K log B/B) の制約違反を達成することを示唆する。
訳抜け防止モード: Theorem 1 は πLyOn が O(\B log B ) の後悔を達成することを示唆する と O(K log B / B ) 制約 - 時間軸 B に違反する バンディットのフィードバックの下で 一階の統計を学習しました
0.72
(19) Proof. The proof of Theorem 1 can be found in Appendix E. (19) 証明。 Theorem 1 の証明は Appendix E で見ることができる。 0.76
In addition to the fact that cumulative reward and penalty processes form stopped and controlled random walks, the main challenge in analyzing the LyOn algorithm performance is that Qn is correlated with the sample path. 累積報酬とペナルティプロセスが停止・制御されたランダムウォークを形成することに加えて、LyOnアルゴリズムの性能解析における主な課題は、Qnがサンプルパスと相関していることである。 0.79
To address this, we prove a maximal inequality for Qn under a concentration event (Lemma 7 in Appendix E), which can have its own value in other queuing systems. これに対処するために、集中イベント(付録eの補題7)の下でqnの最大不等式を証明し、他のキューシステムで独自の値を持つことができる。 0.63
Also note that, compared with LyOff, the online algorithm has a very small increase on the regret and the constraint-violation bounds by factors of √log B and log B, respectively. また、LyOff と比較すると、オンラインアルゴリズムは、後悔と制約違反の境界がそれぞれlog B と log B の因子によって非常に小さい。 0.61
This is a reasonable price to pay since we are not assuming any known statistics. 既知の統計を仮定していないので、これは妥当な価格です。 0.82
To the best of our knowledge, these are the best results available on both regret and constraint violation in the current setup. 私たちの知る限りでは、これらは現在のセットアップにおける後悔と制約違反の両方で得られる最良の結果です。 0.68
8 8 0.85
英語(論文から抽出)日本語訳スコア
6 Simulations We implement both LyOff and LyOn algorithms for K = 2 arms with Bernoulli distributed rewards, costs, and penalties. 6シミュレーション 我々は,K = 2腕のLyOffアルゴリズムとLyOnアルゴリズムをBernoulli分散報酬,コスト,罰則を用いて実装する。 0.76
Assuming c = 0.8, arm 1 is selected to have a high reward rate and a high penalty rate with E[X1] = 0.4, E[Y1] = 0.6, and E[R1] = 0.8. c = 0.8と仮定すると、腕1は報酬率が高く、E[X1] = 0.4、E[Y1] = 0.6、E[R1] = 0.8である。 0.85
Arm 2 is selected to have a low reward rate and a low penalty rate with E[X2] = 0.6, E[Y2] = 0.3, and E[R2] = 0.6. アーム2は、E[X2] = 0.6、E[Y2] = 0.3、E[R2] = 0.6の低い報酬率と低いペナルティ率を有するように選択される。 0.78
These values are interesting in that, an optimal controller will have to make a trade-off between the two arms, whereas any static policy selecting one of the arms will result in either linear regret or linear constraint-violation . これらの値は興味深いが、最適コントローラーは2つのアーム間のトレードオフをしなければならないが、一方のアームを選択する静的ポリシーは線形後悔または線形拘束違反をもたらす。 0.68
t e a R d r a w e R t e a R d r a w e R 0.85
0.9 0.85 0.8 0.9 0.85 0.8 0.59
0 n o i t a c o 0 n o i t a c o 0.85
l l A e m T L -L a e m t 0.68
i f o n o i t c a r F 私は f o n o i t c a r F 0.69
0.6 0.5 0.4 0.6 0.5 0.4 0.59
0 LyOff LyOn 0 LyOff LyOn 0.85
* 5 B (a) 10 104 * 5B (a) 10 104 0.83
* Arm 2 * Arm 1 ※アーム2*アーム1 0.73
LyOff Arm 2 LyOff Arm 1 LyOn Atm 2 LyOn Atm 1 LyOff Arm 2 LyOff Arm 1 LyOn Atm 2 LyOn Atm 1 0.85
5 B (c) 10 104 5B (c) 10 104 0.83
n o 0.1 i t ん? 0.1 i t です 0.60
l a o V うーん o v (複数形 ovs) 0.42
i t i n a r t s n o C 私は t 私は n a r t s n o C 0.69
0.08 0.06 0.04 0.08 0.06 0.04 0.59
0.02 0 0 n o i t a o V 0.02 0 0 n o i t a o V 0.78
i l i t n a r t s n o C 私は うーん 私は t n a r t s n o C 0.59
0.3 0.2 0.1 0.3 0.2 0.1 0.59
0 0 LyOff LyOn 0 0 LyOff LyOn 0.85
2 4 B (b) 6 104 2 4 B (b) 6 104 0.85
B=2 104 B=3 104 B=4 104 B=2104B=3104B=4104 0.76
50 K (d) 100 50K (d) 100 0.79
Figure 1: Performance of LyOff and LyOn (v0 = 1, δ0 = 0.5). 図1: LyOff と LyOn のパフォーマンス(v0 = 1, δ0 = 0.5)。 0.87
(a) (K=2) Reward rate (REW(B)/B). (a) (K=2)後退率(REW(B)/B) 0.82
(b) (K=2) constraint-violation . (b)(K=2)制約違反 0.70
(c) (K=2) Proportion of time allocated to each arm. (c) (K=2)各腕に割り当てられた時間の配分 0.84
(d) Constraintviolation for LyOn as K increases for different B. (d) 異なるBではKが増加するにつれてLyOnの禁忌が増加する。 0.55
Figure 1 shows the simulation results (averaged over 104 runs) with v0 = 1 and δ0 = 0.5 for LyOff and LyOn algorithms. 図1は、v0 = 1とδ0 = 0.5のLyOffアルゴリズムとLyOnアルゴリズムによるシミュレーション結果(平均104ラン以上)を示している。 0.74
To observe the reward rate behavior, in Figure 1a, we plot the reward rates REWπ(B)/B of πLyOff and πLyOn and the optimal randomized policy π∗, with varying budgets B. 報酬率の挙動を観察するために、図1aでは、πlyoff と πlyon の報酬率 rewπ(b)/b と最適なランダム化ポリシー π∗ を予算bでプロットする。 0.74
This figure shows that both the offline and the online designs reach the rate of the optimal design, as predicted by our analysis. この数値は、オフラインデザインとオンラインデザインの両方が最適設計の速度に達することを示している。
訳抜け防止モード: この図は、オフラインとオンラインの両方の設計が最適設計の速度に達することを示している。 分析が予測した通りです
0.73
Also, Figure 1b verifies the fast decaying of constraint-violation with rate ˜O(1/B) as B increases, which confirms the scaling behaviour revealed in our analyses. また、図1bは、bが増加するにつれて、制約違反の急速な減衰を検証し、分析で明らかになったスケーリング挙動を確認します。 0.63
Figure 1c further confirms the convergence of LyOff and LyOn towards π∗ by showing the proportion of time allocated to each arm. 図1cは、各アームに割り当てられた時間の割合を示すことにより、LyOff と LyOn の π∗ への収束をさらに確認する。 0.63
To check the performance of our algorithms for larger K, we increase the number of arms by adding arms with the principle that high reward rate arm also has high penalty rate (otherwise the arms are not competitive). より大きなKに対するアルゴリズムの性能を確認するために、高い報酬率のアームも高いペナルティ率(そうでなければ腕が競合しない)を持つという原則で腕を追加することで、腕の数を増やす。 0.68
Figure 1d shows the constraint-violation of LyOn as K increases under different values of B. 図1dは、K が B の異なる値の下で増加するにつれて、LyOn の制約違反を示す。 0.56
It can be seen that as B increases, the constraint-violation grows at slower rate with respect to K and the growth starts to take the linear form predicted by our analysis as K grows. B が増加するにつれて、制約違反は K に対して遅い速度で増加し、K が成長するにつれて、我々の分析によって予測される線形形式を取るようになる。 0.69
In Appendix F, in addition to providing more numerical results for different v0 and δ0 values, we also investigate the effect of design choices V and δ to capture the tradeoff between constraint-violation and regret under the LyOff and LyOn algorithms. Appendix Fでは、異なるv0とδ0の値に対してより数値的な結果を提供するとともに、LyOffアルゴリズムとLyOnアルゴリズムの制約違反と後悔のトレードオフを捉えるために、設計選択Vとδの効果についても検討する。 0.67
9 9 0.85
英語(論文から抽出)日本語訳スコア
7 Conclusion In this paper, we proposed a broadly applicable computationally efficient methodology based on Lyapunov-drift-minim ization for solving a penalty-constrained reward maximization problem with a limited budget, random costs, and bandit feedback. 7 結論 本稿では,リヤプノフ・ドリフト最小化に基づく計算効率の高い手法を提案し,予算,ランダムコスト,バンディットフィードバックを限定したペナルティ制約付報酬最大化問題を解く。 0.74
Both offline and online algorithms are developed based on this design methodology, which are also proven to have sharp regret and constraintviolation performance. オフラインとオンラインの両方のアルゴリズムは、この設計手法に基づいて開発されており、鋭い後悔と制約違反のパフォーマンスを持つことも証明されている。 0.56
The approach and algorithms are applicable in diverse domains whereby knapsack budget constraints and stochastic feasibility constraints are required. アプローチとアルゴリズムは、knapsackの予算制約と確率的実現可能性制約が要求される様々な領域に適用できる。
訳抜け防止モード: アプローチとアルゴリズムは多様な領域に適用できる knapsack予算の制約と確率的実現可能性の制約が必要です。
0.76
An interesting future work that can benefit from the same methodology would be to extend our setting to the scenario of infinitely many arms. 同じ方法論の利点を享受できる興味深い将来の仕事は、我々の設定を無限に多くの武器のシナリオにまで広げることでしょう。 0.71
References [1] Shipra Agrawal and Nikhil R Devanur. 参考文献 [1]shipra agrawalとnikhil r devanur。 0.59
Bandits with concave rewards and convex knapsacks. コンケーブの報酬と凸ナプサックを持つバンド。 0.61
In Proceedings of the fifteenth ACM conference on Economics and computation, pages 989–1006. 第15回acm経済計算会議の議事録989-1006頁。 0.56
ACM, 2014. 2014年、ACM。 0.89
[2] Søren Asmussen. ソレン・アスムッセン(Søren Asmussen)。 0.55
Applied probability and queues, volume 51. 適用確率と待ち行列、巻51。 0.69
Springer Science & Business Springer Science & Business 0.85
Media, 2008. 2008年、メディア。 0.89
[3] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. [3] ashwinkumar badanidiyuru、robert kleinberg、aleksandrs slivkins。 0.59
Bandits with knapIn 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages knapin 2013年ieee 54th annual symposium on foundations of computer science, pages 0.70
sacks. 207–216. 袋だ 207–216. 0.65
IEEE, 2013. 2013年、IEEE。 0.59
[4] Santiago R Balseiro and Yonatan Gur. [4]サンティアゴ・ル・バルセイロとヨナタン・グル 0.40
Learning in repeated auctions with budgets: Regret 予算を伴う繰り返しオークションでの学習:レグレット 0.61
minimization and equilibrium. Management Science, 65(9):3952–3968, 2019. 最小化と均衡です Management Science, 65(9):3952–3968, 2019。 0.86
[5] Donald A Berry and Bert Fristedt. 5]Donald A BerryとBert Fristedt。 0.67
Bandit problems: sequential allocation of experiments (monographs on statistics and applied probability). バンディット問題:実験の逐次割り当て(統計と応用確率に関するモノグラフ)。 0.71
London: Chapman and Hall, 5:71–87, 1985. ロンドン: チャップマン・アンド・ホール, 5:71-87, 1985。 0.60
[6] Gabriel R Bitran and Thomas L Magnanti. 6]Gabriel R BitranとThomas L Magnanti。 0.70
Duality and sensitivity analysis for fractional pro- 分数proの双対性と感度解析 0.77
grams. Operations Research, 24(4):675–699, 1976. グラム 運用研究、24(4):675-699、1976年。 0.51
[7] J Frédéric Bonnans and Alexander Shapiro. J Frédéric BonnansとAlexander Shapiro。 0.51
Stability and sensitivity analysis. In Perturbation 安定性と感度分析。 摂動で 0.61
Analysis of Optimization Problems, pages 260–400. 最適化問題の解析 260-400頁。 0.72
Springer, 2000. スプリンガー、2000年。 0.57
[8] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al Regret analysis of stochastic and nonstochastic multi-armed bandit problems. 8] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al Regret analysis of stochastic and nonstochastic multi-armed bandit problem。 0.87
Foundations and Trends® in Machine Learning, 5(1):1–122, 2012. Foundations and Trends® in Machine Learning, 5(1):1-122, 2012 0.89
[9] Semih Cayci, Atilla Eryilmaz, and R Srikant. 9] Semih Cayci, Atilla Eryilmaz, R Srikant。 0.63
Budget-constrained bandits over general cost and reward distributions. 一般的なコストと報酬分布に対する予算制約付き盗賊。 0.57
In International Conference on Artificial Intelligence and Statistics, pages 4388–4398. International Conference on Artificial Intelligence and Statistics, page 4388–4398。 0.85
PMLR, 2020. PMLR、2020年。 0.88
[10] Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant. 10]Semih Cayci,Atilla Eryilmaz,Rayadurgam Srikant。 0.59
Learning to control renewal processes with bandit feedback. 包括的フィードバックによる更新プロセスの制御の学習 0.69
Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(2):43, 2019. 計算システムの計測と解析に関するACMの成果(3(2):43, 2019) 0.75
[11] Semih Cayci, Swati Gupta, and Atilla Eryilmaz. [11]Semih Cayci,Swati Gupta,Atilla Eryilmaz。 0.67
Group-fair online allocation in continuous グループフェアオンラインアロケーション 0.48
time. Advances in Neural Information Processing Systems, 33, 2020. 時間だ ニューラル情報処理システムの進歩 -2020年3月33日- 0.71
[12] Leonidas Georgiadis, Michael J Neely, and Leandros Tassiulas. 12] Leonidas Georgiadis, Michael J Neely, Leandros Tassiulas. 0.71
Resource allocation and cross- layer control in wireless networks. 資源配分とクロス- 無線ネットワークにおける層制御 0.83
Now Publishers Inc, 2006. 株式会社、2006年。 0.37
[13] Arpita Ghosh, Preston McAfee, Kishore Papineni, and Sergei Vassilvitskii. Arpita Ghosh氏、Preston McAfee氏、Kishore Papineni氏、Sergei Vassilvitskii氏。 0.57
Bidding for representative allocations for display advertising. ディスプレイ広告のための代表割当の入札。 0.75
In International workshop on internet and network economics, pages 208–219. インターネットとネットワーク経済に関する国際ワークショップ208-219頁。 0.69
Springer, 2009. [14] Bruce Hajek. 2009年春。 ブルース・ハジェク(Bruce Hajek)。 0.55
Hitting-time and occupation-time bounds implied by drift analysis with applica- 漂流解析による着地時間と職業時間の境界 0.69
tions. Advances in Applied probability, pages 502–525, 1982. イオンだ 応用確率の進歩, 502-525, 1982。 0.51
[15] Anikó Hannák, Claudia Wagner, David Garcia, Alan Mislove, Markus Strohmaier, and Christo Wilson. Anikó Hannák, Claudia Wagner, David Garcia, Alan Mislove, Markus Strohmaier, Christo Wilson。 0.60
Bias in online freelance marketplaces: Evidence from taskrabbit and fiverr. オンラインフリーランスマーケットプレースにおけるバイアス: Taskrabbitと5rrからの証拠。 0.74
In Proceedings of the 2017 ACM conference on computer supported cooperative work and social computing, pages 1914–1933, 2017. 2017 acm conference on computer supported collaborative work and social computingの議事録では、1914-1933, 2017 ページが紹介されている。
訳抜け防止モード: 2017 acm conference on computer supported collaborative work and social computingの開催にあたって 1914-1933年、2017年。
0.90
[16] Mor Harchol-Balter. [16]Mor Harchol-Balter 0.83
Task assignment with unknown duration. 時間不明のタスクの割り当て。 0.76
In Proceedings 20th IEEE 第20回IEEEの成果 0.59
International Conference on Distributed Computing Systems, pages 214–224. International Conference on Distributed Computing Systems, page 214-224。 0.89
IEEE, 2000. IEEE、2000年。 0.88
10 10 0.85
英語(論文から抽出)日本語訳スコア
[17] Panagiotis G Ipeirotis. [17]Panagiotis G Ipeirotis。 0.74
Analyzing the amazon mechanical turk marketplace. amazon mechanical turk marketplaceの分析。 0.75
XRDS: Cross- roads, The ACM Magazine for Students, 17(2):16–21, 2010. XRDS:クロス- acm magazine for students, 17(2):16–21, 2010 (英語) 0.80
[18] Amin Abdel Khalek, Constantine Caramanis, and Robert W Heath. 18] アミン・アブデル・ハレック、コンスタンティン・カラマニス、ロバート・w・ヒース 0.56
Delay-constrained video transmission: Quality-driven resource allocation and scheduling. delay-constrained video transmission: quality-driven resource allocation and scheduling。 0.79
IEEE Journal of Selected Topics in Signal Processing, 9(1):60–75, 2014. IEEE Journal of Selected Topics in Signal Processing, 9(1):60–75, 2014 0.88
[19] Tze Leung Lai and Herbert Robbins. 19]Tze Leung LaiとHerbert Robbins。 0.68
Asymptotically efficient adaptive allocation rules. 漸近的に効率的な適応割当規則。 0.54
Ad- vances in applied mathematics, 6(1):4–22, 1985. 広告 応用数学用語、1985年6(1):4–22頁。 0.68
[20] Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. [20]シン・リ、ビン・リ、ペンギ・シ、レー・ヨン。 0.45
Pond: Pessimistic-optimist ic online dispatch. pond: 悲観的最適化のオンラインディスパッチ。 0.43
arXiv preprint arXiv:2010.09995, 2020. arXiv arXiv:2010.09995, 2020 0.79
[21] Michael J Neely. 21]マイケル・j・ニーリー 0.60
Stochastic network optimization with application to communication and 確率的ネットワーク最適化と通信への応用 0.80
queueing systems. Synthesis Lectures on Communication Networks, 3(1):1–211, 2010. 待ち行列システム。 Synthesis Lectures on Communication Networks, 3(1):1–211, 2010 0.82
[22] Michael J Neely. 22]マイケル・j・ニーリー 0.58
Dynamic optimization and learning for renewal systems. 更新システムの動的最適化と学習 0.73
IEEE Transactions IEEEトランザクション 0.76
on Automatic Control, 58(1):32–46, 2012. On Automatic Control, 58(1):32–46, 2012 0.89
[23] Christos H Papadimitriou and John N Tsitsiklis. [23]Christos H PapadimitriouとJohn N Tsitsiklis。 0.75
The complexity of optimal queuing network 最適待ち行列ネットワークの複雑さ 0.79
control. Mathematics of Operations Research, 24(2):293–305, 1999. コントロール。 数学博士、24(2):293–305、1999年。 0.68
[24] Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. [24]周清、Xiaohan Wei、Zhuoran Yang、Jeeping Ye、Zhaoran Wang。 0.59
Upper confidence primal-dual optimization: Stochastically constrained markov decision processes with adversarial losses and unknown transitions. up confidence primal-dual optimization: 逆の損失と未知の遷移を伴う確率的に制約されたマルコフ決定プロセス。 0.64
arXiv preprint arXiv:2003.00660, 2020. arXiv preprint arXiv:2003.00660, 2020 0.81
[25] Theodore S Rappaport, Robert W Heath Jr, Robert C Daniels, and James N Murdock. Theodore S Rappaport, Robert W Heath Jr, Robert C Daniels, James N Murdock.
訳抜け防止モード: [25 ]Theodore S Rappaport, Robert W Heath Jr. ロバート・C・ダニエルズ、ジェームズ・N・マードック。
0.78
Millime- ter wave wireless communications. ミリメ- ter波無線通信。 0.62
Pearson Education, 2015. Pearson Education, 2015年。 0.93
[26] Herbert Robbins. ハーバート・ロビンス(Herbert Robbins)。 0.57
Some aspects of the sequential design of experiments. 実験の逐次設計のいくつかの側面。 0.77
Bulletin of the Ameri- Ameri (複数形 Ameris) 0.50
can Mathematical Society, 58(5):527–535, 1952. can Mathematical Society, 58(5):527–535, 1952。 0.91
[27] Long Tran-Thanh, Archie Chapman, Alex Rogers, and Nicholas R Jennings. ロング・トラン・タン、アーチー・チャップマン、アレックス・ロジャース、ニコラス・R・ジェニングス。 0.54
Knapsack based optimal policies for budget–limited multi–armed bandits. クナプサックは予算制限付き多武装バンディットの最適政策に基づいていた。 0.43
In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012. 第26回 aaai conference on artificial intelligence, 2012 参加報告 0.68
[28] Martin J Wainwright. 28] マーティン・j・ウェインライト 0.65
High-dimensional statistics: A non-asymptotic viewpoint, volume 48. 高次元統計:非漸近的視点、巻48。 0.72
Cambridge University Press, 2019. ケンブリッジ大学出版局、2019年。 0.60
[29] Yingce Xia, Wenkui Ding, Xu-Dong Zhang, Nenghai Yu, and Tao Qin. [29]yingce Xia、Wenkui Ding、Xu-Dong Zhang、Nenghai Yu、Tao Qin。 0.68
Budgeted bandit In Asian conference on machine learning, pages Budgeted Bandit In Asia Conference on Machine Learning, Page 0.76
problems with continuous random costs. 連続的なランダムコストの問題です 0.69
317–332, 2016. 317–332, 2016. 0.84
[30] Yingce Xia, Haifang Li, Tao Qin, Nenghai Yu, and Tie-Yan Liu. [30]yingce Xia、Haifang Li、Tao Qin、Nenghai Yu、Tie-Yan Liu。 0.72
Thompson sampling for budgeted multi-armed bandits. thompson sampling for budgeted multi-armed bandits (英語) 0.59
In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015. 2015年、第20回人工知能国際会議に参加。 0.73
[31] Hao Yu and Michael J Neely. [31]Hao YuとMichael J Neely。 0.78
A low complexity algorithm with o(√T ) regret and o(1) con- o(t) 後悔と o(1) con- を伴う低複雑性アルゴリズム 0.84
straint violations for online convex optimization with long term constraints. 長期的制約を伴う オンライン凸最適化の 歪曲違反 0.80
Journal of Machine Learning Research, 21(1):1–24, 2020. Journal of Machine Learning Research, 21(1):1–24, 2020 0.92
11 11 0.85
英語(論文から抽出)日本語訳スコア
A Applications • Contractual Hiring Our problem formulation also finds interesting applications in fair contractual hiring [15, 17] and server allocation [16]. 応用 • 契約雇用 我々の問題定式化はまた、公正な契約雇用 [15, 17] とサーバアロケーション [16] において興味深い応用を見つけます。 0.59
Consider a task allocation problem, where tasks are sequentially allocated to a worker/server who belongs to one of K groups. タスクをkグループの1つに属するワーカー/サーバに順次割り当てるタスク割り当て問題を考える。
訳抜け防止モード: タスク割り当ての問題を考える。 タスクは、Kグループの1つに属するワーカー/サーバに順次割り当てられる。
0.77
If nth task is allocated to a worker from group k, it takes Xn,k time to complete the task, and yields a reward Rn,k upon completion. n番目のタスクが群 k からワーカーに割り当てられると、そのタスクを完了するのに Xn,k 時間がかかり、完了時に報酬 Rn,k が与えられる。 0.79
For reward maximization objective, the tasks are allocated to the worker group that maximizes the expected total reward, and the other groups do not receive any tasks (see [11]). 報酬の最大化の目的については、期待される全報酬を最大化するワーカーグループにタスクが割り当てられ、他のグループはタスクを受け取らない([11]参照)。 0.77
However, in many systems, the "fair" allocation of tasks are desired. しかし、多くのシステムでは「公平な」タスクの割り当てが望まれている。 0.75
One way to impose fairness is to impose constraints on the total time budget B allocated to user groups. 公平性を課す一つの方法は、ユーザグループに割り当てられた全時間予算Bに制約を加えることである。
訳抜け防止モード: 公平を課す一つの方法は ユーザグループに割り当てられた全時間予算Bに制約を課す。
0.76
Let A ⊂ K be a class of user groups. a, k をユーザグループのクラスとする。 0.68
By letting Yn,k = ω · I{k /∈ A} for all k and some ω ≥ 0, the solution to the optimization problem (4) yields a fair allocation rule where the fraction of the budget allocated to the worker groups in A should be at least proportional to c. すべての k とある ω ≥ 0 に対して Yn,k = ω · I{k /∂ A} を課すことにより、最適化問題の解 (4) は A 内の労働者群に割り当てられた予算の割当が少なくとも c に比例する公平な割当規則を与える。 0.84
• Online Advertising The same idea can be applied to online advertising. • オンライン広告 同じアイデアがオンライン広告にも適用できます。 0.86
Consider an advertiser with a budget B and K advertising spots (impressions) to select from. 予算bとkの広告スポット(インプレッション)が選択される広告主を考えてみよう。 0.77
In order to win an impression, the advertiser has to bid in an auction [13, 4], which means the budget consumption Xn,k is random. インプレッションを獲得するために、広告主はオークション[13,4]に入札しなければならないので、予算消費Xn,kはランダムである。 0.66
Winning an impression will generate a random return Rn,k which measures the value of that impression. インプレッションを獲得すると、そのインプレッションの値を測定するランダムリターンRn,kが生成される。 0.74
The goal of an advertiser is to maximize the expected total return under the budget constraint. 広告主の目標は、予算制約の下で期待される総リターンを最大化することである。 0.62
In addition, the advertiser may want to set a constraint on the number of bids for certain type of impressions to balance between different demographic groups and locations, which can be represented by Yn,k defined above. さらに、広告主は、特定の種類の印象の入札数に制限を設定して、異なる人口集団と、上記のYn,kで表される場所のバランスを保とうとすることもある。 0.58
B Preliminary Results B.1 Results from Renewal Theory b 予備的結果 b.1 更新理論の結果 0.75
In this section, we will prove results on the counting process N π(B) based on renewal theory, which will be used throughout the proofs in the following sections. この節では、更新理論に基づく数え上げ過程 N π(B) に関する結果を証明します。
訳抜け防止モード: この節では、再更新理論に基づく数え上げ過程 n π(b ) の結果を証明する。 これは以下のセクションで証明全体にわたって使用される。
0.66
The proofs are based on [9]. その証明は[9]に基づいている. 0.86
Proposition 3 (High-probability upper bound for N π(B)). 命題3(n π(b) に対する高確率上界)。 0.63
Consider an i.i.d. process Xn,k ∈ [0, 1] a.s. for each k ∈ K, and define n0(B) = ⌈2B/µmin⌉ for µmin = mink∈K E[Xn,k]. i. i. d. プロセス Xn,k ∈ [0, 1] a.s. の各 k ∈ K に対して、μmin = mink∂K E[Xn,k] に対して n0(B) = s2B/μmin を定義する。 0.57
Then, under any policy π ∈ Π, we have the following inequality for all B > 1: すると、任意のポリシー π ∈ s の下で、すべての B > 1 に対して以下の不等式が成立する。 0.64
P(N π(B) ≥ n) = P(cid:16) nXt=1 P(N π(B) ≥ n) = P(cid:16) nXt=1 0.95
X π t ≤ B(cid:17) ≤ e−n/2, X π t ≤ B(cid:17) ≤ e−n/2, 0.79
(20) for any n ≥ n0(B). (20) 任意の n ≥ n0(B) に対して。 0.76
Proof. The equality in (20) is due to the renewal relation {N π(B) ≥ n} = nPn 証明。 20) における等式は、更新関係 {n π(b) ≥ n} = npn によるものである。 0.70
In order to prove the inequality, first note that E[X π X π n − E[X π the following relation: 不等式を証明するために、まず、E[X π X π n − E[X π] が次の関係である。 0.75
n−1] ≥ µmin for any n ≥ 1, and Dn = n−1] is a martingale difference sequence with |Dn| ≤ 1 almost surely. n−1] ≥ μmin 任意の n ≥ 1 に対して、dn = n−1] は |dn| ≤ 1 のマルティンゲール差分列である。 0.82
Then, we have t ≤ Bo. そして私たちは t ≤ Bo。 0.74
n|F π n|F π n|F π n|F π 0.71
t=1 X π {Sπ t=1 X π 対訳 sπ 0.68
n ≤ B} =n nXt=1 n ≤ B} =n nXt=1 0.82
Dt ≤ B − nXt=1 Dt ≤ B − nXt=1 0.72
E[X π Dt ≤ B − nµmin}. E[X π] Dt ≤ B − nμmin}。 0.90
For any n ≥ n0(B), we have B − nµmin ≤ −nµmin/2. 任意の n ≥ n0(b) に対して、b − nμmin ≤ −nμmin/2 となる。 0.63
Therefore, we have: t−1]o ⊂ { nXt=1 t |F π 2 (cid:17), それゆえ、私たちは t−1]o = nXt=1 t |F π 2 (cid:17) 0.79
Dt ≤ − nµmin Dt ≤ − nμmin 0.72
P(Sπ n ≤ B) ≤ P(cid:16) nXt=1 P(Sπ) n ≤ B) ≤ P(cid:16) nXt=1 0.82
≤ e−n/2, where the second inequality follows from concentration bounds for martingale sequences [28] with |Dn| ≤ 1 and deviation ǫ = µmin/2 . ≤ e−n/2。 2次不等式は |dn| ≤ 1 のマルティンゲール列 [28] と偏差 s = μmin/2 の濃度境界から従う。 0.64
In the following, we characterize the performance of a stationary randomized policy π = π(p) by proving tight bounds on the expected cumulative reward and penalty under π(p). 以下に、期待される累積報酬と π(p) の下でのペナルティの厳密な境界を示すことにより、定常ランダム化ポリシー π = π(p) の性能を特徴づける。 0.76
12 12 0.85
英語(論文から抽出)日本語訳スコア
Proposition 4 (Performance of a Stationary Randomized Policy). 命題4(定常ランダム化政策の実行)。 0.57
For any p ∈ ∆K , let π(p) be a Pk∈K pk E[Y1,k] stationary randomized policy, and let r(p) = Pk∈K pk E[X1,k] . 任意の p ∈ pK に対して、π(p) を Pk⋅K pk E[Y1,k] 定常ランダム化ポリシーとし、r(p) = Pk∂K pk E[X1,k] とする。 0.79
Then, we have the following inequalities: 次に、以下の不等式がある。 0.65
Pk∈K pk E[R1,k] Pk∈K pk E[X1,k] and y(p) = Pk・K pk E[R1,k]Pk・K pk E[X1,k]およびy(p) = 0.70
r(p)B ≤ E[REWπ(p)(B)] ≤ r(p)(cid:16)B + min(cid:17). r(p)B ≤ E[REWπ(p)(B)] ≤ r(p)(cid:16)B + min(cid:17)。 0.93
y(p)B ≤ E" N π(p)(B)Xn=1 # ≤ y(p)(cid:16)B + min(cid:17). y(p)B ≤ E" N π(p)(B)Xn=1 # ≤ y(p)(cid:16)B + min(cid:17)。 0.99
Y π(p) n 1 µ2 Y π(p) n 1 µ2 0.87
1 µ2 (21) (22) 1 µ2 (21) (22) 0.86
(23) (24) (25) (23) (24) (25) 0.85
Proof. The proof is based on Proposition 2 in [11]. 証明。 その証明は[11]の命題2に基づいている. 0.71
Under π(p), it can be shown that arm k is π(p) の下では、arm k が成り立つ。 0.62
the reward per unit cost from arm k under π(p) is rk(p) = pk E[R1,k] π(p) の下で arm k から単位コスト当たりの報酬は rk(p) = pk e[r1,k] である。 0.87
pulled exactly once in a regenerative cycle with total expected cost(cid:0)Pj pj E[X1,j](cid:1)/pk. 総コスト(cid:0)Pj pj E[X1,j](cid:1)/pk。 0.51
Therefore, per unit cost from all arms is r(p) = Pk rk(p). したがって、すべてのアームからの単位コストは r(p) = pk rk(p) である。 0.81
Similarly, the penalty per unit cost from arm y(p) =Pk yk(p). 同様に、単位コスト当たりのペナルティはarm y(p) = pk yk(p) である。 0.73
Hence, the upper and lower bounds follow from Proposition 6.1 and Proposition したがって、上下の境界は命題6.1と命題から従う。 0.59
Pj pj E[X1,j ] , which implies the penalty per unit cost from all arms is Pj pj E[X1,j ] は、すべての腕の単位費用当たりのペナルティを意味する。 0.79
Pj pj E[X1,j ] , which implies the reward 報酬を意味する pj pj e[x1,j ] 0.71
k under π(p) is yk(p) = pk E[Y1,k] π(p) 下の k は yk(p) = pk E[Y1,k] である 0.93
6.2 (Lorden’s inequality) in [2], respectively. 6.2 (lordenの不等式) はそれぞれ [2] である。 0.72
B.2 Decomposition of Regret and Constraint-violation B.2 規則と制約違反の分解 0.61
Lemma 1 (Regret Decomposition). Lemma 1 (Regret Decomposition)。 0.76
For any causal policy π ∈ Π, the regret with respect to the optimal stationary policy π∗ can be decomposed as: 因果政策 π ∈ π に対して、最適定常政策 π∗ に対する後悔は次のように分解することができる。 0.72
E[REWπ∗ (B)] − E[REWπ(B)] ≤(cid:16)r(p∗) − E[REWπ∗] (B)] − E[REWπ(B)] ≤(cid:16)r(p∗) − 0.78
n=1 Rπ n] n=1 X π n=1 Rπ n] n=1 X π 0.72
E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) 0.98
n ](cid:17) · n ](cid:17) · 0.97
2B µmin + rmax(cid:16) 1 2Bμmin + rmax(cid:16) 1 0.79
µ2 min + e−B/µmin 1 − µ2 ミン + e−B/μmin 1 − 0.66
√e−1(cid:17) e−1(cid:17) 0.56
where p∗ = (p∗1, . p∗ = (p∗1, )。 0.59
. . , p∗K) is the distribution of budget under π∗ and n0(B) = ⌈2B/µmin⌉ is a high probability upper bounds for N π(B). . . , p∗K) は π∗ の下での予算分布であり、n0(B) は N π(B) の高確率上界である。 0.82
Proof. Take an arbitrary causal policy π ∈ Π. 証明。 任意の因果ポリシー π ∈ π を取る。 0.64
Since π is causal, the following holds for some n = (pπ π π は因果であるから、以下は n = (pπ π) に対して成り立つ。 0.76
1,n, pπ p 2,n, . 1,n,pπ p 2,n である。 0.87
. . , pπ n|F π E[Rπ . . , pπ n|F π E[Rπ] 0.80
K,n) ∈ F π n−1] = r(p K,n) ∈ F π n−1] = r(p) 0.96
n−1: π n)E[X π n−1: π n)E[X π 0.98
n|F π We have the following inequality for the expected cumulative reward under π: n|F π π の下で期待される累積報酬には以下の不等式がある。 0.67
E[REWπ(B)] = Eh ∞Xn=1 = Eh ∞Xn=1 = Eh ∞Xn=1 e[rewπ(b)] = eh ∞xn=1 = eh ∞xn=1 0.93
E[Xn,k|F π E[Xn,k|F π 0.92
n−1]. π pπ k,n n−1]。 π pπk,n 0.87
n−1] = r(p n−1] = r(p) 0.81
n)Xk∈K ni, I{Sπ n−1 ≤ B}Rπ n−1 ≤ B}i, n−1(cid:3)I{Sπ E(cid:2)Rπ n|F π n−1(cid:3)I{Sπ n)E(cid:2)X π n|F π n−1) and Sπ n)XkåK ni, I{Sπ n−1 ≤ B}Rπ n−1 ≤ B}i, n−1(cid:3)I{Sπ E(cid:2)Rπ n|F π n−1(cid:3)I{Sπ n)E(cid:2)X π n|F π n−1)およびSπ 0.76
r(p π n−1 ≤ B}i, r(p) π n−1 ≤ B}i, 0.88
where (24) follows since π is causal (i.e., I π relation (23). ここで (24) は π が因果関係であるため従う(すなわち I π 関係 (23) )。 0.82
For the optimal stationary randomized policy π∗, by Proposition 4, we have the following inequalities: 最適定常ランダム化ポリシー π∗ に対し、命題 4 により次の不等式が得られる。 0.69
n−1 ∈ Fn−1, and (25) follows from the n−1 ∈ fn−1 と (25) は f から従う 0.74
n ∈ F π E[REWπ∗ n ∈ F π E[REWπ∗] 0.78
1 µ2 (B)] ≤ r(p∗)(cid:16)B + min(cid:17), ≤ r(p∗)(cid:16)Eh N π(B)Xn=1 min(cid:17), ni + = Eh ∞Xn=1 n−1 ≤ B}i + n−1(cid:3)I{Sπ r(p∗)E(cid:2)X π n|F π 1 µ2 (B)] ≤ r(p∗)(cid:16)B + min(cid:17), ≤ r(p∗)(cid:16)Eh N π(B)Xn=1 min(cid:17), ni + = Eh ∞Xn=1 n−1 ≤ B}i + n−1(cid:3)I{Sπ r(p∗)E(cid:2)X π n|F π 0.90
1 µ2 X π r(p∗) µ2 1 µ2 X π r(p∗) μ2 0.91
min , (26) (27) ミン , (26) (27) 0.76
13 13 0.85
英語(論文から抽出)日本語訳スコア
where (26) uses the fact that B ≤PN π(B) ここで (26) は b ≤pn π(b) という事実を用いる。 0.77
Combining (25) and (27), we have 25)と(27)を組み合わせることで、私たちは 0.75
n=1 X π n . n = 1 X π n。 0.81
E[REWπ∗ (B)] − E[REWπ(B)] ≤ Eh ∞Xn=1(cid:0)r(p∗) − r(p ≤ Eh NXn=1(cid:0)r(p∗) − r(p + rmax(cid:16) 1 + Xn>N E[REWπ∗] (B)] − E[REWπ(B)] ≤ Eh ∞Xn=1(cid:0)r(p∗) − r(p ≤ Eh NXn=1(cid:0)r(p∗) − r(p + rmax(cid:16)1 + Xn>N 0.85
µ2 min π π n−1(cid:3)I{Sπ n)(cid:1)E(cid:2)X π n|F π n)(cid:1)E(cid:2)X π n−1(cid:3)I{Sπ n|F π n−1 ≤ B)(cid:17). µ2 ミン π π n−1(cid:3)I{Sπ n)(cid:1)E(cid:2)X π n|F π n)(cid:)E(cid:2)X π n−1(cid:)I{Sπ n|F π n−1 ≤ B(cid:17)。 0.75
P(Sπ n−1 ≤ B}i + n−1 ≤ B}i P(Sπ) n−1 ≤ B}i + n−1 ≤ B}i 0.83
r(p∗) µ2 min r(p∗) μ2 ミン 0.74
(28) where (28) uses the fact that X π Let n0(B) = ⌈2B/µmin⌉. (28) ここで (28) は、x π が n0(b) を 2b/μmin とするという事実を用いる。 0.73
By Proposition 3, P(Sπ 命題3によるP(Sπ) 0.71
n ∈ [0, 1] and r(p∗) ≤ rmax. n ∈ [0, 1] および r(p∗) ≤ rmax である。 0.93
implies: n−1 ≤ B) ≤ e−n/2 for all n > n0(B), which 意味するところ: n−1 ≤ B) ≤ e−n/2 for all n > n0(B) 0.71
Xn>n0(B) P(Sπ Xn>n0(B) P(Sπ) 0.87
n−1 ≤ B) ≤ e−B/µmin /(1 − n−1 ≤ B) ≤ e−B/μmin /(1 − 0.72
√e−1). Thus, setting N = n0(B), we have the following inequality: -1)。 したがって、N = n0(B) とすると、以下の不等式が成立する。 0.52
E[REWπ∗ (B)] − E[REWπ(B)] ≤ r(p∗)Eh n0(B)Xn=1 =(cid:16)r(p∗) − + rmax(cid:16) 1 ≤(cid:16)r(p∗) − E[REWπ∗] (B)] − E[REWπ(B)] ≤ r(p∗)Eh n0(B)Xn=1 =(cid:16)r(p∗) − + rmax(cid:16) 1 ≤(cid:16)r(p∗) − 0.84
µ2 min X π ni − Eh n0(B)Xn=1 µ2 ミン X π ni − Eh n0(B)Xn=1 0.75
Rπ + E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) Rπ + E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) 0.87
n=1 Rπ n] n=1 X π e−B/µmin 1 − n=1 Rπ n] n=1 X π n=1 Rπ n] n=1 X π e−B/μmin 1 − n=1 Rπ n] n=1 X π 0.64
n ](cid:17) · Eh n0(B)Xn=1 √e−1(cid:17) n ](cid:17) · n ](cid:17) · eh n0(b)xn=1 (cid:17) n ](cid:17) · 0.88
2B µmin + e−B/µmin 1 − 2Bμmin + e−B/μmin 1 − 0.68
√e−1(cid:17) e−1(cid:17) 0.56
µ2 ni + rmax(cid:16) 1 ni µ2 ni + rmax(cid:16) 1 ni 0.87
X π min + rmax(cid:16) 1 X π ミン + rmax(cid:16) 1 0.75
µ2 min + e−B/µmin 1 − µ2 ミン + e−B/μmin 1 − 0.66
√e−1(cid:17) e−1(cid:17) 0.56
Lemma 2 (Constraint-violatio n Decomposition). Lemma 2 (Constraint-violatio n Decomposition)。 0.79
For any causal policy π ∈ Π, the constraintviolation can be decomposed as: 任意の因果ポリシー π ∈ > に対して、制約違反は次のように分解できる。 0.50
Dπ(B) ≤ EhPn0(B) EhPn0(B) Dπ(B) ≤ EhPn0(B) EhPn0(B) 0.97
n=1 (Y π n=1 (X π n=1(yπ) n=1(Xπ) 0.71
n )i n )i − c! n ) i n )i − c! 0.84
· 2 µmin + · 2 μmin + 0.83
1 B (ymax − c) 1B (ymax − c) 0.82
e−B/µmin √e−1 1 − e-B/μmin >e−1 1 − 0.40
+ 1 B Proof. For any causal policy π, the following holds for some p + 1B 証明。 因果政策 π に対して、以下の p は成立する。 0.74
π n = (pπ π n = (pπ) 0.88
1,n, pπ 2,n, . 1,n,pπ 2,n である。 0.88
. . , pπ K,n) ∈ F π . . ,pπ K,n) ∈ F π 0.85
n−1: E[Y π n |F π n−1 E[Y]π n |F π 0.86
n−1] = y(p n−1] = y(p) 0.81
π n)E[X π n|F π π n)E[X π n|F π 0.78
n−1] = y(p n−1] = y(p) 0.81
π n)Xk∈K π n)xkhtmlk 0.75
pπ k,n E[Xn,k|F π pπk,n E[Xn,k|F π 0.90
n−1]. (29) n−1]。 (29) 0.86
14 14 0.85
英語(論文から抽出)日本語訳スコア
err 翻訳エラー 0.00
英語(論文から抽出)日本語訳スコア
Combining (25) and (34), we have: 25)と(34)を組み合わせると、次のようになる。 0.52
where (33) follows sincePN π(B)−1 E[REWπ(B)]−E[REWπ∗ ここで (33) は PN π(B)−1 E[REWπ(B)]−E[REWπ∗ 0.95
n=1 X π n=1 X π n=1 X π n=1 X π 0.74
n ≤ B ≤PN π(B) n−1(cid:3)I{Sπ n)−r(p∗)(cid:1)E(cid:2)X π n|F π n ≤ B ≤PN π(B) n−1(cid:3)I{Sπ n)−r(p∗)(cid:1)E(cid:2)X π n|F π 0.86
Since r(p) ≤ rmax for all p ∈ ∆K , we have the following inequality for all n > 1: すべての p ∈ > K に対して r(p) ≤ rmax であるため、すべての n > 1 に対して以下の不等式を持つ。 0.72
n and Xn,k ∈ [0, 1] almost surely. n と Xn,k ∈ [0, 1] はほぼ確実に成り立つ。 0.89
n−1 ≤ B}i+r(p∗). n−1 ≤ B}i+r(p∗)。 0.83
(35) π (B)] ≤ Eh ∞Xn=1(cid:0)r(p (B)] ≤ Eh NXn=1(cid:0)r(p (35) π (B)] ≤ Eh ∞Xn=1(cid:0)r(p(B)) ≤ Eh NXn=1(cid:0)r(p) 0.86
E[REWπ(B)] − E[REWπ∗ E[REWπ(B)] − E[REWπ∗] 0.98
π n) − r(p∗)(cid:1)E(cid:2)X π n−1(cid:3)I{Sπ n|F π π n) − r(p∗)(cid:1)E(cid:2)X π n−1(cid:3)I{Sπ n|F π 0.85
+rmax(cid:16)1 + Xn>N +rmax(cid:16)1 + Xn>N 0.90
P(Sπ n−1 ≤ B}i n−1 ≤ B)(cid:17). P(Sπ) n−1 ≤ B}i n−1 ≤ B (cid:17)。 0.80
(36) Let n0(B) = ⌈2B/µmin⌉. (36) n0(b) を 2b/μmin とする。 0.69
Then, by Proposition 3, P(Sπ そして、命題3により、P(Sπ) 0.69
n−1 ≤ B) ≤ e−n/2 for all n > n0(B), n−1 ≤ B) ≤ e−n/2 for all n > n0(B) 0.85
which implies: Thus, setting N = n0(B) in (36), we have the following inequality: つまり したがって、(36) に N = n0(B) を設定すると、次の不等式が成立する。 0.47
Xn>n0(B) P(Sπ Xn>n0(B) P(Sπ) 0.87
n−1 ≤ B) ≤ n−1 ≤ B) ≤ 0.88
e−B/µmin √e−1 1 − e-B/μmin >e−1 1 − 0.40
. E[REWπ(B)] − E[REWπ∗ . E[REWπ(B)] − E[REWπ∗] 0.92
(37) e−B/µmin 1 − (37) e−B/μmin 1 − 0.69
√e−1(cid:17), se−1(cid:17) 0.63
Rπ X π n=1 Rπ n] n=1 X π Rπ X π n=1 Rπ n] n=1 X π 0.79
(B)] ≤ Eh n0(B)Xn=1 ≤(cid:16) E[Pn0(B) E[Pn0(B) + rmax(cid:16)1 + ≤(cid:16) E[Pn0(B) E[Pn0(B) (B)] ≤ Eh n0(B)Xn=1 ≤(cid:16) E[Pn0(B) E[Pn0(B) + rmax(cid:16)1 + ≤(cid:16) E[Pn0(B) E[Pn0(B) 0.98
ni − r(p∗)Eh n0(B)Xn=1 n ] − r(p∗)(cid:17) · Eh n0(B)Xn=1 √e−1(cid:17), n ] − r(p∗)(cid:17) · ni − r(p∗)eh n0(b)xn=1 n ] − r(p∗)(cid:17) · eh n0(b)xn=1 (cid:17), n ] − r(p∗)(cid:17) · 0.97
e−B/µmin 1 − n=1 Rπ n] n=1 X π e−B/μmin 1 − n=1 Rπ n] n=1 X π 0.62
2B µmin ni + rmax(cid:16)1 + 2Bμmin ni + rmax(cid:16)1 + 0.82
X π ni + rmax(cid:16)1 + X π ニ + rmax(cid:16)1 + 0.77
e−B/µmin 1 − e−B/μmin 1 − 0.52
√e−1(cid:17). se−1 (cid:17)。 0.55
(38) For a causal policy π that satisfies the constraint, we have (38) 制約を満たす因果ポリシー π に対して、我々は 0.76
0 ≥ B · Dπ(B) = Eh N π(B)Xn=1 ≥ Eh N π(B)Xn=1 0 ≥ B · Dπ(B) = Eh N π(B)Xn=1 ≥ Eh N π(B)Xn=1 0.98
Y π ni − Bc n )i n − cX π Yπ ni − Bc n )i n − cX π 0.75
(Y π Then, using the fact that |Y π (Yπ) すると |y π という事実を使って 0.76
n − cX π as follows: n − cX π 以下の通りです 0.76
n| ≤ 1 and equation (37), we can bound the constraint violation n| ≤ 1 と方程式 (37) は制約違反を拘束することができる 0.82
Reorganizing the terms and using the fact that E[X π 用語の再編成とE[X π]の事実の利用 0.75
n ] ≥ µmin,∀n, we have, n ] ≥ μmin,...n, we have, 0.85
(Y π n − cX π (Yπ) n − cX π 0.84
n )i ≤ e−B/µmin √e−1 1 − n)i ≤ e-B/μmin >e−1 1 − 0.62
. We will optimize the finite-time performance (i.e., maximize the RHS of (38)) over all π ∈ Π subject to (39) to show that π∗ has a bounded optimality gap. . 有限時間性能(すなわち (38) の RHS を (39) に従属するすべての π ∈ > に対して最適化し、π∗ が有界な最適性ギャップを持つことを示す。 0.82
n=1 Y π n ] n ] ≤ c + n=1 X π n=1 y π n ] n ] ≤ c + n=1 x π 0.90
1 2B · e−B/µmin √e−1 1 − 1 2B · e-B/μmin >e−1 1 − 0.67
. (39) Eh n0(B)Xn=1 E[Pn0(B) E[Pn0(B) . (39) Eh n0(B)Xn=1 E[Pn0(B) E[Pn0(B) 0.88
16 16 0.85
英語(論文から抽出)日本語訳スコア
Consider the following optimization problem: 次の最適化問題を考える。 0.75
max π ∈ Π s.t. max π ∈ s.t. 0.95
n=1 Rπ n] n=1 X π n ] n=1 Y π n ] n ] ≤ c + n=1 X π n=1 Rπ n] n=1 X π n ] n=1 Y π n ] n ] ≤ c + n=1 X π 0.85
E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) 0.99
1 2B · e−B/µmin √e−1 1 − 1 2B · e-B/μmin >e−1 1 − 0.67
. It is shown in Lemma 1 in [22] that there is an optimal stationary randomized policy π(p) for the optimization problem above. . Lemma 1 in [22] では、上記の最適化問題に対して最適な定常ランダム化ポリシー π(p) が存在することが示されている。 0.80
Thus, by letting p∗per(B) ∈ arg max このようにして p∗per(B) ∈ arg max 0.81
p∈∆K nr(p) : y(p) ≤ c + p)K nr(p) : y(p) ≤ c + 0.89
1 2B · e−B/µmin √e−1 1 − 1 2B · e-B/μmin >e−1 1 − 0.67
.o, r(cid:0)p∗per(B)(cid:1) is the optimum value of the optimization problem above. .o. r(cid:0)p∗per(B)(cid:1) は上記の最適化問題の最適値である。 0.69
From (38), the optimality gap grows linearly in B at a rate r(cid:0)p∗per(B)(cid:1) − r(p∗). 38 から、最適性ギャップは B において r(cid:0)p∗per(B)(cid:1) − r(p∗) で直線的に増加する。 0.80
Using sensitivity analysis for Linear Fractional √e−1 , we have r(cid:0)p∗per(B)(cid:1)− r(p∗) ≤ 線形フラクショナル ~e−1 に対する感度解析を用いて r(cid:0)p∗per(B)(cid:1)− r(p∗) ≤ となる。 0.74
Programming [6, 7] with constraint perturbation ǫ = 1 O(c′ǫ) for some constant c′. 制約摂動を伴うプログラミング [6, 7] は、ある定数 c′ に対して 1 o(c′) である。 0.77
Substituting this result into (38), we have: この結果を (38) に置き換えると、 0.60
2B · e−B/µmin 2B · e−B/μmin 0.47
1− E[REWπ(B)] − E[REWπ∗ 1− E[REWπ(B)] − E[REWπ∗] 0.88
(B)] ≤ O(cid:16) (B) ≤ O(cid:16) 0.91
c′e−B/µmin c′e−b/μmin 0.26
√e−1)(cid:17) + rmax(cid:16)1 + e−1)(cid:17) + rmax(cid:16)1 + 0.74
e−B/µmin 1 − e−B/μmin 1 − 0.52
√e−1(cid:17), se−1(cid:17) 0.63
(40) µmin(1 − (40) μmin(1 −) 0.84
which implies REGπ∗ これはREGπ∗を意味する 0.33
(B) ≤ rmax + e−Ω(B) = O(1). (B) ≤ rmax + e−Ω(B) = O(1)。 0.86
(Bounding the constraint-violation ) By the upper bound in Proposition 4, under any stationary randomized policy π(p), we have: 任意の定常ランダム化ポリシー π(p) の下では、命題 4 の上限によって次のようになる。 0.65
By definition, we have y(p∗) ≤ c. Substituting this into the above inequality, we obtain: 定義によれば、 y(p∗) ≤ c である。
訳抜け防止モード: 定義により、y(p∗ ) ≤ c である。 これを上記の不平等に置き換える。 私たちは
0.76
1 B Y π(p) n 1B Y π(p) n 0.82
E" N π(p)(B)Xn=1 E" N π∗ (B)Xn=1 E" N π(p)(B)(Xn=1 E" N π∗ (B)Xn=1 0.90
1 B # ≤ y(p)(cid:16)1 + 1B # ≤ y(p)(cid:16)1 + 0.89
1 Bµ2 min(cid:17), 1Bμ2 min (cid:17) 0.79
n # ≤ c + Y π∗ n # ≤ c + Y π∗ 0.87
c Bµ2 min , c Bμ2 ミン , 0.68
which implies Dπ∗ (B) ≤ c Dπ∗ (b) ≤ c 0.67
Bµ2 min = O( 1 Bμ2 ミン =O(1) 0.64
B ). D Performance Bounds for Offline Lyapunov Policy B)。 オフラインリアプノフ政策におけるDパフォーマンス境界 0.76
Proposition 5 (Drift-Minimizing Policy is Deterministic). 提案5(Drift-Minimizing Policy is Deterministic)。 0.79
For any n ≥ 1, under Fn−1, let 任意の n ≥ 1 に対して Fn−1 の下では、 0.67
Ψn(k, Qn) = −V sn(k, Qn) = −V 0.88
E[Rn,k] E[Xn,k] E[Rn,k] E[Xn,k] 0.85
+ Qn E[Yn,k] E[Xn,k] +Qn E[Yn,k] E[Xn,k] 0.81
kn = arg min k∈K kn = arg min kıK 0.68
Ψn(k, Qn) Then, q I πLyOff n ψn(k, qn) そして、q I πLyOff n 0.86
πLyOff n = I{k = kn} is a solution to (11), i.e., q πLyOff n = i{k = kn} は (11) の解、すなわち q である。 0.83
= kn for all n ≥ 1 and QπLyOff =すべての n ≥ 1 と qπlyoff に対する kn 0.70
n is updated according to (8) under πLyOff. n πLyOff で (8) に従って更新される。 0.79
πLyOff n ∈ arg minq∈∆K Ψn(Qπ(q) πLyOff n ∈ arg minq~Kn(Qπ(q)) 0.87
n (41) (42) n (41) (42) 0.85
). Thus, Proof. ). したがって 証明。 0.72
For qn ∈ Fn−1, since E[Xn,k] > 0,∀n, k, qn ∈ Fn−1 のとき、E[Xn,k] > 0,\n,k, 0.85
17 17 0.85
英語(論文から抽出)日本語訳スコア
Ψn(Qπ(qn) ψn(qπ(qn)) 0.77
n k=1 qn,kE[Xn,k] n k=1 qn,kE[Xn,k] 0.92
k=1 qn,kE[Xn,k] −V E[Rn,k]+Qn·E[Yn,k] k=1 qn,kE[Xn,k] −VE[Rn,k]+Qn·E[Yn,k] 0.96
k=1 qn,k(cid:16) − V E[Rn,k] + Qn · E[Yn,k](cid:17) k=1 qn,k(cid:16) − V E[Rn,k] + Qn · E[Yn,k](cid:17) 1.00
) = PK = PK mink∈Kn−V E[Rn,k]+Qn·E[Yn,k] o ·PK k∈Kn (−V E[Rn,k] + Qn · E[Yn,k]) o ) = PK = PK mink・Kn-V E[Rn,k]+Qn·E[Yn,k] o ·PK k・Kn (−V E[Rn,k] + Qn ·E[Yn,k]) o 0.92
PK PK k=1 qn,kE[Xn,k] PK PK k=1 qn,kE[Xn,k] 0.92
k=1 qn,kE[Xn,k] k=1 qn,kE[Xn,k] 0.98
PK ≥ min E[Xn,k] PK ≥ミン E[Xn,k] 0.79
E[Xn,k] E[Xn,k] E[Xn,k] E[Xn,k] 0.85
≥ k=1 qn,kE[Xn,k] ≥ k=1 qn,kE[Xn,k] 0.92
Therefore, qπLyOff したがって、qπLyOff 0.62
n,k = I{k = kn} is a solution to (11). n,k = I{k = kn} は (11) の解である。 0.78
Lemma 3 (First-order drift bounds for Qn). Lemma 3 (Qn の第一次ドリフト境界)。 0.70
Under Assumption 1, let there be an ǫ-Slater arm for with ǫ > 0. 仮定1の下では、s > 0 である s-Slater の腕が成立する。 0.66
Let Then, under πLyOff, we have the following bound: いくぞ そして πLyOff の下で、以下の有界となる。 0.61
l∗ = V rmax l∗ = V rmax 0.87
ǫ E"(cid:16)QπLyOff ǫ E"(cid:16)QπLyOff 0.84
n+1 − QπLyOff n+1 − QπLyOff 0.59
n (cid:17)I{QπLyOff n (cid:17)I{QπLyOff 0.80
n n−1 # ≤ −ǫ. n n−1 # ≤ − 。 0.83
≥ l∗}(cid:12)(cid:12)(cid :12)F πLyOff ≥ l∗}(cid:12)(cid:12)(cid :12)F πLyOff 0.84
(43) Proof. We will skip the superscript πLyOff for Qn in the proof. (43) 証明。 証明において、Qn のスーパースクリプト πLyOff をスキップする。 0.71
For LyOff policy, the first order statistics for all random variables are assumed to be known. LyOffポリシーでは、すべての確率変数の第一次統計が知られていると仮定される。 0.68
Assume arm k satisfies ǫ-Slater condition with ǫ > 0, i.e. アーム k は > 0, i で >-スレーター条件を満たすと仮定する。 0.65
E[Yn,k − cXn,k] ≤ −ǫ. e[yn,k − cxn,k] ≤ − である。 0.80
Under Fn−1, Qn is given. Fn−1 では Qn が与えられる。 0.73
We will show that if arm k′ has E[Yn,k′ − cXn,k′ ] ≥ 0, then Ψn(k′, Qn)− Ψn(k, Qn) ≥ 0 for Qn ≥ l∗. アーム k′ が E[Yn,k′ − cXn,k′ ] ≥ 0 であるなら、Qn ≥ l∗ に対して、n(k′, Qn)− sn(k, Qn) ≥ 0 であることを示す。 0.89
Ψn(k′, Qn) − Ψn(k, Qn) = −V(cid:16) E[Rn,k′ ] sn(k′, Qn) − sn(k, Qn) = −V(cid:16) E[Rn,k′ ] 0.92
E[Xn,k′ ] − E[Xn,k′ ] − 0.96
E[Rn,k] E[Xn,k](cid:17) + Qn(cid:16) E[Yn,k′ ] E[Rn,k] E[Xn,k](cid:17) + Qn(cid:16) E[Yn,k′ ] 0.92
E[Xn,k′ ] − E[Xn,k′ ] − 0.96
E[Yn,k] E[Xn,k](cid:17) E[Yn,k] E[Xn,k](cid:17) 0.89
E[Rn,k] E[Xn,k′ ] − E[Rn,k] E[Xn,k′ ] − 0.90
E[Xn,k](cid:17) ≤ V rmax E[Xn,k](cid:17) ≤ V rmax 0.92
V(cid:16) E[Rn,k′ ] E[Xn,k](cid:17) ≥ Qn(cid:16)c − c + V(cid:16) E[Rn,k′ ] E[Xn,k](cid:17) ≥ Qn(cid:16)c − c + 0.97
E[Yn,k] ǫ E[Xn,k](cid:17) ≥ Qnǫ E[Yn,k] ǫ E[Xn,k](cid:17) ≥ Qn 0.87
Qn(cid:16) E[Yn,k′ ] Therefore, when Qn ≥ V rmax したがって、Qn ≥ V rmax の場合、Qn(cid:16) E[Yn,k′ ] 0.81
E[Xn,k′ ] − E[Xn,k′ ] − 0.96
ǫ , Ψn(k′, Qn) − Ψn(k, Qn) ≥ ǫ , ψn(k′, qn) − ψn(k, qn) ≥ 0.86
V rmax ǫ · ǫ − V rmax ≥ 0 V rmax ǫ · − V rmax ≥ 0 0.81
(44) From Proposition 5, the drift-minimizing policy is deterministic in the offline setting. (44) 命題5から、ドリフト最小化ポリシーはオフライン環境で決定論的である。 0.72
So kn = arg mink∈K Ψn(k, Qn) will satisfy the ǫ−Slater condition. したがって、kn = arg mink(K )n(k, Qn) は s−Slater 条件を満たす。 0.69
Then E(cid:2)(cid:0)Qn+1 − Qn(cid:1)I{Qn ≥ l∗}(cid:12)(cid:12)Fn−1(cid:3) = E[Yn,kn − cXn,kn ] ≤ −ǫ そして E(cid:2)(cid:0)Qn+1 − Qn(cid:1)I{Qn ≥ l∗}(cid:12)(cid:12)Fn−1(cid:3) = E[Yn,kn − cXn,kn ] ≤ − . 0.78
(45) 18 (45) 18 0.85
英語(論文から抽出)日本語訳スコア
err 翻訳エラー 0.00
英語(論文から抽出)日本語訳スコア
where (a) is using Proposition 5 and (b) is using the definition of π∗ (Definition 4). ここで (a) は命題 5 を使い、 (b) は π∗ (定義 4) の定義を用いている。 0.76
Taking expectation on both sides, since X π x π から両側への期待を 0.63
E[L(Qπ n+1)] − E[L(Qπ E[L(Qπ) n+1)] − E[L(Qπ) 0.89
n)] ≤ σ2 2 + δ + V E[Rπ n) ≤ σ2 2 +δ+VE[Rπ] 0.80
n] − V E[X π n] − V E[X π 0.85
n ]r(p∗) + δE[Qπ n] n ]r(p∗) + δE[Qπ n] 0.98
n ≤ 1, δ2 + 2 n ≤ 1, δ2 + 2 0.96
Taking telescoping sum from N to 0, N から 0 へのテレスコープの和を取る 0.68
E[L(Qπ N )] − E[L(Qπ E[L(Qπ) N )] − E[L(Qπ) 0.90
0 )] ≤ N σ2 0 )] ≤ Nσ2 0.70
2 + N δ2 2 + N δ + V 2 + Nδ2 2 + N δ + V 0.85
− V NXn=1 E[X π -V NXn=1 E[X π] 0.75
n ]r(p∗) + δ n ]r(p∗) + δ 0.85
NXn=1 NXn=1 NXn=1 NXn=1 0.50
E[Rπ n] E[Qπ n] E[Rπ n] E[Qπ n] 0.99
Rearrange the terms, since E[L(Qπ e[l(qπ]から項を並べ替える 0.61
E[Rπ n] n ] ≥ r(p∗) − E[X π E[Rπ n] n ] ≥ r(p∗) − E[X π 0.90
N )] − E[L(Qπ N σ2 + N δ2 N )] − E[L(Qπ N σ2 + N δ2 0.96
0 )] ≥ 0 E[X π 0 )] ≥ 0 E[X π] 0.83
n ] − 2V PN n ] − 2V PN 0.87
n=1 N δ V PN n=1 Nδ V PN 0.75
n=1 Let N = n0(B) = ⌈2B/µmin⌉, n=1 N = n0(B) = >2B/μmin とする。 0.61
n=1 n=1 PN PN E[Pn0(B) E[Pn0(B) n=1 n=1 PN PN E[Pn0(B) E[Pn0(B)) 0.71
n=1 Rπ n] n ] ≥ r(p∗) − n=1 X π ≥ r(p∗) − n=1 Rπ n] n ] ≥ r(p∗) − n=1 X π ≥ r(p∗) − 0.96
n0(B)(σ2 + δ2) 2V n0(B)µmin − σ2 + δ2 + 2δ n0(B)(σ2 + δ2) 2V n0(B)μmin − σ2 + δ2 + 2δ 0.83
2V µmin δPn0(B) 2Vμmin δPn0(B) 0.75
E[Qπ n] V n0(B)µmin E[Qπ n] V n0(B)μmin 0.94
n=1 − n0(B)δ n=1 − n0(B)δ 0.81
V n0(B)µmin − V n0(B)μmin − 0.94
E[Qπ n] V n0(B)µmin E[Qπ n] V n0(B)μmin 0.94
E[X π n ] − E[X π] n ] − 0.90
E[Qπ n] E[X π n ] E[Qπ n] E[X π n ] 0.92
n=1 n=1 δPN V PN δPn0(B) n=1 n=1 δPN V PN δPn0(B) 0.68
n=1 Using the decomposition for regret (Lemma 1), n=1 後悔の分解(補題1)を用いて 0.62
E[REWπ∗ (B)] − E[REWπ(B)] ≤(cid:16)r(p∗) − E[REWπ∗] (B)] − E[REWπ(B)] ≤(cid:16)r(p∗) − 0.78
n ](cid:17) · δPn0(B) Using the definition Qn+1 = max(cid:8)0, Qn + Yn − (c − δ)Xn(cid:9), n ](cid:17) · δPn0(B) 定義 Qn+1 = max(cid:8)0, Qn + Yn − (c − δ)Xn(cid:9), 0.97
E[Pn0(B) E[Pn0(B) E[Pn0(B) E[Pn0(B) 0.98
n=1 Rπ n] n=1 X π n=1 Rπ n] n=1 X π 0.72
B(σ2 + δ2 + 2δ) B(σ2 + δ2 + 2δ) 0.88
2V µ2 ≤ + min 2V μ2 ≤ + ミン 0.72
n=1 V µmin 2B µmin n=1 Vμmin 2Bμmin 0.66
Qn+1 ≥ Qn + Yn − (c − δ)Xn Qn+1 ≥ Qn + Yn − (c − δ)Xn 0.98
+ µ2 + rmax(cid:16) 1 + rmax(cid:16) 1 + µ2 + rmax(cid:16) 1 + rmax(cid:16) 1 0.84
µ2 min min e−B/µmin 1 − + µ2 ミン ミン e−B/μmin 1 − + 0.59
√e−1(cid:17) √e−1(cid:17)(46) 〜e−1(cid:17)〜e−1(cid:17)(46) 0.56
e−B/µmin 1 − e−B/μmin 1 − 0.52
E[Qπ n] Taking telescoping sum from N to 0, E[Qπ n] N から 0 へのテレスコープの和を取る 0.83
Taking expectation on both sides, under πLyOff πLyOff 下での双方の期待 0.67
NXn=1 Yn − (c − δ) NXn=1 Yn − (c − δ) 0.72
NXn=1 Xn ≤ QN NXn=1 Xn ≤ QN 0.72
n ] − (c − δ) n ] − (c − δ) 0.85
NXn=1 E[X π NXn=1 E[X π] 0.77
n ] ≤ E[Qπ N ] n ] ≤ E[Qπ N ] 0.94
Let n = n0(B), n = n0(B) とする。 0.78
E[Y π NXn=1 ni EhPn0(B) ni − c ≤ EhPn0(B) E[Y]π NXn=1 ni EhPn0(B) ni − c ≤ EhPn0(B) 0.91
n=1 Y π n=1 X π n=1 Y π n=1 X π 0.78
n0(B)] E[X π n0(B)]E[X π 0.83
i ] − δ ≤ E[Qπ i ] − δ ≤ E[Qπ] 0.79
Pn0(B) n=1 Pn0(B) n=1 0.78
20 n0(B)] E[Qπ n0(B)µmin − δ 20 n0(B)] E[Qπ n0(B)μmin − δ 0.87
英語(論文から抽出)日本語訳スコア
Using the decomposition for constraint-violation (Lemma 2), 制約違反の分解を利用する(Lemma 2) 0.77
Dπ(B) ≤ ≤ E[Qn0(B)] n0(B)µmin · E[Qn0(B)] Bµmin − dπ(b) ≤ ≤ E[Qn0(B)] n0(B)μmin · E[Qn0(B)] Bμmin − 0.93
2 µmin − 2δ µmin 2μmin − 2δμmin 0.75
+ 2δ µmin 1 B + 2δμmin 1 B 0.83
+ 1 B (ymax − c) + 1B (ymax − c) 0.83
(ymax − c) (ymax − c) 0.85
e−B/µmin √e−1 1 − e−B/µmin √e−1 1 − e−B/μmin >e−1 1 − e−B/μmin >e−1 1 − 0.41
1 B + + 1 B (47) 1B + + 1B (47) 0.82
Let l∗ = V rmax with some η > 0 . η > 0 で l∗ = V rmax とする。 0.78
Therefore, ǫ , from Theorem 2.3 in [14] and Lemma 3, for any n and z > l∗, P[Qπ そのため ǫ , from Theorem 2.3 in [14] and Lemma 3 for any n and z > l∗, P[Qπ] 0.85
n > z] ≤ ae−ηz n > z] ≤ ae−ηz 0.82
E[Qπ n] = E[Qπ n E[Qπ] n] = E[Qπ n] 0.83
I(Qπ P(Qπ I(Qπ) P(Qπ) 0.77
n > z)dz + l∗P(X > l∗) n > z)dz + l∗P(X > l∗) 0.98
n < l∗)] +Z ∞ n < l∗)] +Z ∞ 0.85
l∗ ae−ηzdz + l∗ae−ηl∗ l∗ ae−ηzdz + l∗ae−ηl∗ 0.57
≤ l∗ +Z ∞ ≤ l∗ + Z ∞ 0.82
z0 V rmax + z0 V rmax + 0.83
= ǫ V rmax = ǫ V rmax 0.85
ηǫ ae−ηl∗ + ηǫ ae−ηl∗ + 0.68
V rmax ǫ ae−ηl∗ V rmax ǫ ae−ηl∗ 0.70
E[REWπ∗ = O(cid:16) V rmax ǫ (cid:17) (B)] − E[REWπ(B)] = O σ2B Dπ(B) = O(cid:16) 1 E[REWπ∗] = O(cid:16) V rmax (cid:17) (B)] − E[REWπ(B)] = O σ2B Dπ(B) = O(cid:16) 1 0.85
V rmax Bµminǫ − V rmax Bμmin 0.82
V µ2 + B min V μ2 + B ミン 0.77
δ µmin(cid:17). δ μmin (cid:17)。 0.79
δrmaxB ǫµ2 δrmaxbはμ2である。 0.33
min !. + (48) ミン! + (48) 0.68
(49) (50) Therefore, combining (46), (47) and (48), (49) (50) したがって、(46)、(47)、(48)を組み合わせる。 0.81
The results in Proposition 2 follows by the asymptotic optimality of π∗ (Proposition 1). 命題 2 の結果は π∗ (proposition 1) の漸近的最適性によって従う。 0.69
E Performance Bounds for Online Lyapunov Policy オンラインリアプノフ政策のEパフォーマンス境界 0.73
E.1 Preliminary Results Lemma 5 (Bounds for Ψn under πLyOn). E.1 予備結果 Lemma 5 (πLyOn で πn のバウンド)。 0.76
Let be the high-probability event under policy πLyOn. いくぞ πLyOn ポリシーの下での高確率イベントである。 0.53
Then, given Qn, すると、Qn が与えられる。 0.53
Aπ n = n\t=1 \k∈Kn(cid:12)(cid:12)br π n−1 ·(cid:16)Ψn(I πLyOn Aπ n = n\t=1 \k・Kn(cid:12)(cid:12)br π n−1 ·(cid:16)n(I πLyOn 0.74
πLyOn n I A πLyOn n 私 A 0.81
t,k − rk(cid:12)(cid:12) ≤ radk(n, α) , Qn) − Ψn(kn, Qn)(cid:17) ≤ 2radI n−1(cid:1)c(cid:16)Ψn(I πLyOn t,k − rk(cid:12)(cid:12) ≤ radk(n, α) , qn) − ψn(kn, qn)(cid:17) ≤ 2radi n−1(cid:1)c(cid:16)ψn(i πlyon) 0.82
πLyOn n I(cid:0)A πLyOn n I(cid:0)A 0.84
Proof. For simplicity, let 証明。 単純さのために 0.68
1 + rk E[X1,k]o\n(cid:12)(cid:12)b yπ 1 + rk E[X1,k]o\n(cid:12)(cid:12)b yπ 0.81
t,k − yk(cid:12)(cid:12) ≤ radk(n, α) (n, α) ·(cid:16) V (1 + rmax) t,k − yk(cid:12)(cid:12) ≤ radk(n, α) (n, α) ·(cid:16) V (1 + rmax) 1.00
µmin + 1 + yk μmin + 1 + yk 0.83
E[X1,k]o, (51) (cid:17), E[X1,k]o, (51) (cid:17) 0.94
µmin Qn(1 + ymax) μmin Qn(1 + ymax) 0.82
(52) πLyOn n (52) πLyOn n 0.87
, Qn) − Ψn(kn, Qn)(cid:17) ≤ V rmax + n(1 + ymax). , Qn) − sn(kn, Qn)(cid:17) ≤ V rmax + n(1 + ymax) である。 0.96
(53) where kn = arg mink Ψn(k, Qn). (53) ここで kn = arg mink (k, Qn) である。 0.85
Moreover, we have the following bound: さらに、以下の境界がある。 0.58
Assume that AπLyOn AπLyOn を仮定する 0.62
n−1 holds, and I πLyOn n−1 が成立し、I πLyOn 0.64
n = k such that n = k のように 0.93
νn(V, Qn) =(cid:16) V (1 + rmax) νn(V, Qn) =(cid:16) V (1 + rmax) 1.00
µmin + Qn(1 + ymax) μmin + Qn(1 + ymax) 0.83
µmin (cid:17). μmin (cid:17)。 0.79
Ψn(k, Qn) > Ψn(kn, Qn) + 2radk(n, α) · νn(V, Qn). tn(k, Qn) > tn(kn, Qn) + 2radk(n, α) · νn(V, Qn) である。 0.92
21 21 0.85
英語(論文から抽出)日本語訳スコア
Then, given Qn, we have the following: すると、Qn が与えられたら、次のようになる。 0.50
bΨn(kn, Qn) − radkn (n, α) · νn(V, Qn) ≤ Ψn(kn, Qn), b)n(kn, Qn) − radkn(n, α) · νn(V, Qn) ≤ n(kn, Qn) 0.87
sincebrn,k andbyn,k,m (thusbΨn(k, Qn),∀k ∈ K) are concentrated around the true values in the event n−1 . ゆえに、brn,k andbyn,k,m (thusbψn(k, qn),\k ∈ k) はイベント n−1 の真の値の周りに集中する。 0.79
(54) is a contradiction since we assumed I πLyOn AπLyOn favorable choice, which concludes the proof of the first part. (54) は、I πLyOn AπLyOn が好ましい選択であると仮定し、最初の部分の証明を結論付けるため矛盾である。 0.75
For the second part, note that Qn ≤ n for all n since Yn,k ≤ 1 almost surely for all n, k, m. Therefore, pessimistic upper and lower bounds on Ψn(k, Qn) yield the result. 第2部では、すべての n に対して qn ≤ n であることに注意する。 yn,k ≤ 1 はすべての n, k, m に対してほぼ確実に成り立つから、従って ψn(k, qn) 上の悲観的上界と下界は結果をもたらす。
訳抜け防止モード: 第二の部分は、Yn からすべての n に対して Qn ≤ n である。 すべての n, k, m に対して k ≤ 1 がほぼ確実に成り立つ。 pn(k, Qn) 上の悲観的上界と下界は、結果 . を得る。
0.80
n = k but kn = arg mink Ψn(k, Qn) is a more n = k だが kn = arg mink >n(k, Qn) はそれ以上である 0.92
≤ Ψn(k, Qn) − 2radk(n, α) · νn(V, Qn), ≤ sn(k, Qn) − 2radk(n, α) · νn(V, Qn) 0.87
≤ bΨn(k, Qn) − radk(n, α) · νn(V, Qn), ≤ bψn(k, qn) − radk(n, α) · νn(v, qn) である。 0.86
(54) Lemma 6 (First-order drift bounds for Qn). (54) Lemma 6 (Qnの第一次ドリフト境界)。 0.76
Under Assumption 1, let there be an ǫ-Slater arm for some ǫ > 0. 仮定 1 では、ある s > 0 に対して s-slater arm が存在する。 0.64
Let l∗ = 2V rmax いくぞ l∗ = 2V rmax 0.74
ǫ + V (1 + rmax) ǫ + V (1 + rmax) 0.85
1 + ymax . 1 + ymax . 0.85
Then, under LyOn, we have the following bound for some ǫ0 > 0: すると、リヨンの下では、ある 0 > 0 に対して以下の境界が与えられる。 0.53
E"(cid:16)QπLyOn E"(cid:16)QπLyOn 0.82
n (cid:17)I n+1 − QπLyOn n (cid:17)I n+1 − QπLyOn 0.71
A πLyOn n−1 A πLyOn n−1 0.72
I{QπLyOn n ≥ l∗}(cid:12)(cid:12)(cid :12)F πLyOn I{QπLyOn n ≥ l∗}(cid:12)(cid:12)(cid :12)F πLyOn 0.82
n−1# ≤ −ǫ0. n−1# ≤ −n0。 0.63
is given, we will skip the superscript for Qn in the proof. 与えられたら、証明において Qn のスーパースクリプトをスキップする。 0.63
(55) Proof. Since under F πLyOn From Lemma 5, if AπLyOn (55) 証明。 AπLyOn の場合、Lemma 5 から F πLyOn 未満となる。 0.71
n−1 , QπLyOn n−1 holds, n−1, QπLyOn n−1 は成り立つ。 0.52
n n (cid:16)Ψn(I πLyOn n n (cid:16)ψn(i πlyon) 0.78
, Qn) − Ψn(kn, Qn)(cid:17) ≤ 2radI Then using the definition of Ψn, if Qn ≥ V rmax Qn Qn ≥ V rmax Qn であるなら、 , Qn) − sn(kn, Qn)(cid:17) ≤ 2radI 次に、n の定義を用いる。 0.89
πLyOn n πLyOn n πLyOn n πLyOn n 0.88
ǫ ] ] ≤ V E[Rn,I E[Xn,I ǫ ] ] ≤ v E[Rn,I E[Xn,I] 0.86
] ] − V E[Yn,I E[Xn,I ] ] − V E[Yn,I E[Xn,I] 0.88
πLyOn n πLyOn n πLyOn n πLyOn n 0.88
, we have E[Rn,kn ] E[Xn,kn ] 僕らは E[Rn,kn ] E[Xn,kn ] 0.75
+ Qn E[Yn,kn ] E[Xn,kn ] +Qn E[Yn,kn ] E[Xn,kn ] 0.81
πLyOn n (n, α) ·(cid:16) V (1 + rmax) πLyOn n (n, α)·(cid:16) v (1 + rmax) 0.91
µmin + Qn(1 + ymax) μmin + Qn(1 + ymax) 0.83
µmin (cid:17) μmin (cid:17) 0.78
(a) πLyOn n (a) πLyOn n 0.87
µmin + 2radI μmin +2radI 0.73
≤ V rmax + Qnc − Qnǫ + 2radI ≤ V rmax + Qnc − Qn\ + 2radI 0.97
(n, α) ·(cid:16) V (1 + rmax) ≤ V rmax + Qnc − Qnǫ +(cid:16) V (1 + rmax) (n, α) ≤ ǫ 2 . (n, α) ·(cid:16) V (1 + rmax) ≤ V rmax + Qnc − Qn* +(cid:16) V (1 + rmax) (n, α) ≤ ≤ 2 である。 0.95
1 + ymax πLyOn n 1 + ymax πLyOn n 0.87
+ µmin Qn(1 + ymax) + μmin Qn(1 + ymax) 0.83
(cid:17) (n, α) ·(cid:16) V (1 + rmax) + Qn(cid:17) ǫ (cid:17) (n, α) ·(cid:16) V (1 + rmax) + Qn(cid:17) 0.98
µmin 2 + Qn(1 + ymax) μmin 2 + Qn(1 + ymax) 0.83
µmin (cid:17) μmin (cid:17) 0.78
where (a) is using Lemma 3 that kn satisfies ǫ-Slater condition when Qn ≥ V rmax fact that initial exploration makes 2radI To satisfy E[Yn,I a) 初期探索が 2radI を E[Yn,I を満足させるという事実を Qn ≥ V rmax のとき、kn が Slater 条件を満たす Lemma 3 を用いる場合 0.82
], let the right-hand-side be less than Qnc, we have ]右サイドをQncより小さくしましょう。 0.51
πLyOn n ǫ πLyOn n πLyOn n ǫ πLyOn n 0.87
πLyOn n ] ≤ cE[Xn,I πLyOn n ] ≤ cE[Xn,I] 0.91
; (b) is using the Qn ≥ ; (b) は、 Qn ≥ 0.70
2V rmax ǫ + 2V rmax ǫ + 0.86
V (1 + rmax) V (1 + rmax) 0.85
1 + ymax = l∗ 1 + ymax =l∗ 0.81
Therefore, if AπLyOn したがって、AπLyOn の場合 0.61
n n−1 holds, I πLyOn Eh(cid:16)QπLyOn n n−1 hold, I πLyOn Eh(cid:16)QπLyOn 0.77
will satisfy the ǫ-Slater condition when Qn ≥ l∗, n−1i ≤ −ǫ0. qn ≥ l∗, n−1i ≤ −>0 のとき、slater 条件を満たす。 0.67
n (cid:17)I n+1 − QπLyOn n (cid:17)I n+1 − QπLyOn 0.71
n ≥ l∗}(cid:12)(cid:12)(cid :12)F πLyOn n ≥ l∗}(cid:12)(cid:12)(cid :12)F πLyOn 0.86
I{QπLyOn πLyOn n−1 I{QπLyOn πLyOn n−1 0.69
A (56) (57) A (56) (57) 0.85
Lemma 7 (Maximal inequality for QπLyOn ). Lemma 7 (QπLyOnの最大不等式)。 0.72
Under Assumption 1, if the problem satisfies the Slater condition with ǫ > 0 and l∗ defined in Lemma 6, we have the following bound under πLyOn for any N > l∗: 仮定 1 の下において、問題が Slater 条件を満たすとき、Lemma 6 で定義される > 0 および l∗ を満たすなら、任意の N > l∗ に対して πLyOn の下に次の有界を持つ。 0.63
n (58) Eh max n (58) Eh max 0.85
1≤n≤N QπLyOn 1≤n≤N QπLyOn 0.49
n (cid:12)(cid:12)F0i = O(cid:0) log(N ) + l∗ + 1(cid:1). n (cid:12)(cid:12)F0i = O(cid:0) log(N ) + l∗ + 1(cid:1)。 0.83
22 22 0.85
英語(論文から抽出)日本語訳スコア
err 翻訳エラー 0.00
英語(論文から抽出)日本語訳スコア
Since |Qn+1 − Qn| ≤ 1, Qn+1 − Qn| ≤ 1 である。 0.74
D−1Zn ≤ Zn+1 ≤ DZn D−1Zn ≤ Zn+1 ≤ DZn 0.64
(66) n+1|F0] − (E[Zn+1|F0])2, Since V ar(Zn+1|F0) = E[Z 2 E[Z 2 n+1|F0] (66) V ar(Zn+1|F0) = E[Z 2 E[Z 2 n+1|F0]] 0.79
(E[Zn+1|F0])2 = 1 + ≤ 1 + (E[Zn+1|F0])2 = 1 + ≤ 1 + 0.92
(a) = 1 + 1 (a) = 1 + 1 0.85
V ar(Zn+1|F0) (E[Zn+1|F0])2 4 (D − D−1)E[Z 2 D−2(E[Zn|F0])2 n|F0] V ar(Zn+1|F0) (E[Zn+1|F0])2 4(D − D−1)E[Z2 D−2(E[Zn|F0])2 n|F0] 0.76
4 (D3 − D)E[Z 2 (E[Zn|F0])2 4 (D3 − D)E[Z2 (E[Zn|F0])2 0.99
1 n|F0] where (a) is using the bounded condition of Zn+1 in (66) and upper bound of variance for bounded random variable (Popoviciu’s inequality). 1 n|F0] ここで (a) は Zn+1 in (66) の有界な条件と、有界な確率変数(ポポヴィシウの不等式)の有界な分散の上限を用いる。 0.73
From (61), let B = 1 61)から、B = 1とする。 0.80
4 (D3 − D) < 1. 4 (D3 − D) < 1。 0.91
Then E[Z 2 n+1|F0] そして E[Z2] n+1|F0] 0.68
(E[Zn+1|F0])2 ≤ 1 + B (E[Zn+1|F0])2 ≤ 1 + B 0.88
E[Z 2 n|F0] (E[Zn|F0])2 E[Z 2 n|F0] (E[Zn|F0])2 0.87
Taking telescoping sum on n, n のテレスコップ総和を取る 0.60
Therefore, E[Z 2 そのため E[Z2] 0.81
n|F0] (E[Zn|F0])2 ≤ ≤ n|F0] (E[Zn|F0])2 ≤ ≤ 0.78
+ Bn 1 − Bn−1 1 − B 1 +Bn 1 − bn−1 1 − b 1 0.87
+ 1 1 − B (a) + 1 1-B (a) 0.76
qE[e2ηQn+1|F0] =qE[Z 2 ≤ DpE[Z 2 ≤ Dr(cid:16) 1 = Dr(cid:16) 1 qE[e2ηQn+1|F0] =qE[Z2 ≤ DpE[Z2 ≤ Dr(cid:16) 1 = Dr(cid:16) 1 0.78
(b) 1 − B 1 − B (b) 1-B 1-B 0.67
n+1|F0] n|F0] n+1|F0]n|F0] 0.45
+ 1(cid:17)E[Zn|F0] + 1(cid:17)E[eηQn|F0] + 1(cid:17)E[Zn|F0] + 1(cid:17)E[eηQn|F0] 0.72
(67) (68) (69) (67) (68) (69) 0.85
where (a) is using the bounded condition of Zn+1 in (66) and (b) is using the inequality in (68) . a) は (66) におけるZn+1 の有界条件を使用し、b) は (68) における不等式を用いる。 0.82
Let D′ = Dr(cid:16) 1 D′ = Dr(cid:16) 1 とする。 0.62
1−B + 1(cid:17), from (65) and (69), E[eηQn+1|F0] ≤(cid:16)ρ + 1−B + 1(cid:17), from (65) and (69), E[eηQn+1|F0] ≤(cid:16)ρ + 0.86
D′ n − 1(cid:17)E[eηQn|F0] + eη(l∗+1) D' n − 1(cid:17)E[eηQn|F0] + eη(l∗+1) 0.68
Taking telescoping sum over n, テレスコープの合計を n, 0.65
E[eηQn|F0] ≤ αneηQ0 + βneη(l∗+1) E[eηQn|F0] ≤ αneηQ0 + βneη(l∗+1) 0.56
(70) 24 (70) 24 0.85
英語(論文から抽出)日本語訳スコア
D′ (n − 3)(cid:17) + . D' (n − 3)(cid:17) + 。 0.78
. . where α1 = α2 = ρ + D′, β1 = β2 = 1. . . where α1 = α2 = ρ + D′, β1 = β2 = 1. 0.88
For n > 2, n > 2 の場合。 0.82
αn = α1α2(cid:16)ρ + αn = α1α2(cid:16)ρ + 0.71
D′ (n − 2)(cid:17)(cid:16)ρ + D' (n − 2)(cid:17)(cid:16)ρ + 0.77
D′ (n − 3)(cid:17) . D' (n − 3)(cid:17)。 0.77
. . (cid:16)ρ + D′(cid:17) . . (cid:16)ρ + D′(cid:17) 0.83
D′ D′ D′ D′ D' D' D' D' 0.63
D′ D′ D′ = α1α2 D' D' D' = α1α2 0.62
m(cid:17) βn = 1 +(cid:16)ρ + +(cid:16)ρ + +(cid:16)ρ + n−2Xj=1 m(cid:17) βn = 1 + (cid:16)ρ + (cid:16)ρ + + (cid:16)ρ + n−2Xj=1 0.82
= 1 + (n − 2)(cid:17)(cid:16)ρ + (n − 3)(cid:17) . = 1 + (n − 2)(cid:17)(cid:16)ρ + (n − 3)(cid:17)。 0.87
. . (cid:16)ρ + D′(cid:17) (n − 3)(cid:17) . . . (cid:16)ρ + D′(cid:17) (n − 3)(cid:17)。 0.84
. . (cid:16)ρ + D′(cid:17)2 . . (cid:16)ρ + D′(cid:17)2 0.84
n−2Ym=1(cid:16)ρ + (n − 2)(cid:17) +(cid:16)ρ + (n − 2)(cid:17)(cid:16)ρ + (n − 2)(cid:17)(cid:16)ρ + jYm=1(cid:16)ρ + n < 1}. n−2Ym=1(cid:16)ρ + (n − 2)(cid:17) + (cid:16)ρ + (n − 2)(cid:17)(cid:16)ρ + (n − 2)(cid:17)(cid:16)ρ + jYm=1(cid:16)ρ + n < 1} である。 0.82
Then let γ = (cid:16)ρ + D′ Let n0 = min{n : ρ + D′ constant.) すると γ = (cid:16)ρ + D′ を n0 = min{n : ρ + D′ とする。 0.89
Using the fact ∀n > n0, 1 , and ∀1 ≤ n ≤ n0, 1 αn ≤ (ρ + D′)n0(cid:16)ρ + n0(cid:17)n−n0 D′ +(cid:16)ρ + n0(cid:17)m 1 − γn−n0+1 n0 > n0, 1 , および 1 ≤ n ≤ n0, 1 αn ≤ (ρ + D′)n0(cid:16)ρ + n0(cid:17)n−n0 D′ +(cid:16)ρ + n0(cid:17)m 1 − γn−n0+1 0.77
(n − m)(cid:17) +(cid:16)ρ + (n − m)(cid:17) +(cid:16)ρ + 0.93
n−n0Xm=0(cid:16)ρ + n−n0xm=0(cid:16)ρ + 0.55
n0(cid:17)n−n0 n0(cid:17)n−n0 0.59
n < 1 n0 βn ≤ n < 1 n0 βn ≤ 0.93
= ξγn + ξγn D′ =γn +γn D' 0.74
D′ D′ = 1 − γ D' D' = 1 − γ 0.74
(ρ + D′)n0−1 (ρ + D′)n0−1 0.75
D′ D′ (n − 2)(cid:17)(cid:16)ρ + (n − 3)(cid:17) . D' D' (n − 2)(cid:17)(cid:16)ρ + (n − 3)(cid:17)。 0.72
. . (cid:16)ρ + D′(cid:17)2 n0(cid:17)n0 n0(cid:17), ξ = (cid:16) ρ+D′ . . (cid:16)ρ + D′(cid:17)2 n0(cid:17)n0 n0(cid:17) sh = (cid:16) ρ+D′ 0.81
ρ+ D′ . n ≤ 1. ρ+D′ . n ≤ 1。 0.77
. (0 < γ < 1. ξ is a . (0 < γ < 1 ) は a である。 0.85
(71) (72) (73) (71) (72) (73) 0.85
From (70), (71), and (72), (70)から(71)、(72)まで 0.59
E[eηQn|F0] ≤ ξγneηQ0 +(cid:16) 1 − γn−n0+1 E[eηQn|F0] ≤ γneηQ0 +(cid:16) 1 − γn−n0+1 0.53
1 − γ + ξγn(cid:17)eη(l∗+1) 1 − γ +γn(cid:17)eη(l∗+1) 0.78
Define the fist hitting time τ = inf{n : Qn ≥ z}. fist hit time τ = inf{n : Qn ≥ z} を定義する。 0.82
Define event H N (z) = {max1≤n≤N Qn ≥ z|F0} and a disjoint set of events H N 事象 H N (z) = {max1≤n≤N Qn ≥ z|F0} と事象 H N の解集合を定義する。 0.67
n=1H N n (z). n=1hn n (z)。 0.67
n (z) = I(τ = n). n(z) = i(τ = n) である。 0.86
H N (z) = ∪N eηz P(H N eηz P(H N (z)) = H N (z) = シュN eηz P(H N eηz P(H N (z)) = 0.96
n (z)) NXn=1 NXn=1 NXn=1 n (z) NXn=1 NXn=1 NXn=1 0.57
= (a) ≤ E[eηz IHN = (a) ≤ E[eηz IHN] 0.81
n (z)] E[eηQn I n (z)] E[eηQn I] 0.69
HN n (z)] where (a) is using the fact Qn ≥ z under event H N Assume z > l∗ + 1, HN n (z)] ここで (a) は事象 H N における Qn ≥ z の事実を z > l∗ + 1 とする。 0.80
n (z). NXn=1 n (z)。 NXn=1 0.67
E[eηQn I HN E[eηQn I] HN 0.76
n (z)] = NXn=1 NXn=1 n (z)] = NXn=1 NXn=1 0.62
+ E[E[eηQn I + E[eηQn I] 0.87
HN n (z) I{Qn−1 ≥ l∗}|Fn−1]] HN n (z) I{Qn−1 ≥ l∗}|Fn−1] 0.87
E[E[eηQn IHN E[eηQn IHN 0.79
n (z)I{Qn−1 < l∗}|Fn−1]] n (z)I{Qn−1 < l∗}|Fn−1]] 0.97
25 25 0.85
英語(論文から抽出)日本語訳スコア
Since |Qn − Qn−1| ≤ 1, Qn > z > l∗ + 1 is impossible when Qn−1 < l∗, Qn−1 < l∗ であるとき、|Qn − Qn−1| ≤ 1, Qn > z > l∗ + 1 は不可能である。 0.72
NXn=1 E[E[eηQn IHN NXn=1 E[eηQn IHN 0.69
n (z)I{Qn−1 < l∗}|Fn−1]] = 0 n (z)I{Qn−1 < l∗}|Fn−1]] = 0 0.99
Therefore, eηz P(H N (z)|F0) ≤ そのため eηz P(H N (z)|F0) ≤ 0.82
NXn=1 1 − γN 1 − γ ξ NXn=1 1 − γN 1 − γ ξ 0.77
E[E[eηQn IHN E[eηQn IHN 0.79
n (z)I{Qn−1 ≥ l∗}|Fn−1]|F0] ≤ 1 − γ − γ−n0+1 1 − γN 1 − γ 1 − γ(cid:17)eη(l∗+1) 1 − γ n(z)I{Qn−1 ≥ l∗}|Fn−1]|F0] ≤ 1 − γ − γ−n0+1 1 − γN 1 − γ1 − γ(cid:17)eη(l∗+1) 1 − γ 0.84
eηQ0 +(cid:16) N eηQ0 +(cid:16) N eηQ0 +(cid:16) N eηQ0 +(cid:16) N 0.66
+ ξ + ξ 1 − γ + ξ + ξ 1 − γ 0.85
(a) ≤ ξ (b) (a) ≤ ξ (b) 0.85
≤ NXn=1 E[eηQn|F0] 1 − γ (cid:17)eη(l∗+1) ≤ NXn=1 E[eηQn|F0] 1 − γ (cid:17)eη(l∗+1) 0.76
1 − γN where (a) is using (73) and (b) is dropping the negative terms. 1 − γN a)が (73) を使用し、(b) が負の項を下げている場合。 0.86
Therefore, ξ 1 − γ そのため ξ 1 − γ 0.82
P( max 1≤n≤N P(max 1≤n≤N) 0.56
Qn ≥ z|F0) ≤ Qn ≥ z|F0) ≤ 0.78
=(cid:16) ξ 1 − γ 1−γ (eηQ0 + eη(l∗+1)), b = eη(l∗ +1) 1−γ 1 − γ 1−γ (eηq0 + eη(l∗+1)), b = eη(l∗+1) 1−γ 0.93
Let a = ξ a = s とする。 0.47
Then, let Qmax = max1≤n≤N Qn. すると Qmax = max1≤n≤N Qn とする。 0.63
e−η(z−Q0) +(cid:16) N e−η(z−Q0) +(cid:16)N 0.69
1 − γ (eηQ0 + eη(l∗+1)) + 1 − γ (eηQ0 + eη(l∗+1)) + 0.80
+ ξ 1 − γ(cid:17)e−η(z−l∗−1) + ξ 1 − γ(cid:17)e−η(z−l∗−1) 0.79
eη(l∗+1) 1 − γ eη(l∗+1) 1 − γ 0.86
N(cid:17)e−ηz N(cid:17)e−ηz 0.64
(74) (75) and z0 = max{ log(a+bN ) (74) (75) z0 = max{ log(a+bN ) 0.88
η , l∗}. η , l∗} である。 0.74
E[Qmax|F0] = E[QmaxI(Qmax < z0)|F0] + E[QmaxI(Qmax ≥ z0)|F0] E[Qmax|F0] = E[QmaxI(Qmax < z0)|F0] + E[QmaxI(Qmax ≥ z0)|F0] 0.88
P(Qmax > z)dz + z0P(Qmax > z0) P(Qmax > z)dz + z0P(Qmax > z0) 0.98
(a) = E[QmaxI(Qmax < z0)|F0] +Z N ≤ z0 +Z N (a) = E[QmaxI(Qmax < z0)|F0] +Z N ≤ z0 +Z N 0.87
z0 z0 (b) log(a + bN ) z0 z0 (b) log(a + bN ) 0.82
(a + bN ) = (a + bN) = 0.84
= η + 2 log(a + bN ) + 1 = η + 2 log(a + bN ) + 1 0.85
η (cid:16) η (cid:16) 0.82
1 (a + bN ) − e−ηN(cid:17) + 1 (a + bN ) − e−ηN(cid:17) + 0.84
(a + bN )e−ηN (a + bN)e−ηN 0.82
η + η (a + bN )e−ηzdz + z0(a + bN )e−ηz0 η + η (a + bN )e−ηzdz + z0(a + bN )e−ηz0 0.83
log(a + bN ) log(a + bN ) 0.85
η (a + bN ) (a + bN ) η (a + bN) (a + bN) 0.84
where (a) uses the fact that E[X I(X ≥ z0)] = R N ここで (a) は E[X I(X ≥ z0)] = R N であるという事実を使う 0.87
variable X ∈ [0, N ]; (b) uses the definition of a and b and the inequality (75). 変数 X ∈ [0, N ]; (b) は a と b の定義と不等式 (75) を使用する。 0.78
Therefore, z0 P(X > z)dz + z0P(X > z0) for a random そのため z0 ランダムな P(X > z)dz + z0P(X > z0) 0.82
Eh max 1≤n≤N Eh max 1≤n≤N 0.62
Qn|F0i ≤ 1−γ (eηQ0 + eη(l∗+1)) + eη(l∗ +1) Qn|F0i ≤ 1−γ(eηq0 + eη(l∗+1) + eη(l∗+1) 0.62
2 log(cid:16) ξ +(cid:16) ξ 1−γ (eηQ0 + eη(l∗+1)) + eη(l∗ +1) = O(cid:0) log(N ) + l∗ + 1(cid:1) 2 log(cid:16) シュ +(cid:16) シュ 1−γ (eηQ0 + eη(l∗+1)) + eη(l∗ +1) = O(cid:0) log(N ) + l∗ + 1(cid:1) 0.80
1−γ N(cid:17) + 1 1−γ N(cid:17)e−ηN 1−γn(cid:17)+1−γn(cid:17)e−ηn 0.63
η η 26 η η 26 0.85
英語(論文から抽出)日本語訳スコア
err 翻訳エラー 0.00
英語(論文から抽出)日本語訳スコア
N (σ2 + δ2 + 2δ) E[X π N (σ2 + δ2 + 2δ) E[X π 0.96
n=1 n (n, α)] n radI π E[X π n ] n=1 E[X π n−1)c] n E[X π n ] n=1 n (n, α)] n radI π E[X π n ] n=1 E[X π n−1)c] n E[X π n ] 0.77
I(Aπ E[X π I(Aπ) E[X π] 0.86
n Qπ n] E[X π n ] n Qπ n] E[X π n ] 0.93
n=1 n ] − δPN V PN rmax −PN n=1 n ] − δPN V PN rmax −PN 0.78
1 + rmax µmin − 1 + rmax μmin − 0.99
n=1 2PN V PN n=1 2PN V PN 0.76
n=1 n=1(E[X π n n=1 n=1(E[X π n) 0.72
n=1 E[X π n=1 E[X π] 0.77
V PN n=1 I(Aπ V PN n=1 I(Aπ) 0.74
n−1)c] · n) E[X π n ] n−1)c] · n) E[X π n ] 0.97
σ2 + δ2 + 2δ σ2 + δ2 + 2δ 0.78
E[maxn Qπ n] E[maxn Qπ n] 0.97
2V µmin V µmin 2Vμmin Vμmin 0.74
n radI π n (n, α)Qπ n] n radI π n (n, α)Qπ n] 0.89
E[X π n ] (1 + ymax) E[X π n ] (1+ymax) 0.80
2√2α · N log N E[maxn Qπ 2>2α · N log N E[maxn Qπ 0.71
n] V N µmin 1 + ymax n] VNμmin 1 + ymax 0.82
µmin n=1 n=1 μmin n=1 n=1 0.65
− E[X π E[Rπ n] n ] ≥ r(p∗) − 2V PN E[X π 2PN PN −PN PN ≥ r(p∗) − 2√2α · N log N −PN − E[X π] E[Rπ n] n ] ≥ r(p∗) − 2V PN E[X π 2PN PN −PN PN ≥ r(p∗) − 2\2α ·N log N −PN 0.92
1 n2 n=1 N µmin 1 n2 n=1 N μmin 0.71
rmax − N µmin rmax − N μmin 0.87
− n=1 − δ 1 + rmax µmin − (1 + ymax) − n=1 −δ 1 + rmax μmin − (1 + ymax) 0.78
2V µmin n ] ≥ µmin, X π 2V μmin n ] ≥ μmin, X π 0.90
1 + ymax µmin 1 + ymax μmin 0.82
(76) (77) (78) (76) (77) (78) 0.85
Rearrange the terms, since E[L(Qπ e[l(qπ]から項を並べ替える 0.61
n)] − E[L(Qπ n)] − E[L(Qπ) 0.93
0 )] ≥ 0 PN PN 0 )] ≥ 0 PN PN 0.78
n=1 n=1 where (76)-(78) use the fact that E[X π n=1 n=1 ここで (76)-(78) は e[x π であるという事実を用いる 0.68
n ∈ [1, N ]. n ∈ [1, n ] である。 0.84
In addition, (77) uses the fact thatPN さらに (77) は PN が 0.54
uses the fact that E[I(Aπ Schwarz inequality. e[i(aπ schwarz inequality) を用いる。 0.68
n−1)c] ≤ 1 n−1)c] ≤ 1 0.92
n2 and E[X π n n2 と E[X π n 0.94
I(Aπ n=1 E[X π n−1)c] ≤ 1 I(Aπ) n=1 E[X π n−1)c] ≤ 1 0.79
n ∈ (0, 1], and E[Qπ n ∈ (0, 1] および E[Qπ] 0.86
n] ≤ E[maxn Qπ n] ≤ E[maxn Qπ 0.96
n (n, α)] ≤ √2α · N log N . n (n, α)] ≤ 2α · n log n である。 0.85
(78) n] for all (78) n]何にせよ 0.70
n )2] which is true by Cauchy- は、Cauchyによって真である。 0.27
n radI π npE[(X π n radI π npE[(X π) 0.84
Using the expression for regret (Lemma 1), 後悔の表現を使って (lemma 1) 0.67
E[REWπ∗ ≤(cid:16)r(p∗) − E[REWπ∗] ≤(cid:16)r(p∗) − 0.82
(B)] − E[REWπ(B)] E[Pn0(B) n ](cid:17) · E[Pn0(B) (B)] − E[REWπ(B)] E[Pn0(B) n ](cid:17) · E[Pn0(B) 0.90
n=1 Rπ n] n=1 X π n=1 Rπ n] n=1 X π 0.72
B(σ2 + δ2 + 2δ) B(σ2 + δ2 + 2δ) 0.88
≤ V µ2 min 2B µmin ≤ V μ2 ミン 2Bμmin 0.72
+ rmax(cid:16) 1 + rmax(cid:16) 1 0.92
µ2 min + δ · µ2 ミン + δ · 0.71
2B · E[maxn Qπ n] 2B · E[maxn Qπ n] 0.96
+ V µ2 min 2√2α · B log BE[maxn Qπ + V μ2 ミン 2α · b log be[maxn qπ] 0.74
n] + V µmin n] + Vμmin 0.84
1 + ymax µmin 1 + ymax μmin 0.82
+ + e−B/µmin 1 − + + e−B/μmin 1 − 0.74
√e−1(cid:17) 2√2α · B log B rmax + rmax(cid:16) 1 2α · b log b rmax + rmax(cid:16) 1 0.66
µmin π2 6 µ2 μmin π2 6 µ2 0.82
µmin 1 + rmax μmin 1 + rmax 0.82
µmin + B(1 + ymax) μmin + B(1 + ymax) 0.83
V µ2 min + e−B/µmin 1 − V μ2 ミン + e−B/μmin 1 − 0.69
√e−1(cid:17) e−1(cid:17) 0.56
min From Lemma 7, E[max1≤n≤n0(B) Qπ ミン Lemma 7, E[max1≤n≤n0(B) Qπから 0.60
n] = O(log(n0(B)) + l∗ + 1). n] = O(log(n0(B)) + l∗ + 1) である。 0.92
Therefore, The results in Theorem 1 follows by adding the maximal regret during initial exploration そのため Theorem 1の結果は、最初の探索中に最大の後悔を加えることで従う。 0.69
E[REWπ∗ (B)] − E[REWπ(B)] E[REWπ∗] (B)] − E[REWπ(B)] 0.75
= O rmax√B log B = O rmax\B log B 0.82
+(cid:16) σ2 + ymax + δ log B O(cid:16) y2 min (cid:17) and the asymptotic optimality of π∗ (Proposition 1). +(cid:16) σ2 + ymax + δ log B O(cid:16) y2 min (cid:17) および π∗ (Proposition 1) の漸近最適性。 0.86
Using the definition Qn+1 = max(cid:8)0, Qn + Yn − (c − δ)Xn(cid:9), Qn+1 = max(cid:8)0, Qn + Yn − (c − δ)Xn(cid:9) という定義を用いる。 0.85
Qn+1 ≥ Qn + Yn − (c − δ)Xn Qn+1 ≥ Qn + Yn − (c − δ)Xn 0.98
maxK log B maxK log B 0.85
V µ2 ǫ2µ2 µ2 V μ2 ǫ2µ2 µ2 0.71
min min + δrmax ǫµ2 ミン ミン + δrmax (複数形 δrmaxs) 0.54
min(cid:17)B! min (cid:17)B! 0.90
Taking telescoping sum from N to 0, N から 0 へのテレスコープの和を取る 0.68
Taking expectation on both sides, under πLyOn πLyOn 下での両面の期待 0.63
NXn=1 Yn − (c − δ) NXn=1 Yn − (c − δ) 0.72
NXn=1 Xn ≤ QN NXn=1 Xn ≤ QN 0.72
NXn=1 E[Y π NXn=1 E[Y]π 0.74
n ] − c NXn=1 n ] − c NXn=1 0.72
E[X π n ] ≤ E[Qπ E[X π] n ] ≤ E[Qπ] 0.91
N ] − δ NXn=1 N ] − δ NXn=1 0.72
E[X π n ] 28 E[X π n ] 28 0.85
英語(論文から抽出)日本語訳スコア
Let n = n0(B), n = n0(B) とする。 0.78
EhPn0(B) EhPn0(B) EhPn0(B) EhPn0(B) 0.96
n=1 (Y π n=1 (X π n=1(yπ) n=1(Xπ) 0.71
n )i n )i − c ≤ n )i n )i − c ≤ 0.85
E[Qπ Pn0(B) E[Qπ] Pn0(B) 0.86
i=1 n0(B)] E[X π i=1 n0(B)]E[X π 0.71
i ] − δ ≤ n0(B)] i ] − δ ≤ n0(B)] 0.85
E[Qπ n0(B)µmin − δ E[Qπ n0(B)μmin − δ 0.92
Using the decomposition for regret violation (Lemma 2), 後悔違反に対する分解(lemma 2) 0.50
Dπ(B) ≤ = E[Qπ n0(B)] n0(B)µmin · E[Qπ n0(B)] Bµmin − dπ(b) ≤ = E[Qπ n0(B)] n0(B)μmin · E[Qπ n0(B)] Bμmin − 0.91
n0(B) B − 1 2δ µmin B n0(B) B − 1 2δ μmin B 0.95
+ 2δ µmin + + 2δμmin + 0.79
1 B (ymax − c) 1B (ymax − c) 0.82
(ymax − c) e−B/µmin √e−1 1 − (ymax − c) e−B/μmin >e−1 1 − 0.64
e−B/µmin √e−1 1 − 1 + B e−B/μmin >e−1 1 − 1 + B 0.57
From Lemma 7, E[Qπ Lemma 7, E[Qπ]から 0.84
n0(B)] = O(log(n0(B)) + l∗ + 1). n0(B)] = O(log(n0(B)) + l∗ + 1) である。 0.96
Dπ(B) = O log B Dπ(B) = O log B 0.94
µmin!, minB (cid:17) and the asymptotic optimality of π∗ (Proposition 1). μmin!, minB (cid:17) および π∗ (Proposition 1) の漸近最適性。 0.85
rmax Bµminǫ − rmax (複数形 rmaxs) 0.38
Bµ2 + min δ Bμ2 + ミン δ 0.69
O(cid:16) y2 O(cid:16) y2 0.78
maxK log B ǫ2µ2 maxK log B >2μ2 0.68
+ 1 B (79) The results in Theorem 1 follows by adding the maximal regret during initial exploration + 1B (79) Theorem 1の結果は、最初の探索中に最大の後悔を加えることで従う。 0.78
F Additional Simulation Results F 追加シミュレーション結果 0.78
Figure 2 shows the reward rate and constraint-violation for LyOff and LyOn algorithms with different v0 and δ0 values. 図2は、v0とδ0の値が異なるLyOffとLyOnのアルゴリズムに対する報酬率と制約違反を示している。 0.68
The results confirm the trade-off between regret and constraint-violation when changing the values of V and δ. その結果、v と δ の値を変更する際の後悔と制約違反のトレードオフが確認された。 0.58
Larger V or smaller δ will result in larger constraint-violation but smaller regret (higher reward rate). より大きなvまたはより小さいδは、より大きな制約違反をもたらすが、より少ない後悔(高い報酬率)をもたらす。 0.63
On the other hand, smaller V or larger δ will result in smaller constraint-violation but larger regret (smaller reward rate). 一方、より小さいvまたはより大きなδは、より小さな制約違反をもたらすが、より大きな後悔(より小さな報酬率)をもたらす。 0.71
0.85 0.84 0.83 0.85 0.84 0.83 0.59
0.82 0.81 0.8 0.82 0.81 0.8 0.59
e t a r d r a w e R E t a r d r a w e R 0.82
v0=2, 0=0.5 v0=1.5, 0=0.5 v0=1, 0=0.5 v0=1, 0=0.7 v0=1, 0=0.9 v0=2, 0=0.5v0=1.5, 0=0.5v0=1, 0=0.5v0=1, 0=0.7v0=1, 0=0.9 0.35
0.05 0.04 0.03 0.05 0.04 0.03 0.59
0.02 0.01 v0=2, 0=0.5 v0=1.5, 0=0.5 v0=1, 0=0.5 v0=1, 0=0.7 v0=1, 0=0.9 0.02 0.01 v0=2, 0=0.5v0=1.5, 0=0.5v0=1, 0=0.5v0=1, 0=0.7v0=1, 0=0.9 0.51
n o i t l ん? i t です うーん 0.55
a o V o v (複数形 ovs) 0.38
i t i n a r t s n o C 私は t 私は n a r t s n o C 0.69
0.79 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0.79 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0.72
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0.85
B (a) B (b) B (a) B (b) 0.85
t e a r d r a w e R t e a r d r a w e R 0.85
0.95 0.9 0.85 0.95 0.9 0.85 0.59
0.8 v0=2, 0=1 v0=1.5, 0=1 v0=1, 0=1 v0=1, 0=1.5 v0=1, 0=2 0.8 v0=2, 0=1 v0=1.5, 0=1 v0=1, 0=1 v0=1, 0=1.5 v0=1, 0=2 0.50
0.18 0.16 0.14 0.18 0.16 0.14 0.59
n o i t 0.12 ん? i t です 0.12 0.60
l a o V うーん o v (複数形 ovs) 0.42
i t i n a r t s n o C 私は t 私は n a r t s n o C 0.69
0.1 0.08 0.06 0.1 0.08 0.06 0.59
0.04 0.02 v0=2, 0=1 v0=1.5, 0=1 v0=1, 0=1 v0=1, 0=1.5 v0=1, 0=2 0.04 0.02 v0=2, 0=1 v0=1.5, 0=1 v0=1, 0=1 v0=1, 0=1.5 v0=1, 0=2 0.53
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0.85
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0.85
B (c) B (d) B (c) B (d) 0.85
Figure 2: Constraint-violation and reward rate as B grows for different v0 and δ0 values. 図2: 制約違反と報酬率 b は、異なる v0 と δ0 の値に対して増加する。 0.66
(a) LyOff reward rate. (a) lyoff 報酬率。 0.58
(b) LyOff constraint-violation . (b)lyoff制約違反。 0.66
(c) LyOn reward rate. (c)LyOn報酬率 0.59
(d) LyOn constraint-violation . (d)LyOn制約違反 0.61
29 29 0.85
                                                           ページの最初に戻る

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