論文の概要、ライセンス

# (参考訳) モノトンアームシーケンスを必要とするマルチアームバンド [全文訳有]

Multi-armed Bandit Requiring Monotone Arm Sequences ( http://arxiv.org/abs/2106.03790v2 )

ライセンス: CC BY 4.0
Ningyuan Chen(参考訳) 多くのオンライン学習やマルチアームの盗賊問題では、取られた行動や引き出された腕は規則的であり、時間とともに単調でなければならない。 例えば、企業が早期採用者や戦略的な待機を緩和するためにマークアップ価格ポリシーを使用する動的価格設定や、線量配分は通常、線量制限毒性を防止するために線量エスカレーション原則に従う臨床試験などがある。 腕列が単調である必要がある場合の連続腕包帯問題を考える。 未知の目的関数がリプシッツ連続であるとき、後悔は$O(T)$であることを示す。 さらに、目的関数がユニモーダルあるいは準凹である場合、その後悔は、提案されたアルゴリズムの下で$\tilde o(t^{3/4})$であり、これは最適速度でもある。 これは、連続武装バンディット文学における最適レート$\tilde O(T^{2/3})$から逸脱し、単調性要求によってもたらされる学習効率のコストを示す。

In many online learning or multi-armed bandit problems, the taken actions or pulled arms are ordinal and required to be monotone over time. Examples include dynamic pricing, in which the firms use markup pricing policies to please early adopters and deter strategic waiting, and clinical trials, in which the dose allocation usually follows the dose escalation principle to prevent dose limiting toxicities. We consider the continuum-armed bandit problem when the arm sequence is required to be monotone. We show that when the unknown objective function is Lipschitz continuous, the regret is $O(T)$. When in addition the objective function is unimodal or quasiconcave, the regret is $\tilde O(T^{3/4})$ under the proposed algorithm, which is also shown to be the optimal rate. This deviates from the optimal rate $\tilde O(T^{2/3})$ in the continuous-armed bandit literature and demonstrates the cost to the learning efficiency brought by the monotonicity requirement.
公開日: Tue, 8 Jun 2021 19:52:14 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] G L . 8 ] G L。 0.81
s c [ 2 v 0 9 7 3 0 sc [ 2 v 0 9 7 3 0 0.68
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Multi-armed Bandit Requiring Monotone Arm モノトーンアームを必要とするマルチアームバンド 0.53
Sequences Ningyuan Chen Rotman School of Management, University of Toronto 順序 寧元陳 トロント大学ロトマン経営大学院 0.59
105 St George St, Toronto, ON, Canada カナダ・トロントのセント・ジョージ・セント105番地 0.67
ningyuan.chen@utoron to.ca ningyuan.chen@utoron to.ca 0.59
Abstract In many online learning or multi-armed bandit problems, the taken actions or pulled arms are ordinal and required to be monotone over time. 概要 多くのオンライン学習やマルチアームの盗賊問題では、取られた行動や引き出された腕は規則的であり、時間とともに単調でなければならない。 0.47
Examples include dynamic pricing, in which the firms use markup pricing policies to please early adopters and deter strategic waiting, and clinical trials, in which the dose allocation usually follows the dose escalation principle to prevent dose limiting toxicities. 例えば、企業が早期採用者や戦略的な待機を緩和するためにマークアップ価格ポリシーを使用する動的価格設定や、線量配分は通常、線量制限毒性を防止するために線量エスカレーション原則に従う臨床試験などがある。 0.74
We consider the continuum-armed bandit problem when the arm sequence is required to be monotone. 腕列が単調である必要がある場合の連続腕包帯問題を考える。 0.63
We show that when the unknown objective function is Lipschitz continuous, the regret is O(T ). 未知の目的関数がリプシッツ連続であるとき、後悔は O(T) であることを示す。 0.66
When in addition the objective function is unimodal or quasiconcave, the regret is ˜O(T 3/4) under the proposed algorithm, which is also shown to be the optimal rate. さらに、目的関数がユニモーダルあるいは準凹である場合、その後悔は、提案されたアルゴリズムの下では、o(t 3/4) となる。 0.62
This deviates from the optimal rate ˜O(T 2/3) in the continuous-armed bandit literature and demonstrates the cost to the learning efficiency brought by the monotonicity requirement. これは、連続武装のバンディット文学における最適速度(T2/3)から逸脱し、単調性要求によってもたらされる学習効率のコストを示す。 0.66
1 Introduction In online learning problems such as the multi-armed bandits (MAB), the decision maker chooses from a set of actions/arms with unknown reward. はじめに マルチアームバンディット(mab)のようなオンライン学習問題において、意思決定者は、未知の報酬を持つ一連のアクション/アームから選択する。
訳抜け防止モード: はじめに マルチ武装バンディット(MAB)のようなオンライン学習問題 意思決定者は、未知の報酬を伴う一連のアクション/アームから選択する。
0.64
The goal is to learn the expected rewards of the arms and choose the optimal one as much as possible within a finite horizon. 目標は、腕の期待される報酬を学習し、有限地平線内でできるだけ最適なものを選ぶことである。 0.73
The framework and its many variants have been successfully applied to a wide range of practical problems, including news recommendation [30], dynamic pricing [9] and medical decision-making [8]. フレームワークとその多くのバリエーションは、ニュースレコメンデーション[30]、ダイナミック価格[9]、医療意思決定[8]など、幅広い実践的な問題にうまく適用されています。
訳抜け防止モード: この枠組みとその多くの変種は、幅広い実用的問題にうまく適用されている。 ニュースレコメンデーション[30], 動的価格[9]を含む そして医学的な判断。 8] を作る.
0.71
Popular algorithms such as UCB [4, 5] and Thompson sampling [3, 33] typically explore the arms sufficiently and as more evidence is gathered, converge to the optimal arm. ucb [4, 5] や thompson sampling [3, 33] のような一般的なアルゴリズムは通常、腕を十分に探索し、より多くの証拠が集められると最適な腕に収束する。 0.69
These algorithms are designed to handle the classic MAB problems, in which the arms are discrete and do not have any order. これらのアルゴリズムは従来のMAB問題に対処するために設計されており、腕は離散的であり順序を持たない。 0.74
However, in some practical problems, the arms are ordinal and even continuous. しかし、いくつかの実践的な問題では、腕は規則的で連続的である。 0.51
This is the focus of the study on the so-called continuum-armed bandit [2, 25, 6, 11, 37]. いわゆるcontinuum-armed bandit [2,25,6,11,37]の研究の焦点である。 0.64
By discretizing the arm space properly, algorithms such as UCB and Thompson sampling can still be applied. アーム空間を適切に判別することで、ucbやトンプソンサンプリングのようなアルゴリズムを適用できる。 0.68
Therefore, the continuous decision space has readily been incorporated into the framework. したがって、連続的な決定空間はフレームワークに容易に組み込まれている。 0.69
Another practical issue, which is not studied thoroughly but emerges naturally from some applications, is the requirement that the action/arm sequence is has to be monotone. 十分に研究されていないが、いくつかの応用から自然に生じるもう1つの現実的な問題は、アクション/アームシーケンスが単調である必要があることである。 0.57
Such a requirement is usually imposed due to external reasons that cannot be internalized to be part of the regret. このような要件は、通常、後悔の一部として内部化できない外部の理由により課せられる。 0.78
We give two concrete examples below. 以下の具体例を2つ挙げる。 0.70
Dynamic pricing. When launching a new product, how does the market demand reacts to the price is typically unknown. 動的価格設定。 新製品をローンチするとき、市場の需要が価格にどう反応するかは通常不明だ。 0.78
Online learning is a popular tool for the firm to learn the demand and make profits simultaneously. オンライン学習は、需要を学習し、同時に利益を上げるための人気のあるツールだ。 0.73
See [21] for a comprehensive review. 包括的なレビューは[21]を参照してください。 0.60
In this case, the arms are the prices charged by the firm. この場合、アームは会社によって請求される価格です。 0.52
However, changing prices arbitrarily over time may have severe adverse effects. しかし、時間とともに価格の変動は深刻な悪影響を及ぼす可能性がある。 0.60
First, early adopters of the product are usually loyal customers. 第一に、製品のアーリーアダプターは通常忠実な顧客です。 0.59
Price drops at a later stage may cause a backlash in this group of customers, whom the firm is the least willing to offend. 後期価格の下落は、この顧客グループに反発を引き起こす可能性がある。
訳抜け防止モード: 後段の価格下落は、このグループの顧客を反発させる可能性がある。 会社を嫌がらせしないのは 誰だ?
0.59
Second, Preprint. 第二に プレプリント。 0.71
Under review. レビュー中。 0.58
英語(論文から抽出)日本語訳スコア
customers are usually strategic, as studied extensively in the literature [38, 31, 42, 30, 16]. 顧客は通常、文献[38, 31, 42, 30, 16]で広く研究されているように、戦略的です。 0.74
The possibility of a future discount may make consumers intentionally wait and hurt the revenue. 将来の割引の可能性により、消費者は故意に売上を待ち、損なう可能性がある。 0.56
A remedy for both issues is a markup pricing policy, in which the firm only increases the price over time. 両方の問題に対する対処策は、マークアップ価格ポリシーであり、同社は時間とともにのみ価格を引き上げている。 0.65
In the online learning framework, it is translated to the requirement that the arms in each period are increasing over time. オンライン学習フレームワークでは、各期間の腕が時間とともに増大しているという要件に翻訳される。 0.81
Clinical trials. Early stage clinical trials for the optimal dose are usually conducted in Phase I/II trials sequentially. 臨床試験。 至適投与の早期臨床試験は通常、第I相/第II相臨床試験で順次行われる。 0.71
The online learning framework has been applied to the dose allocation to identify the optimal dose [40, 7]. 最適線量[40, 7]を特定するために,オンライン学習フレームワークを線量割当に適用した。 0.71
The dose allocation commonly follows the “dose escalation” principle [29]. 線量配分は一般に「ドースエスカレーション」の原理[29]に従っている。 0.73
In particular, after a dose has been assigned to a cohort of patients, their responses are recorded before the next cohort is assigned a higher dose. 特に、患者のコホートに投与が割り当てられた後、その反応は次のコホートがより高い投与量に割り当てられる前に記録される。 0.65
If any of the patients experiences dose limiting toxicities (DLTs), then the trial stops immediately. いずれかの患者がDLT(Dod limiting toxicities)を経験すると、試薬はすぐに停止する。 0.75
The dose escalation principle requires the allocated doses to be increasing over time. 線量エスカレーション原理は、割り当てられた線量の増加を時間とともに要求する。 0.55
A recent paper incorporates the principle in the design of adaptive trials [13]. 最近の論文では適応試験の設計にその原理を取り入れている[13]。 0.81
To accommodate the above applications, in this paper, we incorporate the requirement of monotone arm sequences in online learning, or more specifically, the continuum-armed bandit framework. 本稿では,本論文では,オンライン学習における単調アームシーケンスの要件,具体的には連続腕バンディットフレームワークについて述べる。 0.69
We consider an unknown continuous function f (x) and the decision maker may choose an action/arm Xt in period t. The observed reward Zt is a random variable with mean f (Xt). 未知の連続関数 f (x) を考えると、決定者は周期 t においてアクション/アーム Xt を選択することができる。 0.56
The requirement of monotone arm sequences is translated to X1 ≤ X2 ≤ ··· ≤ XT , where T is the length of the horizon. 単調アーム列の要求は x1 ≤ x2 ≤ ····· ≤ xt に変換され、t は地平線の長さである。
訳抜け防止モード: 単調アーム列の要件は x1 ≤ x2 ≤ · · · · ≤ xt に翻訳される。 tは地平線の長さです
0.72
The goal of the decision maker is to minimize the regret T max f (x) −PT t=1 E[f (Xt)]. 意思決定者の目標は、後悔する T max f (x) −PT t=1 E[f (Xt)] を最小化することである。 0.82
Main results. Next we summarize the main results of the paper informally. 主な結果。 次に,論文の主な成果を非公式に要約する。 0.68
We first show that for a general continuous function f (x), the extra requirement makes learning impossible. まず, 一般連続関数 f (x) に対して, 追加条件が学習を不可能にすることを示す。 0.77
Result. For the class of continuous functions f (x), the regret is at least T /4. 結果。 連続函数 f (x) のクラスに対して、後悔は少なくとも T / 4 である。 0.76
This diverges from the results in the continuum-armed bandit literature. これは、連続したバンディット文学の成果から分かれる。 0.64
In particular, [25] shows that the optimal regret for continuous functions scales with T 2/3 without the monotonicity requirement. 特に[25] は、連続函数の最適後悔は、単調性を必要としない T 2/3 でスケールすることを示している。 0.62
Therefore, to prove meaningful results, we need to restrict the class of functions f (x). したがって、意味のある結果を証明するためには、函数 f (x) のクラスを制限する必要がある。
訳抜け防止モード: したがって、有意義な結果を証明する。 関数 f ( x ) のクラスを制限する必要がある。
0.80
From both the practical and theoretical points of view, we find that assuming f (x) to be unimodal or quasiconcave is reasonable. 実用的および理論的観点から、f(x) をユニモーダルあるいは準凹であると仮定することは妥当である。 0.72
In practice, for the two applications mentioned above, the revenue function in dynamic pricing is typically assumed to be quasiconcave in the price [45]; for clinical trials, the majority of the literature assumes the dose-response curve to be increasing [10], increasing with a plateau effect [32], or unimodal [43], all of which satisfy the assumption. 実際、上記の2つのアプリケーションでは、動的な価格設定における収益関数は、通常[45] で準コンケーブと仮定されるが、臨床試験では、ほとんどの文献では、線量-反応曲線が [10] 増加し、プラトー効果 [32] またはユニモーダル [43] で増加すると仮定されている。
訳抜け防止モード: 実際には、上記の2つのアプリケーションに対して、動的価格の収益関数が典型的に仮定される。 to be quasiconcave in the price [45 ] 臨床試験では、ほとんどの文献では、投与量-反応曲線が増加していると仮定している[10]。 プラトー効果[32]またはユニモーダル[43]で増加する 全ては前提を満たす
0.87
In theory, with the additional assumption, we can show that Result. 理論的には、追加の仮定で、結果を示すことができる。 0.73
There is an algorithm that has monotone arm sequences and achieves regret O(log(T )T 3/4) for continuous and quasiconcave functions f (x). 単調な腕列を持ち、連続および準コンケーブ関数 f (x) に対する後悔のO(log(T )T 3/4) を達成するアルゴリズムがある。 0.81
Note that the rate T 3/4 is still different from that in the continuum-armed bandit literature. なお、T3/4の比率は連続武装バンディットの文献とまだ異なる。 0.70
We then proceed to close the case by arguing that this is the fundamental limit of learning, not due to the design of the algorithm. その後、我々は、これはアルゴリズムの設計のためではなく、学習の基本的な限界であると主張することによって、ケースを締めくくった。 0.64
Result. No algorithm can achieve less regret than T 3/4/32 for the instances we construct. 結果。 アルゴリズムは、構築したインスタンスのT3/4/32よりも後悔の少ないものを実現できない。 0.61
The constructed instances that are hard to learn (see Figure 2) are significantly different from the literature. 学習が難しい構築されたインスタンス(図2参照)は、文献と大きく異なる。 0.68
In fact, the classic construction of “needle in a haystack” [26] does not leverage the requirement of monotone arm sequences and does not give the optimal lower bound. 実際、”needle in a haystack” [26] の古典的な構成は単調アームシーケンスの要件を活用せず、最適な下界を与えない。 0.62
We prove the lower bound by using a novel random variable that is only a stopping time under monotone arm sequences. 単調なアーム列の停止時間のみを持つ新しいランダム変数を用いて下界を証明した。
訳抜け防止モード: 私たちは下界を証明します 単調な腕のシーケンスの下で 停止時間しか持たない 新しいランダム変数を使って。
0.65
By studying the Kullback-Leibler divergence of the probabilities measures involving the stopping time, we are able to obtain the lower bound. 停止時間を含む確率尺度のKulback-Leibler分散を研究することにより、下界を得ることができる。 0.67
We also show numerical studies that complement the theoretical findings. また,理論的知見を補完する数値的研究も行った。 0.64
Related literature. The framework of this paper is similar to the continuum-armed bandit problems, which are widely studied in the literature. 関連文学。 本論文の枠組みは,本論文で広く研究されている連続武装バンディット問題に類似している。 0.74
The earlier studies focus on univariate Lipschitz continuous functions [2, 25] and identify the optimal rate of regret O(T 2/3). 初期の研究では、単変量リプシッツ連続函数 [2, 25] に焦点を当て、後悔のO(T 2/3) の最適速度を特定する。
訳抜け防止モード: リプシッツ連続関数 [2, 25] に関する初期の研究 そして、後悔o(t 2/3)の最適な割合を特定する。
0.65
Later papers study various implications including smoothness [6, 15, 24], the presence of constraints and convexity [9, 41], contextual information and high dimensions [37, 12], and so on. その後の論文では、滑らかさ(6,15,24]、制約と凸性の存在(9,41]、文脈情報と高次元[37,12]など様々な意味について研究した。
訳抜け防止モード: その後の論文では, 滑らかさ [6, 15, 24] など, 様々な意味が研究されている。 制約と凸性[9, 41]の存在 文脈情報と高次元 [37, 12] など。
0.87
The typical reduction used in this stream of literature is to adopt a proper discretization scheme and translate the problem into discrete arms. この文献ストリームで使用される典型的な削減は、適切な離散化スキームを採用し、問題を離散アームに変換することである。
訳抜け防止モード: この文学の流れで使われる典型的な削減は 適切な離散化スキームを採用し、問題を離散アームに変換する。
0.72
In the regret analysis, the Lipschitz continuity or smoothness can be used to control the discretization error. 後悔解析では、離散化誤差を制御するためにリプシッツ連続性または滑らか性を利用することができる。 0.69
Our setting is similar to the study in [25] with quasiconcave objective functions and the additional requirement of monotone arm sequences. 我々の設定は[25]の準コンケーブ目的関数とモノトーンアーム配列の追加要件による研究と似ている。 0.76
The optimal rate of regret, as a result その結果,後悔の度合いは最適である 0.70
2 2 0.85
英語(論文から抽出)日本語訳スコア
Table 1: The optimal regret under different settings in the continuum-armed bandit. 表1: 連続武装のバンディットにおける異なる設定下での最適後悔。 0.76
The regret in [18] is achieved under additional assumptions. 18]の後悔は追加の前提で達成される. 0.77
Paper Concavity Quasiconcavity Monotone Arm Sequences 紙 Concavity Quasiconcavity Monotone Arm Sequences 0.82
[25] This paper [20] [34] [18] [25] 本論文 [20] [34] [18] 0.79
This paper N N Y Y N N 本論文 N N Y Y N 0.69
N N Y Y Y Y N N Y Y Y Y Y 0.96
N Y N Y N Y Regret ˜O(T 2/3) O(T ) ˜O(T 1/2) ˜O(T 1/2) ˜O(T 1/2) ˜O(T 3/4) N Y N Y Y regret シュオ(T 2/3) O(T ) シュオ(T 1/2) シュオ(T 1/2) シュオ(T 1/2) シュオ(T 1/2) シュオ(T 3/4) 0.64
of the difference, deteriorates from T 2/3 to T 3/4. 差分のうち、T2/3からT3/4に劣化する。 0.71
This deterioration can be viewed as the cost of the monotonicity requirement. この劣化は単調性要求のコストと見なすことができる。 0.68
In a recent paper, [34] study a similar problem while assuming the function f (x) is strictly concave. 最近の論文では、[34]関数 f(x) が厳密に凹凸であると仮定しながら、同様の問題を研究している。 0.71
The motivation is from the notion of “fairness” in sequential decision making [44]. 動機は逐次意思決定における“フェアネス”の概念にある[44]。 0.70
The concavity allows them to develop an algorithm based on the gradient information. 凹部は勾配情報に基づくアルゴリズムの開発を可能にする。 0.69
The resulting regret is O(T 1/2), the same as continuum-armed bandit with convexity/concavity [20, 1]. 結果として生じる後悔は、凸/凹凸[20, 1]の連続武装バンディットと同じO(T 1/2)である。 0.65
Comparing to this set of results, the strong concavity prevents the deterioration of regret rates under the monotonicity requirement. この一連の結果と比較すると、強い凹凸は単調性条件下での後悔率の低下を防ぐ。 0.66
In contrast, [18, 19] show that the same rate of regret O(T 1/2) can be achieved if the function is not strictly concave, but just unimodal or quasiconcave, under additional technical assumptions. 対照的に [18, 19] は、関数が厳密な凹凸ではなく、追加の技術的仮定の下ではunimodal あるいは quasiconcave であるなら、同じ後悔の O(T 1/2) の率が達成できることを示している。 0.71
The comparison of the regret rates are shown in Table 1. 後悔率の比較は表1に示す。 0.57
Other requirements on the arm sequence motivated by practical problems are also considered in the literature. 実用的問題に動機づけられた腕の配列に関する他の要件も文献で検討されている。 0.54
[17, 35, 36] are motivated by a similar concern in dynamic pricing: customers are hostile to frequent price changes. 17, 35, 36] は動的価格の同様の懸念によって動機づけられている: 顧客は頻繁な価格変更に敵対している。 0.75
They propose algorithms that have a limited number of switches and study the impact on the regret. 彼らは限られた数のスイッチを持つアルゴリズムを提案し、後悔に対する影響を研究する。 0.71
Motivated by Phase I clinical trials, [22] study the best arm identification problem when the reward of the arms are monotone and the goal is to identify the arm closest to a threshold. 第I相臨床試験で動機付けられた[22]は、腕の報酬が単調な場合に最適な腕の識別問題を研究し、その目標は、しきい値に最も近い腕を特定することである。 0.60
[14] consider the setting when the reward is nonstationary and periodic, which is typical in the retail industry as demand exhibits seasonality. [14] 需要が季節性を示すため、小売業界で典型的である非定常的かつ定期的な条件を考慮。 0.72
Notations. We use Z+ and R to denote all positive integers and real numbers, respectively. 表記。 Z+ と R を使ってそれぞれ正の整数と実数を表す。 0.59
Let := {1, . let := {1, . 0.80
. . , m} for any m ∈ Z+. . . , m} 任意の m ∈ z+ に対して。 0.81
Let x∗ = T ∈ Z+ be the length of the horizon. x∗ = T ∈ Z+ を地平線の長さとする。 0.80
Let [m] arg maxx∈[0,1] f (x) be the set of maximizers of a function f (x) in [0, 1]. m] arg maxxjava[0,1] f (x) を [0, 1] 内の関数 f (x) の最大値の集合とする。 0.83
The indicator function is represented by 1. 指標関数は 1 で表される。 0.67
2 Problem Setup The objective function f (x) : [0, 1] → [0, 1] is unknown to the decision maker. 2 問題の設定 目的関数 f (x) : [0, 1] → [0, 1] は、決定者にとって未知である。 0.84
In each period t ∈ [T ], the decision maker chooses Xt ∈ [0, 1] and collects a random reward Zt which is independent of everything else conditional on Xt and satisfies E[Zt|Xt] = f (Xt). 各期間 t ∈ [T ] において、決定者は Xt ∈ [0, 1] を選択し、Xt 上の他の条件に依存せず E[Zt|Xt] = f (Xt) を満たすランダムな報酬 Zt を集める。 0.86
After T periods, the total (random) reward collected by the decision maker is thus PT t=1 Zt. T期間後、決定者によって収集された合計(ランダム)報酬はPT t=1Ztとなる。 0.70
Since the decision maker does not know f (x) initially, the arm chosen in period t only depends on the previously chosen arms and observed rewards. 意思決定者は最初にf(x)を知らないので、t期で選択された腕は、以前に選択された腕にのみ依存し、報酬を観察する。
訳抜け防止モード: 意思決定者は最初に f ( x ) を知らないので、 時代 tで選ばれた腕は 先に選ばれた腕にしか依存しない。
0.76
That is, for a policy π of the decision maker, we have Xt = πt(X1, Z1, . すなわち、意思決定者のポリシー π に対して、Xt = πt(X1, Z1, ) が成立する。 0.78
. . , Xt−1, Zt−1, Ut), where Ut is an independent random variable associated with the internal randomizer of πt (e g , Thompson sampling). . . , Xt−1, Zt−1, Ut) ここで Ut は πt の内部ランダム化器(例えば、トンプソンサンプリング)に付随する独立確率変数である。 0.82
Before proceeding, we first introduce a few standard assumptions. 先に、いくつかの標準的な仮定を紹介します。 0.50
Assumption 1. The function f (x) is c-Lipschitz continuous, i.e., |f (x1) − f (x2)| ≤ c|x1 − x2|, 仮定1。 函数 f (x) は c-Lipschitz 連続、すなわち |f (x1) − f (x2)| ≤ c|x1 − x2| である。 0.72
for x1, x2 ∈ [0, 1]. x1, x2 ∈ [0, 1] に対して。 0.82
This is a standard assumption in the continuum-armed bandit literature [25, 6, 11, 37]. これはcontinuum-armed bandit literature [25, 6, 11, 37]における標準的な仮定である。 0.83
Indeed, without continuity, the decision maker has no hope to learn the objective function well. 実際、連続性なしでは、意思決定者は目的の機能をうまく学習する望みがありません。 0.62
In this study, we do not consider other smoothness conditions. 本研究では,他の平滑性条件は考慮しない。 0.80
Assumption 2. The reward Zt is σ-subgaussian for all t ∈ [T ]. 仮定2。 報酬 zt はすべての t ∈ [t ] に対して σ-subgaussian である。 0.63
That is, conditional on Xt, つまり、Xt の条件付きです。 0.72
E[exp(λ(Zt − f (Xt)))|Xt] ≤ exp(λ2σ2/2) E[exp(λ(Zt − f(Xt)))|Xt] ≤ exp(λ2σ2/2) 0.92
3 3 0.85
英語(論文から抽出)日本語訳スコア
for all λ ∈ R. Subgaussian random variables are the focus of most papers in the literature, due to their benign theoretical properties. すべての λ ∈ r に対して、subgaussian random variable は、文学におけるほとんどの論文の焦点である。
訳抜け防止モード: すべての λ ∈ r に対して、subgaussian random variable は文学におけるほとんどの論文の焦点である。 良質な理論的な性質のためです
0.71
See [28] for more details. 詳細は[28]を参照してください。 0.81
We can now define an oracle that has the knowledge of f (x). 現在、f (x) の知識を持つ oracle を定義することができる。 0.78
The oracle would choose arm x ∈ arg maxx∈[0,1] f (x) and collect the total reward with mean T maxx∈[0,1] f (x). オラクルは腕 x ∈ arg maxx~[0,1] f (x) を選択し、平均 T maxx~[0,1] f (x) で合計の報酬を集める。 0.87
Because of Assumption 1, the maximum is well defined. 仮定1のため、最大値はよく定義される。 0.78
We define the regret of a policy π as 我々は、ポリシーπの後悔を、定義する。 0.62
Rf,π(T ) = T max x∈[0,1] Rf,π(T ) = T max x∂[0,1] 0.90
f (x) − T Xt=1 f (x) − T Xt=1 0.76
E[f (Xt)]. e[f (xt)] である。 0.68
Note that the regret depends on the unknown function f (x), which is not very meaningful. 後悔は未知の函数 f (x) に依存し、あまり意味を持たないことに注意。 0.75
As a standard setup in the continuum-armed bandit problem, we consider the worst-case regret for all f satisfying Assumption 2. 連続武装バンディット問題の標準設定として、仮定 2 を満たすすべての f に対する最悪の後悔を考える。 0.75
Rπ(T ) := max Rπ(T ) := max 0.96
f Rf,π(T ). f Rf,π(T)。 0.80
Next we present the key requirement in this study: the sequence of arms must be increasing. 次に、本研究における重要な要件として、腕の列が増加し続けていることを挙げる。
訳抜け防止モード: 次に,本研究における重要な要件について述べる。 腕の列は増えてる
0.68
Requirement 1 (Increasing Arm Sequence). 要件1(アームシーケンスの強化)。 0.66
The sequence {Xt}T xt (複数形 xts) 0.34
t=1 must satisfy t=1 を満たさなければならない 0.44
almost surely under π. ほぼ確実にπ以下です 0.73
X1 ≤ X2 ≤ ··· ≤ XT X1 ≤ X2 ≤ ··· ≤ XT 0.78
Note that “increasing” can be relaxed to “monotone” without much effort. 増加”は、あまり努力せずに“モノトーン”に緩和できる点に注意が必要だ。 0.64
For the simplicity of exposition, we only consider the increasing arm sequence. 表現の単純さのため、増大する腕列のみを考える。 0.56
As explained in the introduction, this is a practical requirement in several applications. 紹介で説明されているように、これはいくつかのアプリケーションにおいて実践的な要件である。 0.54
In phase I/II clinical trials, the quantity Xt is the dose applied to the t-th patient and f (x) is the average efficacy of dose x. 第i/ii相臨床試験では、xtは第t期患者に適用される線量であり、f(x)は線量xの平均効果である。 0.67
The dose escalation principle protects the patients from DLTs. 線量エスカレーションの原則は、患者をDLTから保護する。 0.67
More precisely, the doses applied to the patients must increase gradually over time such that the trial can be stopped before serious side effects occur to a batch of patients under high doses. より正確には、患者への服用量は時間とともに徐々に増加し、高用量の患者に深刻な副作用が起こる前に治験を停止させる必要がある。 0.72
In dynamic pricing, Xt is the price charged for the t-th customer and f (x) is the expected revenue under price x. 動的価格では、Xtは第tの顧客に課金される価格であり、f(x)は価格xの予測収益である。 0.79
The increasing arm sequence corresponds to a markup pricing strategy that is typical for new products. 増加するアームシーケンスは、新しい製品に典型的なマークアップ価格戦略に対応する。 0.74
Because of the increasing price, early adopters, who are usually loyal to the product, wouldn’t feel betrayed by the firm. 価格が上昇しているため、製品に忠実なアーリーアダプターは会社に裏切られることはないだろう。
訳抜け防止モード: 価格が高騰したため、アーリーアダプターは通常製品に忠実である。 会社に裏切られたとは思わないだろう。
0.49
Moreover, it deters strategic consumer behavior that may cause a large number of customers to wait for promotions, hurting the firm’s profits. さらに、戦略的な消費者行動が損なわれ、多くの顧客が昇進を待つことになり、会社の利益を損なう恐れがある。 0.73
We point out that under Assumption 1 and 2, which typically suffice to guarantee sublinear regret, the regret Rπ(T ) is at least T /4 under Requirement 1 for all policies π. 仮定 1 と 2 では、通常、部分線型後悔を保証するのに十分であるが、後悔する Rπ(T ) は、すべてのポリシー π に対して要求 1 の下では少なくとも T / 4 である。 0.70
Proposition 1. For all π satisfying Requirement 1, we have Rπ(T ) ≥ T /4 under Assumptions 1 with c = 2 and Assumption 2. 命題1。 要求 1 を満たすすべての π に対して、Rπ(T ) ≥ T /4 は c = 2 と仮定 2 の仮定 1 の下にある。 0.66
The result can be easily illustrated by the two functions (f1(x) in the left and f2(x) in the right) in Figure 1. この結果は、図1の2つの関数(左のf1(x)と右のf2(x))によって簡単に説明できます。 0.87
Because of Requirement 1 and the fact that f1(x) = f2(x) for x ∈ [0, 0.5], we must have PT t=1 1Xt≤0.5 being equal under f1(x) and f2(x) for any given policy π. 要求 1 と x ∈ [0, 0.5] に対して f1(x) = f2(x) であるので、任意のポリシー π に対して PT t=1 1Xt≤0.5 が f1(x) と f2(x) の下で等しいことが必要である。 0.77
Moreover, it is easy to see that さらに、それを見るのは簡単です。 0.73
T 1 2 Xt=1 T 1 2 Xt=1 0.76
T 2 − t=1 1Xt≤0.5 +PT T2 − t=1 1Xt≤0.5 +PT 0.54
1Xt≤0.5, Rf2,π(T ) ≥ T − 1Xt≤0.5, Rf2,π(T ) ≥ T − 0.78
Rf1,π(T ) ≥ Recall the fact PT Rf2,π(T ) ≥ T /2, which implies Proposition 1. Rf1,π(T ) ≥ T /2 は PT Rf2,π(T ) ≥ T /2 である。 0.78
Therefore, to obtain sublinear regret, we need additional assumptions for f (x). したがって、部分線型後悔を得るには、f(x) に対する追加の仮定が必要である。 0.59
In particular, we assume Assumption 3. 特に、仮定3を仮定する。 0.60
The function f (x) is quasiconcave, i.e., for any x1, x2, λ ∈ [0, 1], we have 函数 f (x) は準凸、すなわち任意の x1, x2, λ ∈ [0, 1] に対して、我々が持つ 0.92
t=1 1Xt>0.5 = T . t=11Xt>0.5 = T。 0.70
The above inequalities lead to Rf1,π(T ) + 上記の不等式は Rf1,π(T ) + 0.80
1Xt>0.5 − 1Xt≤0.5. 1Xt>0.5 − 1Xt≤0.5。 0.58
T Xt=1 1 2 T Xt=1 1 2 0.76
T Xt=1 f (λx1 + (1 − λ)x2) ≥ min{f (x1), f (x2)} . T Xt=1 f (λx1 + (1 − λ)x2) ≥ min{f (x1), f (x2)} である。 0.79
4 4 0.85
英語(論文から抽出)日本語訳スコア
1 0.8 0.6 0.4 1 0.8 0.6 0.4 0.65
0.2 0 0 1 0.8 0.2 0 0 1 0.8 0.75
0.6 0.4 0.2 0.6 0.4 0.2 0.59
0 0 0.2 0.4 0 0 0.2 0.4 0.72
0.6 0.8 1 0.2 0.6 0.8 1 0.2 0.65
0.4 0.6 0.8 0.4 0.6 0.8 0.59
1 Figure 1: Two functions (f1(x) in the left and f2(x) in the right) that any policy cannot differentiate before any t such that Xt ≤ 0.5 under Requirement 1. 1 図1: 左の2つの関数(f1(x) と右の f2(x) ) 任意のポリシーが要求1の下で Xt ≤ 0.5 となるような t の前に微分できない。 0.84
In other words, a quasiconcave function is weakly unimodal and does not have multiple separated local maximums. 言い換えれば、準コンケーブ函数は弱ユニモーダルであり、複数の局所最大値を持たない。 0.66
Therefore, f2(x) in Figure 1 is not quasiconcave while f1(x) is. したがって、図1のf2(x) は準凹ではなく、f1(x) はそうである。 0.64
Note that a quasiconcave function may well have a plateau around the local maximum. 準コンケーブ函数は局所極大付近の高原を持つこともあることに注意。 0.69
We impose Assumption 3 on the function class due to two reasons. 2つの理由から、関数クラスに仮定3を課します。 0.74
First, quasiconcavity is probably the weakest technical assumption one can come up with that is compatible with Requirement 1. 第一に、準連結性はおそらく要件1と互換性のある最も弱い技術的仮定である。 0.74
It is much weaker than concavity [34], and it is easy to see from Figure 1 that multiple local maximums tend to cause linear regret under Requirement 1. 凹凸[34]よりもずっと弱いので、図1から複数の局所的な最大値が要求1の下で線形後悔を引き起こす傾向があることが分かりやすい。 0.75
Moreover, unimodal functions are the focus of other studies in the online learning literature [18, 19]. さらに,一助関数はオンライン学習文学における他の研究の焦点となっている[18,19]。 0.81
Second, objective functions in practice are commonly assumed to be quasiconcave. 第二に、目的関数は一般的に準凸であると仮定される。 0.55
For the dynamic pricing example, the revenue function is typically assumed to be quasiconcave in the price [45], supported by theoretical and empirical evidence. 動的価格の例では、収益関数は一般的に[45]の準コンケーブであると仮定され、理論的および経験的証拠によって支持される。 0.71
In clinical trials, most literature assumes the dose-response curve to be quasiconcave [10, 43, 32]. 臨床試験において、ほとんどの文献では、線量-反応曲線は (10, 43, 32] と仮定している。
訳抜け防止モード: 臨床試験では、ほとんどの文献が投与量-反応曲線を仮定する 準コンケーブ[10, 43, 32]
0.81
3 The Algorithm and the Regret Analysis 3 アルゴリズムとレグレト解析 0.55
In this section, we present the algorithm and analyze its regret. 本稿では,アルゴリズムを提示し,その後悔を分析する。 0.78
We first introduce the high-level idea of the algorithm. まず,アルゴリズムの高レベルな考え方を紹介する。 0.71
The algorithm discretizes [0, 1] into K evenly-spaced intervals with end points {0, 1/K, . このアルゴリズムは [0, 1] を終点 {0, 1/K, ... の等間隔に分解する。 0.69
. . , (K − 1)/K, 1}, where K is a tunable hyper-parameter. . . , (K − 1)/K, 1} ここで、K はチューナブルなハイパーパラメータである。 0.82
The algorithm pulls arm k/K for m times sequentially for k = 0, 1, . アルゴリズムは、k = 0, 1, に対して、m倍のアーム k/K を順次引き出す。 0.64
. . , for a hyper-parameter m. It stops escalating k after a batch of m pulls if the reward of arm k/K is not as good as that of a previous arm. . . 腕 k/K の報酬が以前の腕ほど良くない場合、m のバッチが引かれると k のエスカレートが停止する。
訳抜け防止モード: . . ハイパーパラメータ m の場合、m のバッチがプルすると k のエスカレーションが停止する。 腕 k / K の報酬は、前の腕ほど良くない。
0.79
More precisely, the stopping criterion is that the upper confidence bound for the average reward of arm k/K is less than the lower confidence bound for that of some arm i/K for i < k. When the stopping criterion is triggered, the algorithm always pulls arm k/K afterwards. より正確には、停止基準は、arm k/k の平均報酬に対する上限が、i < k に対してある arm i/k に対して低い信頼度よりも小さいことである。
訳抜け防止モード: より正確には、停止基準は、arm k / k の平均報酬に対する上限が、停止基準がトリガーされたとき、i < k に対してある arm i / k のそれに対する低い信頼度よりも小さいことである。 アルゴリズムは常にarm k / k をプルする。
0.76
The detailed steps of the algorithm are shown in Algorithm 1. アルゴリズムの詳細なステップはアルゴリズム1で示される。 0.69
The intuition behind Algorithm 1 is easy to see. アルゴリズム1の背後にある直感は見やすい。 0.63
Because of Assumption 3, the function f (x) is unimodal. 仮定 3 のため、函数 f(x) はユニモーダルである。 0.76
Therefore, when escalating the arms, the algorithm keeps comparing the upper confidence bound of the current arm k/K with the lower confidence bound of the historically best arm. したがって、アームをエスカレートする際、アルゴリズムは現在のアームk/Kの上位信頼境界と歴史的に最高のアームの下位信頼境界を比較し続ける。 0.71
If the upper confidence bound of k/K is lower, then it means k/K is likely to have passed the “mode” of f (x). k/K の上限が低いとすると、k/K は f (x) の「モード」を通り過ぎたことになる。
訳抜け防止モード: k / K の上限が低いとき、 すると、k / K は f ( x ) の「モード」をパスした可能性が高い。
0.75
At this point, the algorithm stops escalating and keeps pulling k/K for the rest of the horizon. この時点で、アルゴリズムはエスカレートを停止し、残りの水平線のためにk/Kを引っ張り続ける。 0.66
Clearly, Algorithm 1 satisfies Requirement 1. 明らかに、アルゴリズム1は要求1を満たす。 0.69
The regret of Algorithm 1 is provided in Theorem 2. アルゴリズム1の後悔は定理2に示される。 0.58
Theorem 2. By choosing K = ⌊T 1/4⌋ and m = ⌊T 1/2⌋, the regret of Algorithm 1 satisfies 定理2。 k = 1/4 と m = 1/2 を選ぶことで、アルゴリズム1の後悔は満たされる。 0.66
Rπ(T ) ≤(cid:18)3c + when T ≥ 16, under Assumptions 1 to 3. Rπ(T ) ≤(cid:18)3c + if T ≥ 16, under Assumptions 1 to 3 0.91
We note that to achieve the regret in Theorem 2, the algorithm requires the information of T and σ but not the Lipschitz constant c. The requirement for σ may be relaxed using data-dependent confidence intervals such as bootstrap, proposed in [27, 23]. 定理 2 において後悔を達成するには、アルゴリズムは t と σ の情報を必要とし、リプシッツ定数 c を必要としない。
訳抜け防止モード: Theorem 2 における後悔の達成に留意する。 アルゴリズムはTとσの情報を必要とするが、リプシッツ定数cではない。 データを使用する -[27, 23]で提案されたブートストラップのような依存信頼区間。
0.69
The requirement for T is typically T の要件は典型的には 0.82
+ 4√3σplog T(cid:19) T 3/4 + 3σplog T(cid:19) T 3/4 0.62
11 2 5 11 2 5 0.85
英語(論文から抽出)日本語訳スコア
Algorithm 1 Increasing arm sequence アルゴリズム1 腕列の増大 0.78
Input: K, m, σ Initialize: k ← 0, t ← 0, S ← 0 while S = 0 do 入力: K, m, σ 初期化: k > 0, t > 0, S > 0 であり、S = 0 である。 0.89
⊲ Stopping criterion Choose Xt+1 = ··· = Xt+m = k/K and observe rewards Zt+1, . ※停止基準 Xt+1 = ··· = Xt+m = k/K を選び、報酬 Zt+1, を観察する。 0.55
. . , Zt+m Calculate the confidence bounds for arm k/K . . , Zt+m は腕 k/K の信頼境界を計算する 0.77
U Bk ← LBk ← 略称はUBk。 通称LBk。 0.29
1 m 1 m t+m t+m 1m 1m t+m t+m 0.69
Xi=t+1 Xi=t+1 Xi=t+1 Xi=t+1 0.32
if U Bk < LBi for some i < k then ある i < k に対して U Bk < LBi であれば 0.79
Zi + σr 2 log m Zi − σr 2 log m Zi + σr 2 log m Zi − σr 2 log m 0.98
m m else S ← 1 t ← t + m, k ← k + 1 M M その他 S > 1 > 1 > 1 t > t + m, k > k + 1 0.69
end if end while Set Xt ≡ k/K for the remaining t 終われば、残りの t に対して Xt > k/K をセットする。 0.62
relaxed using the well-known doubling trick. 有名な2倍のトリックを使ってリラックスしました。 0.43
However, it may not work in this case because of Requirement 1: once T is doubled, the arm cannot start from Xt = 0 again. しかし、この場合、必要条件1: t が二重化されると、arm は xt = 0 から再び起動できない。
訳抜け防止モード: しかし、この場合、要件1:によりうまくいかない場合がある。 t が倍になると、アームは再び xt = 0 からスタートすることができない。
0.74
It remains an open question whether Algorithm 1 can be extended to the case of unknown T . アルゴリズム 1 が未知の T の場合に拡張できるかどうかについては未解決のままである。 0.66
Next we introduce the major steps of the proof of Theorem 2. 次に、定理2の証明の主要なステップを紹介する。 0.67
The discretization error of pulling arms k/K, k ∈ {0, . 引抜きの離散化誤差 arms k/k, k ∈ {0, 。 0.80
. . , K}, is of the order O(T /K). . . , k} は順序 o(t /k) である。 0.80
Therefore, choosing K = O(T 1/4) controls the regret at the desired rate. したがって、K = O(T 1/4) の選択は所望の速度で後悔を制御する。 0.73
We consider the good event, on which f (k/K) is inside the confidence interval [LBk, U Bk] for all k = 0, 1, . 我々は、すべての k = 0, 1, に対して f (k/k) が信頼区間 [lbk, u bk] 内にある良い事象を考える。 0.78
. . until the stopping criterion is triggered. . . 停止基準が発動されるまで 0.76
We choose m such that for a given k this happens with a probability no less than 1 − O(1/m). 任意の k に対して 1 − O(1/m) 未満の確率で発生するような m を選択する。 0.78
Therefore, applying the union bound to at most K discretized arms, the probability of the good event is no less than 1 − O(K/m) = 1 − O(T −1/4). したがって、結合を少なくとも K 個の離散化された腕に限定すると、良い事象の確率は 1 − O(K/m) = 1 − O(T −1/4) となる。 0.78
As a result, the regret incurred due to the bad event is bounded by T O(T −1/4) = O(T 3/4), matching the desired rate. その結果、悪い事象によって生じた後悔は T O(T −1/4) = O(T 3/4) で束縛され、所望の速度に一致する。 0.73
On the good event, the stopping criterion is triggered because arm k/K has passed arg maxx∈[0,1] f (x). 良い事象では、腕 k/K が arg maxx∂[0,1] f (x) を通過したため、停止基準が引き起こされる。 0.73
But it is not much worse than the optimal arm because otherwise the stopping criterion would have been triggered earlier. しかし、それ以外は停止基準が早期に引き起こされた可能性があるため、最適なアームほど悪くはない。 0.64
The gap Multiplying it by T (because k/K is pulled for the rest of the horizon once the stopping criterion is ギャップ T による乗算(停止基準が成立すると k/K が地平線の残りの部分に引かれるため) 0.55
between f (k/K) and f (x∗) is controlled by the width of the confidence interval, O(plog m/m). f(k/k) と f(x∗) は信頼区間 o(plog m/m) の幅によって制御される。 0.83
triggered) gives O(Tplog m/m) = O(T 3/4√log T ). trigger) O(Tplog m/m) = O(T 3/4) を与える。 0.76
Putting the pieces together gives the regret 部品を組み立てると 後悔が生まれます 0.63
bound in Theorem 2. Theorem 2に縛られる。 0.85
4 Lower Bound for the Regret 悔やみのために下限を4つ 0.64
In the classic continuum-armed bandit problem, without Requirement 1, it is well known that there exist policies and algorithms that can achieve regret O(T 2/3), which has also been shown to be tight [25, 6, 37]. 古典的なcontinuum-armed bandit問題では、要件1を伴わずに、後悔のo(t 2/3)を達成するためのポリシーやアルゴリズムがあることはよく知られている。
訳抜け防止モード: 古典的連続体 - 武装した盗賊問題において、要求1なしで 後悔のO(T 2/3 )を達成するためのポリシーやアルゴリズムが存在することはよく知られている。 タイト[25, 6, 37]でもある.
0.78
In this section, we show that in the presence of Requirement 1, no policies can achieve regret less than Ω(T 3/4) under Assumptions 1, 2 and 3. 本節では,要求1の存在下では,仮定1,2,3の条件下で,Ω(T3/4)未満の後悔を達成する政策は存在しないことを示す。 0.72
Theorem 3 (Lower Bound). 原題はTheorem 3 (Lower Bound)。 0.78
When T ≥ 16, under Assumption 1 with c = 1, Assumptions 2 and 3, we have T ≥ 16 の場合、c = 1 の仮定 1 の下で、仮定 2 と 3 が成立する。 0.80
for any policy π satisfying Requirement 1. 要求 1 を満たす任意のポリシー π に対して 0.76
Rπ(T ) ≥ 1 32 Rπ(T ) ≥ 1 32 0.92
T 3/4, Compared to the literature, Theorem 3 implies that Requirement 1 substantially impedes the learning efficiency by increasing the rate of regret from T 2/3 to T 3/4. T3/4 文献と比較すると、要求1はT2/3からT3/4への後悔率を高めて学習効率を著しく低下させる。 0.76
The proof for Theorem 3 is significantly different from that in the literature. 定理3の証明は、文献のそれとは大きく異なる。 0.59
In particular, a typical construction for the lower bound in the continuum-armed bandit literature involves a class of functions that have “humps” in a small interval 特に、連続体で武装したバンディット文学における下限の典型的な構成は、小さな間隔で「ハンプ」を持つ関数のクラスを含んでいる。 0.73
6 6 0.85
英語(論文から抽出)日本語訳スコア
1 0.8 0.6 0.4 1 0.8 0.6 0.4 0.65
0.2 0 0 1 0.8 0.2 0 0 1 0.8 0.75
0.6 0.4 0.2 0.6 0.4 0.2 0.59
0 0 0.2 0.4 0 0 0.2 0.4 0.72
0.6 0.8 1 0.2 0.6 0.8 1 0.2 0.65
0.4 0.6 0.8 0.4 0.6 0.8 0.59
1 Figure 2: The constructed instances for the lower bound in continuum-armed bandit (left panel) and Theorem 3 (right panel). 1 図2: 連続武装バンディット (左パネル) と Theorem 3 (右パネル) の下位境界に対する構築されたインスタンス。 0.83
and are zero elsewhere, as illustrated in the left panel of Figure 2. 図2の左パネルに示されているように、他ではゼロです。 0.72
The idea is to make the functions indistinguishable except for two small intervals. この考え方は、2つの小さな間隔を除いて関数を区別できないものにすることである。 0.52
In our case, it is not sufficient to achieve O(T 3/4). この場合、O(T 3/4) を達成するには不十分である。 0.76
To utilize Requirement 1, the constructed functions in the right panel of Figure 2 share the same pattern before reaching the mode. 要求1を利用するために、図2の右パネルで構築された機能は、モードに到達する前に同じパターンを共有する。
訳抜け防止モード: 要件1を利用する。 図2の右パネルを構成する機能は、モードに到達する前に同じパターンを共有する。
0.82
Afterwards, the functions diverge. 関数はその後発散する。 0.72
The objective is to make it hard for the decision maker to decide whether to keep escalating the arm or stop, and punish her severely if a wrong decision is made. その目的は、意思決定者が腕をエスカレートし続けるか停止するかを判断し、間違った決定がなされた場合には彼女を厳しく罰することである。 0.77
(Consider stopping at the mode of the red function while the actual function is yellow.) (実際の機能は黄色ながら、赤関数のモードに停止する。) 0.72
Such regret is much larger than the hump functions and thus gives rise to the higher rate. このような後悔はハンプ関数よりも遥かに大きいため、より高い率に繋がる。 0.64
Besides the construction of the instances, the proof relies on the following random time インスタンスの構築に加えて、証明は次のランダム時間に依存する 0.68
τ = max{t|Xt ≤ a} τ = max{t|Xt ≤ a} 0.96
for some constant a. ある一定の a に対して。 0.49
Note that τ is typically not a stopping time for a stochastic process Xt. τ は一般に確率過程 Xt の停止時間ではないことに注意。 0.77
Under Requirement 1, however, it is a stopping time. しかし、要件1では、停止する時間です。 0.64
This is the key observation that helps us to fully utilize the monotonicity. これは、モノトニック性を完全に活用するための重要な観察です。 0.56
Technically, this allows us to study the Kullback-Leibler divergence for the probability measures on (X1, Z1, . 技術的には、これは (X1, Z1, ) 上の確率測度に対するクルバック・リーブラの発散を研究することができる。
訳抜け防止モード: 技術的には 我々は、(X1, Z1,) 上の確率測度に対するKulback-Leibler分散を研究する。
0.69
. . , Xτ , Zτ , τ ). . . , Xτ , Zτ , τ )。 0.86
By decomposing the KL-divergence on the events {τ = 1}, {τ = 2}, and so on, we can focus on the periods when Xt ≤ a, which cannot possibly distinguish functions whose mode are larger than a (right panel of Figure 2). 事象 {τ = 1}, {τ = 2} などの KL-分割を分解することで、モードが a (図2の右パネル) よりも大きい関数を区別できない Xt ≤ a の周期に焦点を合わせることができる。 0.68
This observation and innovation is essential in the proof of Theorem 3. この観察と革新は定理3の証明に不可欠である。 0.70
5 Numerical Experiment In this section, we conduct numerical studies to compare the regret of Algorithm 1 with a few benchmarks. 5 数値実験 本稿では,アルゴリズム1の後悔をいくつかのベンチマークと比較するために,数値的研究を行う。 0.73
The experiments are conducted on a Windows 10 desktop with Intel i9-10900K CPU. 実験は、Intel i9-10900K CPUを搭載したWindows 10デスクトップ上で行われる。 0.66
To make a fair comparison, we generate the instances randomly so that it doesn’t bias toward our algorithm. 公平な比較を行うために、インスタンスをランダムに生成し、アルゴリズムに偏らないようにします。 0.69
In particular, we consider T ∈ {1000, 11000, 21000, . 特に、T ∈ {1000, 11000, 21000, を考える。 0.67
. ., 101000}. . ., 101000}. 0.78
For each T , we simulate 100 independent instances. 各Tに対して、100個の独立インスタンスをシミュレートする。 0.64
For each instance, we generate x1 ∼ U (0, 1) and x2 ∼ U (0.5, 1), and let f (x) be the linear interpolation of the three points (0, 0), (x1, x2), and (1, 0). それぞれの例について、x1 で u (0, 1) と x2 で u (0.5, 1) を生成し、f (x) を三点 (0, 0) と (x1, x2) と (1, 0) の線型補間とする。 0.81
The reward Zt ∼ N (f (Xt), 0.1) for all instances and T .1 We consider the following algorithms for each instance: すべてのインスタンスに対する報酬 Zt, N (f (Xt), 0.1) と T .1 は、各インスタンスについて以下のアルゴリズムを考える。 0.79
1. Algorithm 1. 1. アルゴリズム1。 0.75
As stated in Theorem 2, we use K = ⌊T 1/4⌋, m = ⌊T 1/2⌋ and σ = 0.1. 定理 2 で述べられているように、k は 1/4 であり、m は 1/2 であり、σ は 0.1 である。
訳抜け防止モード: Theorem 2 で述べられているように、我々は K = (T 1/4) を用いる。 m = 1/2 および σ = 0.1 である。
0.67
2. The classic UCB algorithm for the continuum-armed bandit. 2. continuum-armed banditの古典的なucbアルゴリズム 0.76
We first discretize the interval [0, 1] into K + 1 equally spaced grid points, {k/K}K まず間隔を識別し [0, 1] を K + 1 に等間隔の格子点 {k/K}K 0.73
k=0, where K = ⌊T 1/3⌋ according k=0 ならば K = 1/3 である。 0.64
to [25]. Then we implement the version of UCB in Chapter 8 of [28] on the multi-armed 25]へ。 次に、マルチアーム上で[28]の8章で UCB のバージョンを実装します。 0.61
1Here U (a, b) denotes a uniform random variable between in [a, b]; N (a, b) denotes a normal random 1 U (a, b) は [a, b] における一様確率変数を表し、N (a, b) は正規確率を表す。
訳抜け防止モード: 1Here U ( a, b ) は [ a, b ] ; N ( a, b ) の間の一様確率変数を表す b) 正常な乱数を示す
0.81
variable with mean a and standard deviation b. 平均 a と標準偏差 b を持つ変数。 0.78
7 7 0.85
英語(論文から抽出)日本語訳スコア
t e r g e R t e r g e R 0.85
105 104 103 105 104 103 0.85
102 101 Algorithm 1 102 101 アルゴリズム1 0.81
UCB UCB Requirement 1 UCB UCB 要件 1 0.82
Deflating UCB 0.2 膨らませるUCB 0.2 0.62
0.4 0.6 0.8 0.4 0.6 0.8 0.59
1 T ·105 Figure 3: The average regret of Algorithm 1 and three benchmarks. 1 T ·105 図3: アルゴリズム1と3のベンチマークの平均的な後悔。 0.78
bandit problem with K + 1 arms. k + 1 の腕のバンディット問題。 0.64
More precisely, we have Xt = arg max より正確には、 Xt = arg max 0.70
(U CBk(t)) (u cbk(t)) 0.56
k/K U CBk(t) =(1 k/K U CBk(t) =(1 0.72
ˆµk(t − 1) + σq 2 log(1+t log(t)2) μk(t − 1) + σq 2 log(1+t log(t)2) 0.96
Tk(t−1) Tk(t − 1) = 0 Tk(t − 1) ≥ 1 Tk(t−1) Tk(t − 1) = 0 Tk(t − 1) ≥ 1 0.85
where µk(t − 1) is the empirical average of arm k, x = k/K, in the first t − 1 periods; Tk(t − 1) is the number that arm k is chosen in the first T − 1 periods. ここで μk(t − 1) は、最初の t − 1 周期における腕 k, x = k/K の経験的平均であり、Tk(t − 1) は腕 k が最初の T − 1 周期で選択される数である。 0.86
Note that in this benchmark we do not impose Requirement 1. このベンチマークでは、要求1を強制しません。 0.58
3. UCB with Requirement 1. 3. UCB with Requirement 1 (英語) 0.79
We follow the same discretization scheme and UCB definition 同じ離散化スキームと ucbの定義に従います 0.78
in the last benchmark, except that we impose Xt+1 ≥ Xt. 最後のベンチマークでは、xt+1 ≥ xt を課す。 0.77
That is (U CBk(t))}. これは (U CBk(t))} である。 0.88
Xt = max{Xt−1, arg max Xt = max{Xt−1, arg max 0.96
k/K 4. Deflating UCB with Requirement 1. k/K 4. 要求1でUCBを膨らませる。 0.70
To improve the performance of UCB with Requirement 1, we need to make the algorithm more likely to stick to the current arm. 要求1で UCB の性能を向上させるためには,アルゴリズムを現在のアームに定着させる可能性を高める必要がある。 0.83
Moreover, when exploring new arms, we need to encourage the algorithm to explore the arm slightly larger than the current arm. さらに、新しいアームを探索する場合は、アルゴリズムに現在のアームよりわずかに大きいアームを探索するよう促す必要がある。 0.67
We design a heuristic for this purpose by deflating the UCB initialization of the arms. 腕のUCB初期化を緩和することで,この目的のためにヒューリスティックな設計を行う。 0.65
More precisely, we let In this way, the decision maker is encouraged to explore arms with small k first and gradually escalate the arms. より正確に言えば、 このようにして、意思決定者は、まず小さなkで腕を探索し、徐々に腕をエスカレートする。
訳抜け防止モード: より正確に言えば、 このようにして意思決定者は奨励される 最初は小さなkで腕を探索し 徐々に腕をエスカレートします
0.65
U CBk(t) = 1 − k/K, if Tk(t − 1) = 0. U CBk(t) = 1 − k/K, if Tk(t − 1) = 0。 0.92
The average regret over the 100 instances is shown in Figure 3. 平均100インスタンスに対する後悔は図3に示されます。 0.74
We may draw the following observations from the experiment. 実験から以下の観察をすることができる。 0.71
First, the regret of UCB is significantly less than the other three algorithms which are constrained by Requirement 1. 第一に、UCBの後悔は、要求1で制約される他の3つのアルゴリズムよりも著しく少ない。 0.69
Therefore, the cost brought to the learning efficiency by Requirement 1 is huge. したがって、要求1による学習効率にもたらすコストは膨大である。 0.82
Second, simply imposing Requirement 1 to the UCB algorithm doesn’t perform well (the green curve). 第二に、要件 1 を UCB アルゴリズムに単純に適用しても、うまく動作しない(グリーンカーブ)。 0.77
It more than triples the regret of Algorithm 1. アルゴリズム1の後悔の度合いは3倍以上だ。 0.69
Third, the deflating UCB heuristic seems to perform well. 第三に、膨らんだUCBヒューリスティックはうまく機能しているようだ。 0.50
Its regret is on par with that of Algorithm 1, although the trend implies a fast scaling with T . その後悔はアルゴリズム1と同等だが、この傾向はtで高速にスケーリングすることを意味する。 0.61
The regret analysis and the optimal choice of the deflating factor remain an open question. 後悔の分析と膨張係数の最適選択は、未解決の問題のままである。 0.69
Overall, Algorithm 1 performs the best among the algorithms that are constrained by Requirement 1. 全体として、アルゴリズム1は要求1によって制約されるアルゴリズムの中で最善の性能を発揮する。 0.64
The result is consistent with the theoretical studies. その結果は理論研究と一致している。 0.82
6 Conclusion In this study, we investigate the online learning or multi-armed bandit problem, when the chosen actions are ordinal and required to be monotone over time. 6 結論 本研究では,オンライン学習やマルチアームバンディット問題において,選択した行動が順序的であり,時間とともに単調でなければならない場合について検討する。 0.66
The requirement appears naturally in その要件は自然に現れる 0.84
8 8 0.85
英語(論文から抽出)日本語訳スコア
several applications: firms setting markup pricing policies in order not to antagonize early adopters and clinical trials following dose escalation principles. いくつかの応用:早期採用者や服用エスカレーションの原則に従って臨床試験に支障を来さないよう、マークアップ価格ポリシーを設定する企業。 0.56
It turns out that the requirement may severely limit the capability of the decision maker to learn the objective function: the worst-case regret is linear in the length of the learning horizon, when the objective function is just continuous. 最悪のケースの後悔は、目的関数がただ連続しているだけである場合、学習地平線の長さにおいて線形である。
訳抜け防止モード: この要件は、意思決定者の能力を著しく制限する可能性があることが判明した。 目的の機能を習得し 最悪の場合、後悔は学習地平線の長さに線形である。 目的関数が連続であるとき
0.75
However, we show that if the objective function is also quasiconcave, then the proposed algorithm can achieve sublinear regret ˜O(T 3/4). しかし, 目的関数が準コンケーブであれば, 提案したアルゴリズムは, 準線形後悔(T3/4)を達成できることを示す。 0.81
It is still worse than the optimal rate in the continuum-armed bandit literature, but is proved to be optimal in this setting. 連続武装バンディット文学の最適率よりも依然として悪いが、この設定では最適であることが証明されている。 0.70
The study has a few limitations and opens up potential research questions. この研究にはいくつかの制限があり、潜在的な研究疑問を開く。 0.59
First, since the doubling trick no longer works, the assumption of knowing T in advance cannot be simply relaxed. まず、二重化トリックはもはや機能しないので、前もって T を知っているという仮定は単純に緩和できない。 0.59
It is not clear if one can design a new algorithm that can achieve the optimal regret even when T is unknown. T が未知であっても最適な後悔を達成できる新しいアルゴリズムを設計できるかどうかは不明である。 0.83
Second, it is unclear if the monotone requirement can be incorporated in contextual bandits. 第二に、モノトーン要件が文脈的バンディットに組み込むことができるかどうかは不明である。 0.48
This is a highly relevant question in clinical trials, which increasingly rely on patient characteristics for the dose allocation. これは臨床試験において非常に関連性の高い質問であり、用量配分の患者特性にますます依存している。
訳抜け防止モード: これは臨床試験において非常に関連性のある質問です 投与量配分の患者特性にますます依存する。
0.72
A novel framework is needed to study how the dose escalation principle plays out in this setting. この設定で線量エスカレーション原理がどのように作用するかを研究するために、新しい枠組みが必要である。
訳抜け防止モード: 新しい枠組みが必要です この設定で線量エスカレーション原理がどのように作用するかを研究する。
0.60
References [1] Alekh Agarwal, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Alexander Rakhlin. 参考文献 Alekh Agarwal、Dean P Foster、Daniel J Hsu、Sham M Kakade、Alexander Rakhlin。 0.60
Stochastic convex optimization with bandit feedback. バンディットフィードバックを用いた確率凸最適化 0.69
In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, Volume 24。 0.94
Curran Associates, Inc., 2011. curran associates, inc., 2011年。 0.63
[2] Rajeev Agrawal. ラジェエフ・アグラヴァル(Rajeev Agrawal)。 0.56
The continuum-armed bandit problem. 連続武装のバンディット問題。 0.69
SIAM journal on control and opti- siam journal on control and opti- 0.82
mization, 33(6):1926–1951, 1995. Mization, 33(6):1926–1951, 1995。 0.85
[3] Shipra Agrawal and Navin Goyal. [3]Shipra AgrawalとNavin Goyal。 0.70
Further optimal regret bounds for thompson sampling. トンプソンサンプリングのためのさらなる最適後悔境界 0.60
In Artificial intelligence and statistics, pages 99–107. 院 人工知能と統計、99-107頁。 0.57
PMLR, 2013. 2013年、PMLR。 0.66
[4] Peter Auer. ピーター・オーアー(Peter Auer)。 0.63
Using confidence bounds for exploitation-explora tion trade-offs. エクスプロレーション-探索トレードオフに信頼境界を使用する。 0.47
Journal of Ma- chine Learning Research, 3(Nov):397–422, 2002. 雑誌『マ』 chine Learning Research, 3(Nov):397-422, 2002。 0.73
[5] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Peter Auer, Nicolo Cesa-Bianchi, Paul Fischer. 0.65
Finite-time analysis of the multiarmed マルチアームの有限時間解析 0.75
bandit problem. Machine learning, 47(2):235–256, 2002. 盗賊問題。 機械学習, 47(2):235–256, 2002。 0.68
[6] Peter Auer, Ronald Ortner, and Csaba Szepesvári. 6]Peter Auer, Ronald Ortner, Csaba Szepesvári 0.53
Improved rates for the stochastic continuumarmed bandit problem. 確率的連続武装バンディット問題に対する改善率 0.62
In International Conference on Computational Learning Theory, pages 454–468. 計算学習理論に関する国際会議」454-468頁。 0.78
Springer, 2007. 2007年、スプリンガー。 0.55
[7] Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. 8]Maryam Aziz、Emilie Kaufmann、Marie-Karelle Riviere。 0.71
On multi-armed bandit designs 多腕バンディットの設計について 0.40
for dose-finding clinical trials. 治療薬を投与する臨床試験。 0.58
Journal of Machine Learning Research, 22:1–38, 2021. Journal of Machine Learning Research, 22:1–38, 2021。 0.82
[8] Hamsa Bastani and Mohsen Bayati. 8]hamsa bastaniとmohsen bayati。 0.52
Online decision making with high-dimensional covariates. 高次元共変量を用いたオンライン意思決定 0.57
Operations Research, 68(1):276–294, 2020. 運用調査, 68(1):276–294, 2020。 0.77
[9] Omar Besbes and Assaf Zeevi. 9]Omar BesbesとAssaf Zeevi。 0.58
Dynamic pricing without knowing the demand function: Risk 需要関数を知らない動的価格設定:リスク 0.79
bounds and near-optimal algorithms. 境界と近似最適アルゴリズム。 0.76
Operations Research, 57(6):1407–1420, 2009. 運用研究、57(6):1407-1420、2009年。 0.61
[10] Thomas M Braun. 10] トーマス・m・ブラウン 0.60
The bivariate continual reassessment method: extending the CRM to phase 二変量連続的再評価法:CRMをフェーズに拡張する 0.80
I trials of two competing outcomes. 私は2つの競争の結果を試す。 0.57
Controlled clinical trials, 23(3):240–256, 2002. 治験23(3):240-256, 2002。 0.58
[11] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. 11] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba Szepesvári。 0.68
X-armed bandits. Jour- nal of Machine Learning Research, 12(5), 2011. X武装の盗賊。 旅 nal of machine learning research, 12(5), 2011を参照。 0.58
[12] Ningyuan Chen and Guillermo Gallego. [12]寧元陳とギレルモ・ガレゴ。 0.55
Nonparametric pricing analytics with customer co- 顧客共同による非パラメトリック価格分析 0.81
variates. Operations Research, Forthcoming. 変種。 オペレーションリサーチ、近日開始。 0.63
[13] Ningyuan Chen and Amin Khademi. 13] 寧元 チェンと アミン・ハデミ。 0.65
Adaptive seamless dose-finding trials. 適応的シームレス線量フィリング試験。 0.63
Working Paper, 2020. 作業用紙。 2020. 0.77
[14] Ningyuan Chen, Chun Wang, and Longlin Wang. [14]寧庵陳、忠王、龍林王。 0.56
Learning and optimization with seasonal patterns. 季節的学習と最適化 パターン 0.65
Working paper, 2020. 新聞社、2020年。 0.61
[15] Qi Chen, Stefanus Jasin, and Izak Duenyas. [15]Qi Chen、Stefanus Jasin、Izak Duenyas。 0.66
Nonparametric self-adjusting control for joint learning and optimization of multiproduct pricing with finite resource capacity. 共用学習のための非パラメトリック自己調整制御と有限資源容量多産物価格の最適化 0.83
Mathematics of Operations Research, 44(2):601–631, 2019. 算術演算研究44(2):601-631, 2019。 0.71
[16] Yiwei Chen and Vivek F Farias. 16]Yiwei ChenとVivek F Farias。 0.65
Robust dynamic pricing with strategic customers. 戦略的顧客による堅牢な動的価格設定。 0.71
Mathemat- ics of Operations Research, 43(4):1119–1142, 2018. 数学 ics of operations research, 43(4):1119–1142, 2018年。 0.71
9 9 0.85
英語(論文から抽出)日本語訳スコア
[17] Wang Chi Cheung, David Simchi-Levi, and He Wang. [17]Wang Chi Cheung、David Simchi-Levi、He Wang。 0.76
Dynamic pricing and demand learning 動的価格設定と需要学習 0.90
with limited price experimentation. Operations Research, 65(6):1722–1731, 2017. 限定的な価格実験で 運用調査, 65(6):1722-1731, 2017。 0.77
[18] Richard Combes and Alexandre Proutiere. リチャード・コムスとアレクサンドル・プティエール。 0.61
Unimodal bandits: Regret lower bounds and optimal algorithms. ユニモーダル・バンディット(Unimodal bandits): 下位境界と最適アルゴリズムをレグレットする。 0.48
In International Conference on Machine Learning, pages 521–529. 国際機械学習会議において、521-529頁。 0.79
PMLR, 2014. 2014年、PMLR。 0.67
[19] Richard Combes, Alexandre Proutière, and Alexandre Fauquette. 19]リチャード・コームズ、アレクサンドル・プロティエール、アレクサンドル・フォーケット 0.53
Unimodal bandits with continuous arms: Order-optimal regret without smoothness. 連続した腕を持つ単調な包帯:滑らかさのない順序最適後悔。 0.56
Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1–28, 2020. ACM on Measurement and Analysis of Computing Systems, 4(1):1-28, 2020 0.74
[20] Eric W Cope. エリック・W・コープ(Eric W Cope) 0.59
Regret and convergence bounds for a class of continuum-armed bandit problems. 連続体武装のバンディット問題のクラスに対する後悔と収束の限界。 0.67
IEEE Transactions on Automatic Control, 54(6):1243–1253, 2009. IEEE Transactions on Automatic Control, 54(6):1243–1253, 2009 0.93
[21] Arnoud V Den Boer. [21]Arnoud V Den Boer 0.61
Dynamic pricing and learning: historical origins, current research, and 動的価格と学習--歴史的起源、現在の研究、そして 0.87
new directions. Surveys in operations research and management science, 20(1):1–18, 2015. 新しい方向だ 20(1):1-18, 2015年オペレーション・リサーチ・マネジメント・サイエンス調査 0.71
[22] Aurélien Garivier, Pierre Ménard, Laurent Rossi, and Pierre Menard. Aurélien Garivier氏、Pierre Ménard氏、Laurent Rossi氏、Pierre Menard氏。 0.63
Thresholding bandit for Thresholding bandit for ~ 0.85
dose-ranging: The impact of monotonicity. 線量配置:単調性の影響。 0.63
Working paper, 2017. 新聞社、2017年。 0.56
[23] Botao Hao, Yasin Abbasi-Yadkori, Zheng Wen, and Guang Cheng. 23]botao hao、yasin abbasi-yadkori、zheng wen、guang cheng。 0.58
Bootstrapping upper confi- ブートストラップ上部コンフィ- 0.55
dence bound. Working Paper, 2019. デンス・バウンドだ 2019年 新聞社。 0.36
[24] Yichun Hu, Nathan Kallus, and Xiaojie Mao. [24]Yichun Hu、Nathan Kallus、Xiaojie Mao。 0.59
Smooth contextual bandits: Bridging the parametric and non-differentiable regret regimes. 平滑なコンテキスト的バンディット:パラメトリックと非微分可能な後悔のレジームを橋渡しする。 0.50
In Conference on Learning Theory, pages 2007– 2010. 2007-2010年「学習理論に関する会議」に参加。 0.70
PMLR, 2020. PMLR、2020年。 0.88
[25] Robert Kleinberg. ロバート・クラインバーグ(Robert Kleinberg)。 0.67
Nearly tight bounds for the continuum-armed bandit problem. 連続武装バンディット問題に対するほぼ厳密な境界 0.70
Advances in Neural Information Processing Systems, 17:697–704, 2004. 進歩 Neural Information Processing Systems, 17:697–704, 2004。 0.60
[26] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Robert Kleinberg氏、Aleksandrs Slivkins氏、Eli Upfal氏。 0.48
Multi-armed bandits in metric spaces. 距離空間における多重武装バンディット 0.47
In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681–690, 2008. 第40回年次acmコンピューティング理論シンポジウムの報告(681-690頁、2008年)
訳抜け防止モード: コンピューティング理論に関する第40回年次ACMシンポジウムの開催報告 681-690頁、2008年。
0.76
[27] Branislav Kveton, Csaba Szepesvari, Sharan Vaswani, Zheng Wen, Tor Lattimore, and Mohammad Ghavamzadeh. [27]Branislav Kveton, Csaba Szepesvari, Sharan Vaswani, Zheng Wen, Tor Lattimore, Mohammad Ghavamzadeh。 0.73
Garbage in, reward out: Bootstrapping exploration in multi-armed bandits. Garbage in, reward out: Bootstrapping Explor in multi-armed bandits。 0.86
In International Conference on Machine Learning, pages 3601–3610. International Conference on Machine Learningで、3601–3610頁。 0.89
PMLR, 2019. 2019年、PMLR。 0.72
[28] Tor Lattimore and Csaba Szepesvári. [28]Tor LattimoreとCsaba Szepesvári。 0.78
Bandit algorithms. バンディットアルゴリズム。 0.61
Cambridge University Press, 2020. ケンブリッジ大学出版局、2020年。 0.66
[29] Christophe Le Tourneau, J Jack Lee, and Lillian L Siu. Christophe Le Tourneau氏、J Jack Lee氏、Lillian L Siu氏。 0.63
Dose escalation methods in phase I cancer clinical trials. 第I相がん臨床試験におけるドーズエスカレーション法 0.72
JNCI: Journal of the National Cancer Institute, 101(10):708–720, 2009. JNCI: Journal of the National Cancer Institute, 101(10):708-720, 2009 0.90
[30] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. [30]Lihong Li、Wei Chu、John Langford、Robert E Schapire。 0.72
A contextual-bandit approach to personalized news article recommendation. パーソナライズされたニュース記事レコメンデーションへのコンテキスト帯域アプローチ 0.56
In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010. 第19回world wide web国際会議の議事録、2010年661-670頁。 0.74
[31] Qian Liu and Garrett J Van Ryzin. [31]Qian LiuとGarrett J Van Ryzin。 0.76
Strategic capacity rationing to induce early purchases. 早期購入を促すための戦略的能力配分。 0.69
Management Science, 54(6):1115–1131, 2008. 経営科学、54(6):1115–1131, 2008。 0.79
[32] Marie-Karelle Riviere, Ying Yuan, Jacques-Henri Jourdan, Frédéric Dubois, and Sarah Zohar. [32]Marie-Karelle Riviere、Ying Yuan、Jacques-Henri Jourdan、Frédéric Dubois、Sarah Zohar。 0.82
Phase I/II dose-finding design for molecularly targeted agent: plateau determination using adaptive randomization. 分子標的剤のフェーズi/ii線量探索設計:適応ランダム化を用いたプラトー決定 0.71
Statistical methods in medical research, 27(2):466–479, 2018. 医学研究における統計手法 27(2):466–479, 2018。 0.80
[33] Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. [33]Daniel J. Russo、Benjamin Van Roy、Abbas Kazerouni、Ian Osband、Zheng Wen。 0.66
A tutorial on thompson sampling. チュートリアル トンプソンのサンプリングで 0.43
Found. Trends Mach. 見つかった トレンドマッハ。 0.58
Learn., 11(1):1–96, July 2018. 11(1):1-96、2018年7月。 0.68
[34] Jad Salem, Swati Gupta, and Vijay Kamble. [34]Jad Salem、Swati Gupta、Vijay Kamble。 0.58
Taming wild price fluctuations: Monotone stochas- 乱暴な価格変動:モノトーン・ストチャス- 0.70
tic convex optimization with bandit feedback. tic convex Optimization with bandit feedback. 0.83
Working paper, 2021. [35] David Simchi-Levi and Yunzong Xu. 2021年製紙。 [35]David Simchi-LeviとYunzong Xu。 0.74
Phase transitions and cyclic phenomena in bandits with switching constraints. スイッチング制約をもつ帯域における相転移と循環現象 0.80
In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, R. Garnett, editors, Advances in Neural Information Processing Systems, Volume 32。 0.91
Curran Associates, Inc., 2019. Curran Associates, Inc., 2019 0.71
[36] David Simchi-Levi, Yunzong Xu, and Jinglong Zhao. [36]David Simchi-Levi、Yunzong Xu、Jinglong Zhao。 0.79
Blind network revenue management and ブラインドネットワーク収益管理と 0.72
bandits with knapsacks under limited switches. 限定スイッチ下のナップサック付きバンディット。 0.57
Working paper, 2019. 新聞社、2019年。 0.50
[37] Aleksandrs Slivkins. [37]Aleksandrs Slivkins。 0.60
Contextual bandits with similarity information. 類似情報付きコンテキストバンディット。 0.60
Journal of Machine Journal of Machine 0.85
Learning Research, 15(73):2533–2568, 2014. 学習研究 15(73):2533–2568, 2014 0.84
[38] Xuanming Su. [38]xuanming su。 0.65
Intertemporal pricing with strategic customer behavior. 戦略的顧客行動による時間的価格設定。 0.67
Management Science, 53(5):726–741, 2007. 経営学。 53(5):726–741, 2007. 0.68
10 10 0.85
英語(論文から抽出)日本語訳スコア
[39] Alexandre B Tsybakov. 39] アレクサンドル・b・ツィバコフ 0.58
Introduction to nonparametric estimation. 非パラメトリック推定入門。 0.60
Springer Science & Busi- Springer Science & Busi- 0.98
ness Media, 2008. 2008年、メディア。 0.74
[40] Sofía S Villar, Jack Bowden, and James Wason. 40] Sofía S Villar、Jack Bowden、James Wason。 0.68
Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. 臨床試験の最適設計のためのマルチアームバンディットモデル:利点と課題 0.59
Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015. 統計学 数学統計学研究所(Institute of Mathematical Statistics, 30(2):199, 2015)のレビュージャーナル。 0.83
[41] Zizhuo Wang, Shiming Deng, and Yinyu Ye. [41]Zizhuo Wang、Shiming Deng、Yinyu Ye。 0.60
Close the gaps: A learning-while-doing algorithm for single-product revenue management problems. ギャップを埋める: 単一製品収益管理問題に対する学習時処理アルゴリズム。 0.81
Operations Research, 62(2):318–331, 2014. 運用調査, 62(2):318–331, 2014 0.87
[42] Rui Yin, Yossi Aviv, Amit Pazgal, and Christopher S Tang. 42]rui yin、yossi aviv、amit pazgal、christopher s tang。 0.50
Optimal markdown pricing: Implications of inventory display formats in the presence of strategic customers. 最適マークダウン価格:戦略的顧客の存在下での在庫表示形式の影響。 0.79
Management Science, 55(8):1391–1408, 2009. 経営科学、55(8):1391–1408、2009年。 0.65
[43] Wei Zhang, Daniel J Sargent, and Sumithra Mandrekar. [43]Wei Zhang、Daniel J Sargent、Sumithra Mandrekar。 0.66
An adaptive dose-finding design in- 適応的線量フィニング設計- 0.76
corporating both toxicity and efficacy. 毒性と効果を 組み合わせること。 0.61
Statistics in Medicine, 25(14):2365–2383, 2006. 医学統計、25(14):2365–2383, 2006。 0.82
[44] Xueru Zhang and Mingyan Liu. 44]Xueru ZhangとMingyan Liu。 0.65
Fairness in learning-based sequential decision algorithms: A 学習に基づく逐次決定アルゴリズムの公正性:A 0.78
survey. Working paper, 2020. 調査。 新聞社、2020年。 0.63
[45] Serhan Ziya, Hayriye Ayhan, and Robert D Foley. [45]Serhan Ziya, Hayriye Ayhan, Robert D Foley。 0.71
Relationships among three assumptions in revenue management. 3つの仮定間の関係 収益管理。 0.70
Operations Research, 52(5):804–809, 2004. 運用研究、52(5):804–809, 2004。 0.83
A Proofs Proof of Theorem 2: Let x∗ ∈ arg maxx∈[0,1] f (x). 証明 定理 2 の証明: x∗ ∈ arg maxx∂[0,1] f (x) とする。 0.62
Because K = ⌊T 1/4⌋, we can find k∗ such that |x∗ − k/K| ≤ 1/(2⌊T 1/4⌋). K = s T 1/4 であるから、k∗ は |x∗ − k/K| ≤ 1/(2 s T 1/4 ) となる。 0.63
Therefore, we have Rπ(T ) = T f (x∗) − したがって、我々は Rπ(T ) = T f(x∗) − 0.89
T Xt=1 E[f (Xt)] T Xt=1 E[f(Xt)] 0.72
= T f (x∗) − T f (k∗/K) + (T f (k∗/K) − = T f (x∗) − T f (k∗/K) + (T f (k∗/K) − 0.99
T Xt=1 E[f (Xt)]) T Xt=1 E[f(Xt)]) 0.70
T Xt=1 ≤ T c|x∗ − k/K| + (T f (k∗/K) − T Xt=1 ≤ T c|x∗ − k/K| + (T f (k∗/K) − 0.73
E[f (Xt)]) = E[f(Xt)]) = 0.75
cT 2K + (T f (k∗/K) − cT 2K + (T f (k∗/K) − 0.92
T Xt=1 E[f (Xt)]). T Xt=1 e[f (xt)]) である。 0.69
(1) mPm Here the first (1) mPm 最初は 0.71
inequality is due to Assumption 1. 不平等は仮定1による。 0.64
Next we can focus on T f (k∗/K) − 次に t f (k∗/k) − に集中することができる。 0.63
PT t=1 E[f (Xt)]), the regret relative to the best arm in {0, 1/K, . pt t=1 e[f (xt)]), {0, 1/k, .} の最高のアームに対する後悔。 0.66
. . , (K − 1)/K, 1}. . . , (K − 1)/K, 1。 0.82
Consider m IID random rewards Z ′ k/K, for k = 0, . k = 0 に対して m IID のランダム報酬 Z ′ k/K を考える。 0.79
. . , K. Let ¯Z ′ k = 1 . . , K. > Z ′ k = 1 とする。 0.79
k,1, . . . , Z ′ t=1 Z ′ K,1。 . . , Z ′ t=1 Z ′ 0.83
k,m having the same distribution as Zt when Xt = k,m. k,m は Xt = k,m のとき Zt と同じ分布を持つ。 0.86
Consider the event E as イベントEを考えてみましょう 0.66
E :=( ¯Z ′ k − σr 2 log m E :=(~Z′) k − σr 2 log m 0.85
m ≤ f (k/K) ≤ ¯Z ′ m ≤ f (k/K) ≤ Z ′ 0.95
k + σr 2 log m k + σr 2 log m 0.97
m , ∀k ∈ {0, . M は、k ∈ {0, である。 0.70
. . , K}) . . . , k) であった。 0.76
If we couple Z ′ k,i, i = 1, . Z ′ k, i, i = 1 と組む。 0.52
. . , m, with the rewards generated in the algorithm pulling arm k/K, then the event represents the high-probability event that the f (k/K) is inside the confidence interval [LBk, U Bk]. . . そして、アルゴリズムがk/Kに生成した報酬をmとすると、この事象は、f(k/K)が信頼区間[LBk,UBk]内にある高確率事象を表す。 0.80
Using the standard concentration bounds for subgaussian random variables (note that k is σ/√m-suggaussian), we have ¯Z ′ 準ガウス確率変数の標準濃度境界(k は σ/n-suggaussian であることに注意)を用いると、Z′ となる。 0.67
P(Ec) ≤ ∪K P(Ec) ≤ >K 0.89
k=0 P | ¯Z ′ K=0 P | ...Z ′ 0.59
m ! k]| > σr 2 log m k − E[ ¯Z ′ m (cid:27) = ≤ (K + 1)2 exp(cid:26)− m 2σ2 × M! k]| > σr 2 log m k − E[ >Z ′ m (cid:27) = ≤ (K + 1)2 exp(cid:26)− m 2σ2 × 0.84
2σ2 log m 2(K + 1) 2σ2 log m 2(K + 1) 0.82
m . (2) 11 M . (2) 11 0.83
英語(論文から抽出)日本語訳スコア
Based on the event E, we can decompose the regret as イベントEに基づいて、後悔を分解できる 0.48
T f (k∗/K) − T f (k∗/K) − 0.92
T Xt=1 E[f (Xt)] = T Xt=1 E[f (Xt)] = 0.73
≤ ≤ T T Xt=1 Xt=1 Xt=1 ≤ ≤ T T Xt=1 Xt=1 Xt=1 0.77
T E [(f (k∗/K) − f (Xt))1E] + T E [(f (k∗/K) − f (Xt))1E] + 0.90
T Xt=1 E [(f (k∗/K) − f (Xt))1Ec] T Xt=1 E [(f (k∗/K) − f (Xt))1Ec] 0.80
E [(f (k∗/K) − f (Xt))1E] + T P(Ec) E [(f (k∗/K) − f (Xt))1E] + T P(Ec) 0.93
E [(f (k∗/K) − f (Xt))1E] + E [(f (k∗/K) − f (Xt))1E] + 0.95
2T (K + 1) m , 2T(K+1) M , 0.83
(3) where the first inequality follows from f (k∗/K) ≤ 1 and the second inequality follows from (2). (3) 第一の不等式は f (k∗/k) ≤ 1 から、第二不等式は (2) から続く。 0.77
Next we analyze the first term of (3). 次に (3) の第一項を分析する。 0.77
We can divide the horizon into two phases [0, T1] and [T1 + 1, T ], based on when the stopping criterion is triggered. 停止基準がトリガーされると、水平線を[0, t1] と [t1 + 1, t ] の2つの位相に分割することができる。 0.75
Before the stopping criterion, the first term of (3) is bounded by 停止基準の前に、(3)の第一項は境界付きである 0.84
E" T1 Xt=1 E [(f (k∗/K) − f (Xt))1E]# ≤ (K + 1)mf (k∗/K) ≤ (K + 1)m E"T1 Xt=1 E [(f (k∗/K) − f (Xt))1E]# ≤ (K + 1)mf (k∗/K) ≤ (K + 1)m 0.82
(4) To analyze the second phase, since we can couple the random variables Z ′ k,m and the rewards of arm k/K, we can suppose that LBk ≤ f (k/K) ≤ U Bk on event E for all k during Algorithm 1. (4) 第2相を解析するために、ランダム変数 Z ′ k,m とアーム k/K の報酬を対応付けることができるので、アルゴリズム 1 の全ての k に対して、事象 E 上の LBk ≤ f (k/K) ≤ U Bk と仮定できる。 0.83
Note that when the stopping criterion S ← 1 is triggered for some arm k/K in Algorithm 1, we must have (5) アルゴリズム1のいくつかのarm k/kに対して停止基準 s s 1 がトリガーされると、(5) を持つ必要があることに注意せよ。 0.59
f (k/K) ≤ U Bk < LBi ≤ f (i/K) f (k/K) ≤ U Bk < LBi ≤ f (i/K) 0.93
for some i < k. Note that (5), combined with Assumption 3, implies that x∗ ≤ k/K. ある i < k に対して (5) と仮定 3 が組み合わさって x∗ ≤ k/K となることに注意。 0.77
Otherwise we have f (x∗) ≥ f (i/K) > f (k/K) while i/K < k/K < x∗, which contradicts Assumption 3. そうでなければ、f (x∗) ≥ f (i/K) > f (k/K) であり、i/K <k/K <x∗ である。 0.75
This fact then implies that k∗ ≤ k and furthermore k∗ ≤ k − 1 because f (k/K) ≤ f (i/K). この事実は、k∗ ≤ k であり、さらに f (k/K) ≤ f (i/K) であるから k∗ ≤ k − 1 である。 0.75
Because the stopping criterion is triggered for the first time, it implies that 停止基準が初めて引き起こされるため、これが意味する。 0.55
f ((k − 1)/K) ≥ LBk−1 = U Bk−1 − 2σr 2 log m f ((k − 1)/K) ≥ LBk−1 = U Bk−1 − 2σr 2 log m 0.87
m ≥ LBi − 2σr 2 log m m ≥ LBi − 2σr 2 log m 0.96
m ≥ U Bi − 4σr 2 log m M ≥ U Bi − 4σr 2 log m 0.86
m ≥ f (i/K) − 4σr 2 log m m ≥ f (i/K) − 4σr 2 log m 0.88
m . (6) Here the first inequality is due to event E. The first equality is due to the definition of U B and LB. M . (6) ここで、第一の不等式は事象 E によるものであり、第一の等式は UB と LB の定義によるものである。 0.76
The second inequality is due to the fact that the stopping criterion is not triggered for arm k′/K. 第2の不等式は、アーム k′/K に対して停止基準が引き起こされないためである。 0.65
The last inequality is again due to event E. Moreover, because arm i/K is historically the best among {0, 1/K, . さらに、arm i/k は歴史的に {0, 1/k, ... の中で最良である。
訳抜け防止モード: 最後の不等式はイベントEによるものである。 arm i / K は歴史的に {0, 1 / K,
0.68
. . , (k − 1)/K}, we have . . , (k − 1)/k} です。 0.79
f (i/K) ≥ LBi ≥ LBk′ = U Bk′ − 2σr 2 log m f (i/K) ≥ LBi ≥ LBk′ = U Bk′ − 2σr 2 log m 0.87
m ≥ f (k′/K) − 2σr 2 log m m ≥ f (k′/K) − 2σr 2 log m 0.83
m (7) for all 0 ≤ k′ ≤ k − 1. M (7) すべての 0 ≤ k′ ≤ k − 1 に対して。 0.80
Now (6) and (7), combined with k∗ ≤ k − 1, imply that ここで (6) と (7) は k∗ ≤ k − 1 と組み合わされ、つまり、 0.89
f(cid:18) k − 1 f(cid:18) k − 1 0.94
K (cid:19) ≥ f (i/K) − 4σr 2 log m K (cid:19) ≥ f (i/K) − 4σr 2 log m 0.84
m ≥ f (k∗/K) − 6σr 2 log m m ≥ f (k∗/K) − 6σr 2 log m 0.88
m . By Assumption 1, we then have M . 仮定1により、我々は 0.75
f (k/K) ≥ f(cid:18) k − 1 f (k/K) ≥ f(cid:18) k − 1 0.90
K (cid:19) − K (cid:19) − 0.88
c K ≥ f (k∗/K) − c K ≥ f (k∗/K) − 0.96
c K − 6σr 2 log m c K − 6σr 2 log m 0.88
m . Plugging the last inequality back into the first term of (3) in the second phase, we have M . 最後の不等式を第2フェーズで(3)の第一項に戻すと、 0.72
E" T Xt=T1+1 E"T Xt=T1+1 0.58
E [(f (k∗/K) − f (Xt))1E]# ≤ T (f (k∗/K) − f (k/K)) ≤ E [(f (k∗/K) − f (Xt))1E]# ≤ T (f (k∗/K) − f (k/K)) ≤ 0.99
cT K + 6σr 2 log m cT K + 6σr 2 log m 0.87
m T. (8) 12 M t. (8) 12 0.84
英語(論文から抽出)日本語訳スコア
Combining (1), (3), (4) and (8), we have (1), (3), (4), (8) を組み合わせると 0.53
Rπ(T ) ≤ cT 2K Rπ(T ) ≤ cT 2K 0.94
+ 2(K + 1)T + 2(K + 1)T 0.85
m + (K + 1)m + M + (K + 1)m + 0.80
cT K + 6σr 2 log m cT K + 6σr 2 log m 0.87
m T ≤ 3cT 3/4 + 4T 3/4 + ≤(cid:18)3c + M T ≤ 3cT 3/4 + 4T 3/4 + ≤(cid:18)3c + 0.78
11 2 + 4√3σplog T(cid:19) T 3/4, 11 2 + 3σplog T(cid:19) T 3/4, 0.75
3 2 T 3/4 + 4√3σplog T T 3/4 3 2 T 3/4 + 4\3σplog T T 3/4 0.71
where we have plugged in K = ⌊T 1/4⌋ and m = ⌊T 1/2⌋, and moreover, ここでは、K = の T 1/4 であり、m = の T 1/2 である。 0.63
3 K ≤ T 1/4 ≤ 2K, K + 1 ≤ 2 because T ≥ 16. 3 K ≤ T 1/4 ≤ 2K, K + 1 ≤ 2 は T ≥ 16 である。 0.91
This completes the proof. これが証明を完了します。 0.61
T 1/4, T 1/2 ≤ T 1/2 − 1 ≤ m ≤ T 1/2, T1/4 T 1/2 ≤ T 1/2 − 1 ≤ m ≤ T 1/2, 0.82
3 4 Proof of Theorem 3: Let K = ⌊T 1/4⌋ and construct a family of functions fk(x) as follows. 3 4 定理3の証明: K = s T 1/4 とし、次の関数 fk(x) の族を構成する。 0.81
For k ∈ [K], let k ∈ [K] に対して、 0.82
fk(x) =(cid:26)x fk(x) =(cid:26)x 0.98
x ∈ [0, (k − 1/2)/K) max{(2k − 1)/K − x, 0} x ∈ [(k − 1/2)/K, 1] x ∈ [0, (k − 1/2)/K) max{(2k − 1)/K − x, 0} x ∈ [(k − 1/2)/K, 1] 0.99
As a result, we can see that maxx∈[0,1] fk(x) = (k − 1/2)/K is attained at x = (k − 1/2)/K. その結果、maxx∂[0,1] fk(x) = (k − 1/2)/K が x = (k − 1/2)/K で到達することが分かる。 0.90
Clearly, all the functions satisfy Assumption 1 with c = 1 and Assumption 3. 明らかに、すべての関数は仮定 1 を c = 1 と仮定 3 で満たしている。 0.78
For each fk(x), we construct the associated reward sequence by Zt ∼ N (fk(Xt), 1), which is a normal random variable with mean fk(Xt) and standard deviation 1. 各fk(x) に対して、平均 fk(Xt) と標準偏差 1 を持つ正規確率変数である Zt > N (fk(Xt), 1) によって関連する報酬列を構築する。 0.73
It clearly satisfies Assumption 2. 仮定2を満たしている。 0.69
Consider a particular policy π. 特定のポリシー π を考える。 0.77
Let Rk := Rfk,π(T ) いくぞ Rk := Rfk,π(T) 0.64
be the regret incurred when the objective function is fk(x) for k ∈ [K]. 目的関数が k ∈ [K] に対して fk(x) であるときに生じる後悔である。 0.83
Because of the construction, it is easy to see that for the objective function fk(x), if Xt /∈ [(k − 1)/K, k/K], then a regret no less than 1/(2K) is incurred in period t. Therefore, we have この構成のため、目的関数 fk(x) に対して、Xt /∂ [(k − 1)/K, k/K] が成立すれば、期間 t で 1/(2K) 以下の後悔が生じることが容易にわかる。 0.69
Here we use Ek to denote the expectation taken when the objective function is fk(x). ここでは、目的関数が fk(x) であるときに取られる期待を表すために ek を用いる。 0.70
On the other hand, if we focus on RK , then it is easy to see that 一方、RKに注目すると、それは容易にわかる。 0.50
Rk ≥ 1 2K T Rk ≥ 1 2K T 0.86
Xt=1 Ek[1Xt /∈[(k−1)/K,k/K]]. Xt=1 Ek[1Xt/∂[(k−1)/K,k/K]。 0.72
(9) RK ≥(cid:18) 1 2 − (9) RK ≥(cid:18) 1 2 − 0.90
1 2K(cid:19) T Xt=1 1 2K(cid:19)T Xt=1 0.77
EK[1Xt≤⌊K/2⌋/K ], EK[1Xt≤\K/2\/K ] 0.54
(10) because a regret no less than 1/2 − 1/2K is incurred in the periods when Xt ≤ 1/2. (10) なぜなら 1/2 − 1/2K 以下の後悔は Xt ≤ 1/2 の時期に起こるからである。 0.78
Based on the regret decomposition in (9) and (10), we introduce Tk,i for k, i ∈ [K] as 9) と (10) における後悔の分解に基づいて、k, i ∈ [K] に対して Tk,i を導入する。 0.81
Tk,i = Ek[1Xt∈[(i−1)/K,i/K)]. Tk,i = Ek[1Xt∂[(i−1)/K,i/K)]。 0.86
T Xt=1 In other words, Tk,i is the number of periods in which the policy chooses x from the interval [(i − 1)/K, i/K) when the reward sequence is generated by the objective function fk(x).2 A key observation due to Requirement 1 is that T Xt=1 言い換えると、tk,i は、目的関数 fk(x).2 によって報酬シーケンスが生成されるとき、ポリシーが区間 [(i − 1)/k, i/k) から x を選択する期間の数である。
訳抜け防止モード: T Xt=1 言い換えると、tk, i は、ポリシーが x を区間 [ (i − 1)/k, i / k ) から選択する周期の数である。 報酬の順序は目的関数によって生成される fk(x.2 要件 1 による重要な観察は
0.74
(11) This is because for k > i, the function fk(x) is identical for x ≤ i/K. (11) これは k > i に対して、函数 fk(x) は x ≤ i/K と同一であるからである。 0.82
Before reaching some t such that Xt > i/K, the policy must have spent the same number of periods on average in the interval [(i − 1)/K, i/K) no matter the objective function is fi+1(x), . Xt > i/K となるような t に達する前には、目的関数が fi+1(x) であっても、ポリシーは平均で [(i − 1)/K, i/K) の間隔で同じ期間を過ごしたに違いない。 0.75
. . , fK−1(x), or fK(x). . . fk−1(x) または fk(x) である。 0.83
But t=1 Ek[1Xt ∈[1−1/K,1]] include the right end. しかし t=1 Ek[1Xt ∈[1−1/K,1]] は右端を含む。 0.75
This is a minor technical point that doesn’t これは、そうでない小さな技術的ポイントです 0.76
Ti+1,i = Ti+2,i = ··· = TK,i. Ti+1,i = Ti+2,i = ··· = TK,i。 0.83
2We let Tk,K = PT 2 we let tk,k = pt 0.78
affect the steps of the proof. 証明の手順に影響を与えます 0.69
13 13 0.85
英語(論文から抽出)日本語訳スコア
because of Requirement 1, once Xt > i/K for some t, the policy never pulls an arm in the interval [(i − 1)/K, i/K) afterwards. 要求 1 により、ある t に対して Xt > i/K となると、ポリシーはその後[(i − 1)/K, i/K) の間隔で腕を引くことはない。 0.70
Therefore, (11) holds. したがって (11) は成り立つ。 0.75
This allows us to simplify the notation by letting Ti := Tk,i for k > i. これにより、Ti := Tk,i を k > i とし、表記を単純化することができる。 0.68
In particular, by (10), we have 特に (10) までには 0.51
RK ≥ K − 1 2K RK ≥ K − 1 2K 0.92
⌊K/2⌋ Xi=1 略称は「k/2」。 Xi=1 0.38
TK,i = K − 1 2K TK,i = K − 1 2K 0.92
⌊K/2⌋ Xi=1 略称は「k/2」。 Xi=1 0.38
Ti. (12) Next we are going to show the relationship between Tk,i (or equivalently Ti) and Ti,i for k > i. Ti。 (12) 次に、tk,i (またはti) と ti,i の関係を k > i で示す。
訳抜け防止モード: Ti。 (12) 次に、Tk, i の関係を示す。 または、Ti ) と Ti , i for k > i である。
0.78
We introduce a random variable τi 確率変数 τi を導入する 0.72
Because of Requirement 1, we have {τi ≤ t} ∈ σ(X1, Z1, X2, Z2, . 要求 1 により {τi ≤ t} ∈ σ(X1, Z1, X2, Z2, ) となる。 0.87
. . , Xt, Zt, Ut).3 Therefore, τi is a stopping time. . . , Xt, Zt, Ut)3 したがって、τi は停止時間である。 0.86
We consider the two probability measures, induced by the objective functions fi(x) and fk(x) respectively, on (X1, Z1, . 目的関数 fi(x) と fk(x) によって誘導される2つの確率測度を (X1, Z1, ) 上で考える。 0.83
. . , Xτi, Zτi, τi). . . , Xτi, Zτi, τi)。 0.80
Denote the two measures by µi,i and µk,i respectively. μi,i と μk,i の2つの測度を表す。 0.76
Therefore, we have τi := max{t|Xt < i/K} . したがって、我々は τi := max{t|Xt < i/K}。 0.80
Ti,i − Tk,i = Eµi,i" τi Xt=1 (µi,i(A) − µk,i(A)) Ti,i − Tk,i = Eμi,i" τi Xt=1 (μi,i(A) − μk,i(A)) 0.95
1Xt∈[(i−1)/K,i/K)# − Eµk,i" τi Xt=1 1xt ∈[(i−1)/k,i/k)# − eμk,i" τi xt=1 0.70
A ≤ T sup ≤ Tr 1 A ≤ T sup ≤ Tr 1 0.85
2 D(µi,i k µk,i). 2 D(μi,i k μk,i)。 0.88
the definition of the definition of... 0.47
1Xt∈[(i−1)/K,i/K)#! 1Xt・[(i−1)/K,i/K)#! 0.70
(13) (14) (13) (13) (14) (13) 0.85
Here follows that Pτi t=1 1Xt∈[(i−1)/K,i/K) ≤ T . ここ 以下 Pτi t=1 1Xt~[(i−1)/K,i/K) ≤ T である。 0.64
The second inequality (14) follows from Pinsker’s inequality (see [39] for an introduction) and D(P k Q) denotes the Kullback-Leibler divergence defined as 2番目の不等式(14)はピンスカーの不等式(導入の [39] を参照)から従い、D(P k Q) はクルバック・リーバーの発散を表す。 0.62
total variation distance and the 全変動距離 そして... 0.54
fact the We can further bound the KL-divergence in (14) by: 事実 はあ? KL-発散は (14) でさらに有界である。 0.56
D(P k Q) =Z log( D(P k Q) =Z log( 0.94
dP dQ )dP. dP dQ )dP。 0.80
D(µi,i k µk,i) = D(μi,i k μk,i) = 0.99
= = = = T T = = = = T T 0.85
T Xt=1Zτi=t Xt=1Zτi=t Xt=1Zτi=tZz1,...,zt Xt=1Zτi=tZz1,...,zt Xt=1Zτi=t T Xt=1Zτi=t Xt=1Zτi=t Xt=1Zτi=tZz1,...,zt Xt=1Zτi=tZz1,...,zt Xt=1Zτi=t 0.60
µk,i(x1, z1, . μk,i(x1, z1, 。 0.80
. . , xt, zt)(cid:19) dµi,i log(cid:18) µi,i(zs|xs) . . , xt, zt)(cid:19) dμi,i log(cid:18) μi,i(zs|xs) 0.84
log(cid:18) µi,i(x1, z1, . log(cid:18) μi,i(x1, z1, )。 0.76
. . , xt, zt) µk,i(zs|xs)(cid:19) dµi,i Xs=1 log(cid:18) µi,i(zs|xs) Xs=1 Xs=1 D(N (fi(xs), 1) k N (fk(xs), 1))dµi,i(x1, . . . , xt, zt) μk,i(zs|xs)(cid:19) dμi,i Xs=1 log(cid:18) μi,i(zs|xs) Xs=1 Xs=1 D(N (fi(xs), 1) k N (fk(xs), 1))dμi,i(x1, )。 0.86
. . , xt) (fi(xs) − fk(xs))2dµi,i(x1, . . . , xt) (fi(xs) − fk(xs))2dμi,i(x1, )。 0.87
. . , xt) µk,i(zs|xs)(cid:19) dµi,i(·|x1, . . . ,xt) μk,i(zs|xs)(cid:19) dμi,i(·|x1, 。 0.77
. . , xt)dµi,i(x1, . . . , xt)dμi,i(x1, 。 0.85
. . , xt) Xs=1 . . ,xt) Xs=1 0.74
1 2 T T t t 1 2 T T t t 0.85
t t Here the second equality follows from the fact that for the same policy π, we have µi,i(xs|x1, z1, . t t ここで第二等式は、同じポリシー π に対して μi,i(xs|x1, z1, ) が存在するという事実から従う。
訳抜け防止モード: t t 第二の平等は 同じポリシー π に対して、μi, i(xs|x1, z1,) が存在する。
0.82
. . , xs−1, zs−1) = µk,i(xs|x1, z1, . . . , xs−1, zs−1) = μk,i(xs|x1, z1, )。 0.80
. . , xs−1, zs−1). . . , xs−1, zs−1)。 0.80
Note that on the event τi = t, we have xs < i/K for s ≤ t. Therefore, we have τi = t のとき、xs < i/k が s ≤ t に対して成り立つことに注意せよ。 0.69
|fi(xs) − fk(xs)| ≤(cid:26) 1 |fi(xs) − fk(xs)| ≤(cid:26) 1 0.96
K xs ∈ [(i − 1)/K, i/K) 0 K xs ∈ [(i − 1)/K, i/K) 0 0.96
xs < (i − 1)/K xs < (i − 1)/K 0.94
, 3Recall that Ut is an internal randomizer. , 3 recall that ut is a internal randomizer. 0.83
Since we can always couple the values of Ut under the two Ut の値は常に 2 つの値で対応できるので 0.62
measures, we omit the dependence hereafter. 措置は今後、依存を省略する。 0.51
14 14 0.85
英語(論文から抽出)日本語訳スコア
by the construction of fi(x) and fk(x). fi(x) と fk(x) の構成による。 0.69
As a result, D(µi,i k µk,i) ≤ その結果である。 d(μi,i k μk,i) ≤ 0.87
T Xt=1Zτi=t T Xt=1Zτi=t 0.56
T 2 k,i 2K 2 dµi,i(x1, . T 2 k,i 2K 2 dμi,i(x1, 。 0.87
. . , xt) ≤ . . , xt) ≤ 0.85
T 2 k,i 2K 2 . T 2 k,i 2K 2。 0.83
Plugging it into (14), we have Therefore, (14) implies それを (14) に差し込むと、 (14) は 0.57
Combining (15) and (9), we can provide a lower bound for the regret Ri for i = 1, . (15) と (9) を組み合わせることで、i = 1 に対する後悔の Ri に対する下界を与えることができる。 0.80
. . ,⌊K/2⌋/K: (16) . . k/2/k: (16) である。 0.70
Ri ≥ 1 2K (T − Ti,i) ≥ Ri ≥ 1 2K (T − Ti,i)≥ 0.83
Next, based on (12) and (16), we show that for k ∈ {1, . 次に、(12) と (16) に基づいて、k ∈ {1, について表す。 0.70
. . ,⌊K/2⌋/K, K}, there exists at least one k such that . . ここで、少なくとも1つの k {\displaystyle k} が存在する。 0.82
Ti,i ≤ Tk,i + Ti,i ≤ Tk,i + 0.85
T T 2KpTk,i = Ti + 2K (cid:18)T − Ti − T T 2KpTk,i = Ti + 2K (cid:18)T − Ti − 0.88
1 2KpTi. 2KpTi(cid:19) . 1 2KpTi。 2KpTi (cid:19)。 0.79
T (15) Rk ≥ T (15) Rk ≥ 0.85
1 32 T 3/4. 1 32 T3/4。 0.78
Ti ≤ 32(K − 1)⌊K/2⌋ Ti ≤ 32(K − 1)... 0.81
2K T 3/4. If the claim doesn’t hold, then we have RK ≥ T 3/4/32. 2K T3/4。 主張が成り立たないなら、RK ≥ T 3/4/32 である。 0.74
By (12) and the pigeonhole principle, there exists at least one i such that 12)とハトホールの原理により、少なくとも1つのiが存在する。 0.64
Because T ≥ 16 and K ≥ 2, we have K/(K − 1) ≤ 2 and ⌊K/2⌋ ≥ T 1/4/4. T ≥ 16 と K ≥ 2 であるため、K/(K − 1) ≤ 2 と シュK/2 ≥ T 1/4/4 を持つ。 0.79
Therefore, Now by (16), for this particular i, we have そのため さて (16) までには、この特別な i に対して、 0.75
Ti ≤ 1 2 T 1/2. Ti ≤ 1 2 T1/2。 0.80
1 1 2 2K (cid:18)T − Ri ≥ ≥ 2T −1/4 T − ≥(cid:18) 7 4 − 1 1 2 2K (cid:18)T − Ri ≥ ≥ 2T −1/4 T − ≥ (cid:18) 7 4 − 0.84
√2(cid:19) T 3/4 ≥ 2(cid:19) T 3/4 ≥ 0.68
T 1/2 − 1 2 T 1/2 − 1 2 0.88
T 1/2 − 1 32 T 1/2 − 1 32 0.88
T 2KqT 1/2/2(cid:19) √2 2 T 2KqT 1/2/2(cid:19) =2 0.72
T! T 3/4, (17) T! T3/4 (17) 0.85
(18) resulting in a contradiction. (18) 矛盾を生じさせます 0.73
Here (17) follows from the fact that 2K ≥ T 1/4 ≥ K when T ≥ 16; (18) follows from T 1/2 ≥ 4. ここで (17) は T ≥ 16 のとき 2K ≥ T 1/4 ≥ K であるという事実から従う; () は T 1/2 ≥ 4 から従う。 0.82
Therefore, we have proved that for at least one k, Rk ≥ T 3/4/32. したがって、少なくとも1つの k に対して Rk ≥ T 3/4/32 であることが証明された。 0.61
This completes the proof. これ 証明を完了します 0.71
15 15 0.85
                               ページの最初に戻る

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