# (参考訳) arcアルゴリズムによる動的価格設定のための相関バンディット [全文訳有]

Correlated Bandits for Dynamic Pricing via the ARC algorithm ( http://arxiv.org/abs/2102.04263v1 )

ライセンス: CC BY 4.0
Samuel Cohen and Tanut Treetanthiploet(参考訳) Asymptotic Randomised Control (ARC)アルゴリズムは、合理的な計算の複雑さを維持しながら、ベイズバンドの広いクラスの最適戦略に厳密な近似を提供します。 特に、意思決定者は報酬に加えて信号を観察し、異なる選択の結果間の相関を組み込むことができ、見積もりに非自明なダイナミクスを持つことができます。 このアルゴリズムは、バンディットの初期不確実性に応じて誤差を伴って、予想される割引支払を漸近的に最適化することが保証される。 本稿では、一般化された線形モデルから観測結果が到着するバッチ帯域問題について考察し、ARCアルゴリズムをこの設定に拡張する。 これをベイズ階層モデルに基づく古典的動的価格問題に適用し、ARCアルゴリズムが代替手法よりも優れていることを示す。

The Asymptotic Randomised Control (ARC) algorithm provides a rigorous approximation to the optimal strategy for a wide class of Bayesian bandits, while retaining reasonable computational complexity. In particular, it allows a decision maker to observe signals in addition to their rewards, to incorporate correlations between the outcomes of different choices, and to have nontrivial dynamics for their estimates. The algorithm is guaranteed to asymptotically optimise the expected discounted payoff, with error depending on the initial uncertainty of the bandit. In this paper, we consider a batched bandit problem where observations arrive from a generalised linear model; we extend the ARC algorithm to this setting. We apply this to a classic dynamic pricing problem based on a Bayesian hierarchical model and demonstrate that the ARC algorithm outperforms alternative approaches.
公開日: Mon, 8 Feb 2021 14:54:26 GMT

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


    Page: /      
Correlated Bandits for Dynamic Pricing via the ARC algorithm arcアルゴリズムによる動的価格設定のための相関バンディット 0.65
Samuel N. Cohen∗ Samuel N. Cohen∗ 0.78
Tanut Treetanthiploet† Tanut Treetanthiploet 0.77
February 9, 2021 Abstract 2021年2月9日 概要 0.58
The Asymptotic Randomised Control (ARC) algorithm provides a rigorous approximation to the optimal strategy for a wide class of Bayesian bandits, while retaining reasonable computational complexity. Asymptotic Randomised Control (ARC)アルゴリズムは、合理的な計算の複雑さを維持しながら、ベイズバンドの広いクラスの最適戦略に厳密な近似を提供します。 0.84
In particular, it allows a decision maker to observe signals in addition to their rewards, to incorporate correlations between the outcomes of different choices, and to have nontrivial dynamics for their estimates. 特に、意思決定者は報酬に加えて信号を観察し、異なる選択の結果間の相関を組み込むことができ、見積もりに非自明なダイナミクスを持つことができます。 0.66
The algorithm is guaranteed to asymptotically optimise the expected discounted payoff, with error depending on the initial uncertainty of the bandit. このアルゴリズムは、バンディットの初期不確実性に応じて誤差を伴って、予想される割引支払を漸近的に最適化することが保証される。 0.60
In this paper, we consider a batched bandit problem where observations arrive from a generalised linear model; we extend the ARC algorithm to this setting. 本稿では、一般化された線形モデルから観測結果が到着するバッチ帯域問題について考察し、ARCアルゴリズムをこの設定に拡張する。 0.76
We apply this to a classic dynamic pricing problem based on a Bayesian hierarchical model and demonstrate that the ARC algorithm outperforms alternative approaches. これをベイズ階層モデルに基づく古典的動的価格問題に適用し、ARCアルゴリズムが代替手法よりも優れていることを示す。 0.84
Keywords: multi-armed bandit, parametric bandit, generalised linear model, dynamic pricing MSC2020: 62J12, 90B50, 91B38, 93C41 キーワード:マルチアームバンディット、パラメトリックバンディット、一般化線形モデル、動的価格MSC2020:62J12、90B50、91B38、93C41 0.64
1 Introduction In the multi-armed bandit problem, a decision maker needs to sequentially decide between acting to reveal data about a system and acting to generate profit. 1 はじめに マルチアームバンディット問題において、意思決定者は、システムに関するデータを明らかにする行動と利益を生み出す行動とを順次決定する必要がある。
訳抜け防止モード: 1 はじめに 複数武装バンディット問題における意思決定者の必要性 システムに関するデータを開示する行為と、利益を生み出す行為とを順次決定する。
The central idea of the multi-armed bandit is that the agent has K ‘options’ or equivalently, a bandit with K arms, and must choose which arm to play at each time. マルチアームバンディットの中心的な考え方は、エージェントがkのオプティオンまたは同等のkの腕を持つバンディットを持ち、毎回どの腕を弾くかを選択することである。 0.64
Playing an arm results in a reward generated from a fixed but unknown distribution which must be inferred ‘on-the-fly’. 腕を弾くと、固定だが未知の分布から生じる報酬が「オン・ザ・フライ」と推測される。 0.63
In the classic multi-armed bandit problem, the reward of each arm is assumed to be independent of the others (Gittins and Jones [9], Agrawal [1], Lattimore and Szepesv´ari [13]) and it is the only observation obtained by the decision maker at each step. 古典的な多腕バンディット問題では、各アームの報酬は、他のアーム (gittins and jones [9], agrawal [1], lattimore and szepesv ́ari [13]) とは独立であると仮定され、各ステップにおいて意思決定者が得る唯一の観察である。
訳抜け防止モード: 古典的な多武装バンディット問題では、各腕の報酬は他の腕(ギッティンスとジョーンズ [9])から独立していると仮定される。 Agrawal [ 1 ], Lattimore and Szepesv ́ari [ 13 ]) それぞれの段階において 意思決定者によって得られた 唯一の観察です
In practice, we often observe signals in addition to the rewards and there is often correlation between the distributions of outcomes for different choices. 実際には、報酬に加えて信号もよく観察し、異なる選択に対する結果の分布の間には相関関係がある。 0.70
For example, in a dynamic pricing problem (Dub´e and Misra [6], Misra et al. 例えば、動的価格問題 (dub ́e と misra [6], misra et al.) において。 0.80
[14]), an agent wants to fix the price of a single product, from a finite set of prices {c1, ..., cK} to maximise revenue. 14]) エージェントは、収入を最大化するために有限の価格 {c1, ..., ck} から1つの製品の価格を修正したいと考えている。 0.76
We know that when the price is high, the demand p(ck) (which we interpret as the chance that each customer will buy the product) is low, but each sale yields a higher return. 私達は価格が高いとき、要求p(ck)(私達が各顧客がプロダクトを買うチャンスと私達が解釈する)が低いことを知っていますが、各販売はより高いリターンをもたらします。 0.73
The agent’s reward on a given day is ckSk where Sk|N ∼ B(N, p(ck)) is the number of customers who buy the product and N is the number of customers on a particular day. ある日のエージェントの報酬は ckSk であり、Sk|N、B(N、p(ck)) は製品を購入する顧客の数であり、N は特定の日に顧客の数です。 0.74
On each day, the agent wishes to choose ck to maximise ckESk = ckp(ck)E(N ). 毎日、エージェントはckESk = ckp(ck)E(N )を最大化するためにckを選択することを望みます。 0.75
Unfortunately, the agent does not know the true demand p(ck), and needs to infer it over time. 残念ながら、エージェントは真の要求 p(ck) を知らないので、時間とともに推測する必要がある。 0.74
The situation above can be modeled as a multi-armed bandit problem, where each price corresponds to an arm of the bandit. 上記の状況は、各価格がバンディットの腕に対応するマルチアームのバンディット問題としてモデル化することができる。 0.67
However, this is not a classical bandit problem: First, we observe more than the reward, i.e. しかし、これは古典的なバンディットの問題ではありません。
訳抜け防止モード: しかし、これは古典的なバンディットの問題ではありません。 : まず、報酬以上のものを観察します。
we observe both the number of customers entering the shop and the number of sales, while the reward only represents the number of sales. 入店されたお客様の数と販売数の両方を観察し、報酬は販売数のみを表します。 0.67
The second difference is more fundamental, in that we know that there is some correlation between the number of sales (and thus the rewards) of different price choices. 第2の差はより根本的なものであり、異なる価格選択の売り上げ数(つまり報酬)の間に何らかの相関があることが分かっている。 0.80
For example, when the price ck increases, we expect the demand p(ck) to decrease. 例えば、価格 ck が増加すると、需要 p(ck) が減少すると予想されます。 0.81
In recent work, bandits with correlation have been considered (Filippi et al. 近年の研究では、相関関係のある包帯が検討されている(Filippi et al。 0.53
[8] and Rusmevichientong and Tsitsiklis [15]). 8] と rusmevichientong と tsitsiklis [15]) である。 0.72
However, these approaches require the distribution of the reward to follow a Generalised しかし、これらのアプローチは、一般化された報酬の分配を必要とする。 0.55
1 2 0 2 b e F 8 1 2 0 2 b e F 8 0.85
] . C O h t a m ] . C O h t a m 0.85
[ 1 v 3 6 2 4 0 [ 1 v 3 6 2 4 0 0.85
. 2 0 1 2 : v i X r a . 2 0 1 2 : v i X r a 0.85
∗ † Mathematical Institute, University of Oxford, Woodstock Rd, Oxford, OX2 6GG, UK, samuel.cohen@maths.o x.ac.uk Mathematical ∗ † オックスフォード大学数学研究所 ウッドストックRd, Oxford, OX2 6GG, UK, Samuel.cohen@maths.o x.uk Mathematical 0.84
Oxford, Woodstock オックスフォード、ウッドストック 0.60
University Institute, Oxford, 大学 研究所 オックスフォード大学 0.66
of Rd, OX2 ですから Rd。 OX2 0.66
6GG, UK, tanut.treetanthiploe t@maths.ox.ac.uk 6GG。 イギリス tanut.treetanthiploe t@maths.ox.uk 0.55
1 1 0.85
Linear Model (GLM), and the reward is the only observation. 線形モデル(GLM)と報酬は唯一の観測である。 0.72
In the case of the dynamic pricing problem described above, the numbers of customers on each day will vary and the reward is scaled with the price, making this an unnatural assumption. 上記の動的価格問題の場合、1日あたりの顧客数は様々であり、報酬は価格とともにスケールされるため、これは不自然な仮定である。 0.71
In our earlier work [5], we considered a wide class of Bayesian multi-armed bandits as a stochastic control problem (equivalently, a Markov decision problem), allowing a wide range of flexibility in modelling. 初期の研究[5]では、ベイズ的マルチアームバンディットの幅広いクラスを確率的制御問題(マルコフ決定問題と同等)とみなし、モデリングにおける幅広い柔軟性を実現した。 0.70
By applying an asymptotic expansion, together with a regularisation, this leads to the Asymptotic Randomised Control (ARC) algorithm. 漸近的拡張を正規化とともに適用することにより、漸近的ランダム化制御(ARC)アルゴリズムに繋がる。 0.79
They also showed that the ARC algorithm gives a near optimal value for the total discounted reward problem (2.1). 彼らはまた、ARCアルゴリズムが合計割引報酬問題(2.1)にほぼ最適な値を与えることも示した。 0.71
However, their implementation is limited to the case where the estimation procedure admits a simple prior-posterior conjugate pair. しかし、それらの実装は、推定手順が単純な後続共役ペアを許容する場合に限られる。 0.69
In this paper, we consider a general class of multi-armed bandit problems where the observations of each arm arrive from a parametric exponential family in batches, with a shared parameter, following a generalised linear model1. 本稿では,各アームの観測が一般化線形モデル1に従えば,共有パラメータを持つパラメトリック指数関数群からバッチで到着するマルチアームバンディット問題の一般クラスについて考察する。 0.81
We also generalise the implementation of the ARC algorithm to tackle cases without exact prior-posterior conjugacy, by applying the Kalman filter to the generalised linear model as in Fahrmeir [7]. また,fahrmeir [7] のように一般化線形モデルにカルマンフィルタを適用することで,arcアルゴリズムの実装を,正確な事前の共役を伴わないケースに一般化する。 0.74
The paper proceeds as follows. 論文は次の通り進める。 0.67
In Section 2, we formulate dynamic online pricing as a generalised linear bandit model and give a description of how we can use large sample theory and Bayesian statistics to propagate our beliefs. 第2節では、オンライン価格を一般化線形バンディットモデルとして定式化し、大規模なサンプル理論とベイズ統計を使って信念を広める方法について説明する。 0.72
We then give a brief description of bandit algorithms which may be considered as candidates for the generalised linear bandit problem and outline the implementation of the ARC algorithm in Section 3. 次に、一般化された線形バンディット問題の候補と考えられるバンディットアルゴリズムの簡単な説明を行い、第3節でARCアルゴリズムの実装について概説する。 0.79
Finally in Section 4, we use experimental data from Dub´e and Misra [6] to illustrate the performance of each bandit algorithm in observations from a generalised linear model. 最後に,Dub ́e と Misra [6] の実験データを用いて,一般化線形モデルからの観測において,各帯域アルゴリズムの性能を示す。 0.80
2 Dynamic Pricing and Generalised Linear Bandit Model 2 動的価格と一般化線形バンディットモデル 0.84
In September 2015 Dub´e and Misra [6] ran an experiment, in collaboration with the business-to-business company ZipRecruiter.com, to choose an optimal price in an online sales problem. 2015年9月、dub ́e と misra [6] はビジネスツービジネス企業の ziprecruiter.com と共同でオンライン販売問題において最適な価格を選択する実験を行った。 0.70
Their experiment ran in two stages, as an offline learning problem: first collecting data using randomly assigned prices, and then testing their optimal price. まずランダムに割り当てられた価格を使用してデータを収集し、次に最適な価格をテストします。
訳抜け防止モード: 彼らの実験はオフライン学習問題として2段階に分けて行われた。 ランダムに割り振られた価格でデータを収集し 最適な価格をテストします
Figure 1: (a): The relation between the price and the logit of Acquisition Rate. 図1: (a):価格と取得率の対価の関係 0.62
(b): The relation between the price and the expected reward per customer. (b):顧客一人当たりの価格と期待される報酬の関係。 0.73
In contrast, Misra et al. 対照的に、misraとal。 0.68
[14] used the same data to illustrate dynamic online pricing as a classical multi-armed bandit problem and tackled this problem using a modification of the classical UCB algorithm 14] 従来のマルチアームバンディット問題と同じデータを用いて動的オンライン価格を記述し, 従来の UCB アルゴリズムを改良してこの問題に対処した。 0.81
1Filippi et al. 1Filippi et al。 0.95
[8] consider the same observation sequence but they assume that the observation is the reward. [8]同じ観察シーケンスを考えても、その観察が報奨であると仮定する。 0.77
2 05010015020025030035 0400Price: c2.252.001.751.501.2 51.000.750.50logit of Acquisition Rate : log(p/(1-p))(a)05010 0150200250300350400P rice: c010203040Expected Reward: pc(b) 2 05010015020025030035 0400Price: c2.252.001.751.501.2 51.000.750.50logit of Acquisition Rate : log(p/(1-p))(a)05010 0150200250300350400P rice: c010203040Expected Reward: pc(b) 0.73
and UCB-tuned algorithm (Auer et al. と UCB-tuned algorithm (Auer et al。 0.85
[2]) where the demand correlation is not taken into consideration. [2]) 需要相関が考慮されない場合。 0.53
Figure 1(a) displays the relation between the logit of the acquisition rate (the proportion of the customers who subscribe), together with its best fit line. 図1(a)は、取得率(購読する顧客の比率)のロジットと、最適なフィットラインとの関係を示しています。 0.68
It is clear that the demands at different prices are related, which agrees with economic intuition. 異なる価格の要求が関連していることは明らかであり、これは経済的直感に同意する。 0.70
These data can be found in Table 5 of [6]. これらのデータは[6]の表5で確認できる。 0.79
The expected reward for each customer (ckp(ck)) generated by the best fit line and the observed data is illustrated in Figure 1(b). ベストフィットラインと観測データによって生成された各顧客(ckp(ck))に対する期待報酬を図1(b)に示します。 0.85
Guided by to Figure 1, it is reasonable to consider a logistic model for the probability of subscription; the reward, however, does not fit as naturally into a GLM framework. 図1に示すように、サブスクリプションの確率のためのロジスティックモデルを考慮することは合理的です。しかし、報酬はGLMフレームワークに自然に収まりません。 0.68
Given this model, the next question is how to use this model to sequentially choose prices. このモデルを考えると、次の質問は、このモデルを使って価格を順次選択する方法である。 0.68
This requires us to combine the multi-armed bandit problem with generalised linear regression. これにより、多重武装バンディット問題を一般化線形回帰と組み合わせる必要がある。 0.65
2.1 Multi-armed bandit problem 2.1 マルチアームバンディット問題 0.58
We now give a formal specification of our multi-armed bandit problem: Suppose that at each time t, we need to choose one of the K arms. 我々は今、私たちのマルチアームのバンディット問題の正式な仕様を与える:毎回tで、私たちはKアームの1つを選択する必要があると仮定してください。
訳抜け防止モード: 私たちは今、マルチ武装バンディット問題の正式な仕様を与えます。 t のたびに、K の腕の 1 つを選択する必要があると仮定します。
After choosing the kth arm at time t, we observe a random variable Y (k) k 番目の腕を時間 t で選択した後、ランダム変数 Y (k) を観測する。 0.73
whose distribution varies with k and collect a reward R(k)(cid:0)Y (k) その分布はkと異なり、報酬 r(k)(cid:0)y(k) を集める 0.82
(cid:1). The collection of previous observations (cid:1)。 過去の観測の収集 0.74
t t t t t are used as historical data on which to base our next decision, and the problem repeats. t t t t t 次の決定を下すための 歴史的データとして使われます 問題が繰り返されます 0.83
), Θ). The random variable Y (k) ), Θ). ランダム変数 Y (k) 0.69
To provide a mathematical framework, let (Ω, P,F) be a probability space equipped with a random )t∈N,k=1,2,..,K and a sequence (ζt)t∈N with ζt ∼IID U [0, 1] variable Θ, a family of random variables (Y (k) independent of ((Y (k) is interpreted as the observation when the kth arm is chosen at time t, the process (ζt) is used to allow random decisions, and Θ is a hidden parameter specifying the distribution of all (Y (k) )t∈N are conditionally independent for each t given Θ. 数学的な枠組みにおいて、(Ω, P, F) を確率空間とし、(Ω, P, F) をランダム )t(k=1,2, K) と、(Y(k)) と独立な確率変数の族、(Y(k)) を時間 t で選択したときの観測として解釈し、(Y(k) ) t(N) を任意の t に対して条件的に独立する列(t)t(N) と、(Y(k) ) ) t(N) の分布を指定する隠されたパラメータとする。 0.78
At time t, we need to choose an action At taking values in {1, .., K}. 時間 t において、{1, .., k} の値を取るアクションを選択する必要がある。 0.70
We can incorporate additional i=1 ui = 1} where the kth component of Ut represents the (conditional) probability that we choose the kth arm. 追加の i=1 ui = 1} を組み込むことができ、ここで Ut の kth 成分は kth アームを選択する (条件付き) 確率を表す。 0.74
The corresponding actions and filtrations (representing historical observations) can be given by At = A(Ut, ζt) 対応する行動と濾過(歴史的観察を表わす)は、at = a(ut, ]t) で与えられる。 0.66
randomisation by instead choosing a sequence (Ut) taking values in ∆K := {u ∈ [0, 1]K : (cid:80)K where A(u, ζ) := sup(cid:8)i :(cid:80)i K := {u ∈ [0, 1]K : (cid:80)K : (cid:80)K := sup(cid:8)i :(cid:80)i で値を取るシーケンス(Ut)を選択する代わりにランダム化 0.88
) in a Bayesian manner. ) ベイジアン的な方法で。 0.59
We assume (for simplicity) that (Y (1) 単純化のために) (Y (1) 0.61
k=1 uk ≥ ζ(cid:9) and F U k=1 uk(cid:9)とF U 0.95
The random variable Ut+1 must be chosen based on information at time t, that is, U is (F U ランダム変数 Ut+1 は、時間 t、すなわち U が (F U) の情報に基づいて選択されなければならない。 0.78
t )t≥0predictable. t )t≥0 予測可能。 0.51
We emphasise that, for any strategy (Ut), the parameter Θ is not generally F U t -measurable for any t ≥ 0, that is, it is impossible to completely resolve our uncertainty over the distribution of outcomes. 任意の戦略 (Ut) に対して、パラメータ t は一般に F U t -測定可能ではなく、すなわち結果の分布に関する不確実性を完全に解決することは不可能である、と強調する。 0.77
The objective of the multi-armed bandit is to choose a strategy U to optimise some objective. マルチアームバンディットの目的は、ある目的を最適化する戦略uを選択することである。 0.69
This := σ(cid:0)ζ1, Y (A1) これ := σ(cid:0)>1, y(a1) 0.78
, ..., ζt, Y (At) , ..., , t, Y (アット) 0.80
, ..., Y (K) (cid:1). 、...、Y(K) (cid:1)。 0.79
1 t t t t t 1 t t t t t 0.85
objective varies in the literature. 目的は文学によって異なります 0.71
One common objective is to minimise the cumulative (frequentist) regret (e.g. 共通の目的の1つは累積的(繰り返し的)後悔を最小化することである(例えば)。 0.53
Agrawal [1], Auer et al. Agrawal [1], Auer et al。 0.73
[2], Kaufmann et al. [2],kaufmannら。 0.47
[10], Lai and Robbins [12]) [10], Lai and Robbins [12]) 0.71
where A∗ = arg maxk ここで A∗ = arg maxk 0.73
E(cid:104) E(cid:104) 0.84
R(cid:0)Θ, T, (Ut)(cid:1) (cid:18) E(cid:104) T(cid:88) R(A∗)(cid:0)Y (A∗) (cid:1)(cid:12)(cid: 12)(cid:12)Θ (cid:105) R(k)(cid:0)Y (k) r(cid:0)θ, t, (ut)(cid:18) e(cid:104) t(cid:88) r(a∗)(cid:0)y (a∗) (cid:1)(cid:12)(cid: 12)θ (cid:105) r(k)(cid:0)y (k) 0.92
:= t=1 . t := t=1 . t 0.78
t where π is a prior belief for the parameter Θ. t ここで π はパラメータ θ の事前の信念である。 0.83
r(π, T, (Ut)) := Eπ r(π, T, (Ut)) := Eπ 0.91
al. [20], Cohen and Treetanthiploet [5]); アル [20], Cohen and Treetanthiploet [5]) 0.47
V(cid:0)π, β, (Ut)(cid:1) := Eπ V(cid:0)π, β, (Ut)(cid:1) := Eπ 0.92
for a given discount rate β ∈ (0, 1). 与えられた割引率 β ∈ (0, 1) に対して。 0.79
(cid:1)(cid:12)(cid: 12)(cid:12)Θ (cid:1)(cid:12)(cid: 12)(cid:12) 0.76
(cid:105) − E(cid:104) (cid:105)-E(cid:104) 0.83
R(At)(cid:0)Y (At) R(At)(cid:0)Y(At) 0.99
t (cid:105)(cid:19) (cid:1)(cid:12)(cid: 12)(cid:12)Θ t (cid:105)(cid:19) (cid:1)(cid:12)(cid: 12)(cid:12)θ 0.79
. (cid:2)R(cid:0)Θ, T, (Ut)(cid:1)(cid:3), . (cid:2)R(cid:0) , T, (Ut)(cid:1) (cid:3) 0.88
(cid:34) ∞(cid:88) (cid:34) ∞(cid:88) 0.78
βt−1R(At)(cid:16) βt−1R(At)(cid:16) 0.67
(cid:17)(cid:35) (cid:17)(cid:35) 0.75
Y (At) t t=1 Y (At) t t=1 0.72
3 One may also minimise Bayesian regret (Russo and Roy [17, 18]); 3 また、ベイズ的後悔を最小化することができる(Russo and Roy [17, 18])。 0.79
An alternative objective is to maximise the total discounted reward (Gittins and Jones [9] Ryzhov et 別の目的は、総割引報酬を最大化することである (gittins and jones [9] ryzhov et. 0.78
(2.1) (2.1) 0.78
2.2 Generalised Linear Bandit Model 2.2 一般化線形バンディットモデル 0.70
In this section, we will focus on our dynamic pricing problem, where observations are sampled from an exponential family whose parameter depends on our decision. この節では、我々の決定にパラメータが依存する指数関数的な族から観察をサンプリングする動的価格問題に焦点を当てます。 0.79
At the beginning of each day, we need to choose a price from the set {c1, ..., cK}. 一日の始めに、集合 {c1, ..., cK} から価格を選択する必要がある。
訳抜け防止モード: 一日の始めに、私たちは必要です。 セット {c1, ..., cK } から価格を選択する。
On day t, with chosen price ck, we observe N (k) customers arriving at the store. 当日は、選択した価格ckで、店舗に到着するN(k)の顧客を観察します。 0.78
In order to capture the relations between demands at different prices, we suppose that the probability that each customer buys the product can be modeled by a logistic model, i.e. 需要間の関係を異なる価格で捉えるためには、各顧客が製品を購入する確率をロジスティックモデル、すなわちモデル化することができると仮定する。 0.77
the relation between the demand p(ck) and the price ck is given by 要求 p(ck) と価格 ck の関係は 0.52
logit(cid:0)p(ck)(ci d:1) = Γ0 + Γck = (Γ0, Γ)(cid:62)(1, ck) =: Θ(cid:62)x(k) (cid:1). logit(cid:0)p(ck)(ci d:1) = s0 + sck = (s0, s)(cid:62)(1, ck) =: s(cid:62)x(k) (cid:1)。 0.89
The parameter Θ = (Γ0, Γ) is unknown. パラメータ θ = (γ0, γ) は未知である。 0.76
At the end of day t, we observe 一日の終わりに、私たちは観察します。 0.63
t i,t takes values in {0, 1} and indicates whether the product is t i,t は {0, 1} で値を取り、その積が正しいかどうかを示す 0.79
t t i,t 1−p t t 私は... 1−p 0.67
Y (k) t i=1,...,N (k) Y (k) t i=1,...,N(k) 0.85
:=(cid:0)N (k) :=(cid:0)N(k) 0.97
(cid:1), where Q(k) (cid:1), ここで Q(k) 0.89
where logit(p) = log(cid:0) p ,(cid:8)Q(k) (cid:9) bought by the ith customer, and collect a reward R(k)(cid:0)Y (k) ここで logit(p) = log(cid:0) p ,(cid:8)Q(k) (cid:9) は ith 顧客が購入し、報酬 R(k)(cid:0)Y (k) 0.90
(cid:1) = ck (cid:80)N (k) independent random variables(cid:0)Q(k) (cid:1)Nt (cid:12)(cid:12)(cid :12)Θ ∼IID h(q) exp Φ(k)q − G(cid:0)Φ(k)(cid:1)(cid:17) (cid:16) Φ(k) = φ(cid:0)Θ(cid:62)x(k)(cid:1) and Q(k) we will assume that for each fixed k, the processes (cid:0)N (k) (cid:1)∞ (cid:1). (cid:1) = ck (cid:80)n (k) 独立確率変数(cid:0)q(k) (cid:1)nt (cid:12)(cid:12)(cid :12)θ(iid h(q) exp φ(k)q − g(cid:0) φ(k)(cid:1)(cid:17) (cid:16) φ(k) = φ(cid:0)θ(cid:62)x(k)(cid:1) および q(k) それぞれの固定 k に対して、プロセス (cid:0)n (k) (cid:1)∞ (cid:1) を仮定する。 0.86
, we obtain a reward R(k)(cid:0)N (k) は、報酬R(k)(cid:0)N(k)を取得します。 0.70
is independent of N (k) N (k) とは独立である 0.87
observing Q(k) Q(k) i,t Q(k)を観察する Q(k) i,t 0.80
i,t and N (k) i,t と N (k) 0.84
i,t i,t 私は... 私は... 0.39
, t t t t More generally, we can fit the dynamic pricing problem into the GLM framework. , t t t t より一般的には、動的価格問題をGLMフレームワークに適合させることができる。 0.82
Let {x(1), ..., x(K)} ⊆ Rl be a collection of features to be chosen by the agent, each corresponding to a choice {1, ..., K}, and let Θ be a random variable taking values in Rl representing an unknown parameter. x(1), ..., x(k)} をエージェントが選択する特徴の集合とし、それぞれが選択する {1, ..., k} に対応し、θ を未知のパラメータを表す rl 内の値を取る確率変数とする。 0.65
After choosing x(k) at time t, the agent observes N (k) t で x(k) を選択した後、エージェントは N (k) を観察する。 0.79
i=1 where i=1 Q(k) i,t . i=1 i=1 Q(k) i,t。 0.80
t . Here, h, φ and G are known functions. t . ここで、h, φ, G は既知函数である。 0.82
For simplicity, t=1 are IID with known distribution2. 単純な場合、t=1 は既知の分布を持つ IID である。 0.57
After 1,t , ..., Q(k) N (k) 後 1,t , ..., Q(k) N (k) 0.78
t , Q(k) ,t t, Q(k) t.t. 0.64
t t (2.2) Remark 1. t t (2.2) 備考1。 0.74
A straightforward extension is to allow the observation Q to be such that T (Q) belongs to an exponential family for some function T in an arbitrary dimension. 直接的な拡張は、観測 Q を T (Q) が任意の次元の関数 T に対して指数族に属するようにすることである。 0.80
This follows the same analysis and will allow us to use the same model to consider e.g. これは同じ分析に従っており、例えば同じモデルを使って検討することができます。 0.78
pricing for multiple products. 2.2.1 Approximate posterior update 複数の製品の価格。 2.2.1 近似更新 0.75
In order to implement a multi-armed bandit algorithm, we need an efficient way to update our estimate of the parameter Θ, together with its precision. マルチアームのバンディットアルゴリズムを実装するには、パラメータの推定を精度とともに更新する効率的な方法が必要です。 0.71
As our observations are obtained in batches, we shall use a large sample approximation to update via a normal-normal conjugate model. 我々の観測はバッチで得られるので、通常の共役モデルを用いて大きなサンプル近似を用いて更新する。 0.81
From (2.2), the mean and variance of Q given parameter Θ = θ are (2.2) から、与えられたパラメータ θ = θ の平均と分散は、 0.73
(cid:0)Q(k) (cid:0)Q(k) 0.94
i,t (cid:1) = G(cid:48)(cid:0)φ(k)(cid:1) and Varθ 私は... (cid:1) = G(cid:48)(cid:0)φ(k)(cid:1)およびVarθ 0.60
(cid:0)Q(k) (cid:0)Q(k) 0.94
i,t (cid:1) = G(cid:48)(cid:48)(ci d:0)φ(k)(cid:1). 私は... (cid:1) = g(cid:48)(cid:0) φ(k)(cid:1)。 0.65
Eθ where φ(k) = φ(θ(cid:62)x(k)). Eθ ここで φ(k) = φ(\(cid:62)x(k)) である。 0.82
Suppose that the link function φ is invertible and differentiable. リンク関数φが可逆かつ微分可能であると仮定する。 0.77
If our model is non-degenerate, G(cid:48) must also be invertible. モデルが非退化の場合、G(cid:48)も可逆でなければなりません。 0.61
We define ψ := (G(cid:48) ◦ φ)−1. ψ := (g(cid:48) , φ)−1 と定義する。 0.79
It then follows from the Central Limit Theorem and the Delta method that 次に、Central Limit Theorem と Delta メソッドから続きます。 0.71
(cid:16) (cid:17) 0, 1/[G(cid:48)(cid:48)(ci d:0)φ(k)(cid:1)φ(cid:48)(θ(cid:62)x(k))2] (cid:0)Ψn − θ(cid:62)x(k)(cid:1) d−−→ N (0, 1), (cid:16) (cid:17) 0, 1/[G(cid:48)(cid:48)(ci d:0)φ(k)(cid:1φ(cid:48)(\(cid:62)x( k))2] (cid:0)\n − s(cid:62)x(k)(cid:1) d−−→ N(0,1) 0.83
(2.3) nVn √ (2.3) nVn √ 0.83
, . Moreover, by Slutsky’s lemma, , . さらに、Slutskyの補題によって。 0.79
(cid:17) where Vn := V (Ψn) := G(cid:48)(cid:48)(φ(Ψn))(cid:0)φ(cid:48)(Ψn)(cid:1)2 (cid:17) ここでvn := v (ψn) := g(cid:48)(cid:48)(φ(ψn))(cid:0) φ(cid:48)(ψn)(cid:1)2 0.81
as n → ∞, where Ψn = ψ n → ∞ とすると、ψn = ψ である。 0.72
i,t √ n(cid:0)Ψn − θ(cid:62)x(k)(cid:1) d−−→ N (cid:16) 1 (cid:80)n (cid:80)n (cid:80)n 私は... √ n(cid:0) =n − θ(cid:62)x(k)(cid:1) d−− − N (cid:16) 1 (cid:80)n (cid:80)n (cid:80)n 0.67
i=1 Q(k) i=1 Q(k) i=1 Q(k) i=1 Q(k) 0.88
n . i=1 Q(k) n . i=1 Q(k) 0.86
When n is not large, ψ( 1 n n が大まかでないとき、s(1 n) 0.77
the logistic model when 1 n 1nがロジスティックなモデルで 0.76
i,t ) may not be well-defined for some values of Q. i,t ) は Q のいくつかの値についてよく定義されないかもしれない。 0.60
This is the case for i,t ∈ {0, 1}. これは i,t ∈ {0, 1} の場合である。 0.81
In order to avoid this degeneracy, if Mt−1 is our running この退化を避けるために、Mount−1 が実行中である場合 0.58
2In fact, one may allow that the distribution of (N (k) 2 事実、 (N (k)) の分布を許すことができる。 0.81
follow through with an extra posterior update step for the parameter of (N (k) simplify our discussion. N (k) のパラメータの余分な後続更新ステップを通して、議論を単純化します。 0.77
t t )∞ t=1 is not known. t t )∞ t=1 は知られていない。 0.79
In this case, all of our approximation arguments ). この場合、すべての近似引数 )。 0.52
We will leave this to the reader in order to 我々はこれを読者に任せておこう。 0.55
4 4 0.85
estimate of θ, we consider a linear expansion of ψ around ψ−1(M(cid:62) value of Q(k) observations, as in (2.4). θ を推定すると、(2.4) のように、Q(k) の観測の y−1(M(cid:62) 値の線型展開を考える。 0.79
t−1x(k)), which approximates the expected i,t . t−1x(k)) は期待される i,t に近似する。 0.72
This approach was used by Fahrmeir [7] to derive an extended Kalman filter with GLM このアプローチはFahrmeir [7] によって GLM による拡張カルマンフィルタの導出に使用された。 0.78
Suppose that the posterior of Θ at time t − 1 is t − 1 のとき t の後方が成り立つと仮定する。 0.72
Then, after observing(cid:8)Q(k) その後、観察後(cid:8)Q(k) 0.83
i,t equations 私は... equations 0.62
(cid:9) , the posterior can be approximately updated by the Kalman filter (cid:9) 後部はカルマンフィルタでほぼ更新できます。 0.67
Θ|F U θ|f u である。 0.28
t−1 ∼ N (Mt−1, Σt−1). t−1 は N (Mt−1, Σt−1) である。 0.55
t i=1,...,N (k) t i=1,...,N(k) 0.85
Mt = Σt Σ−1 t−1Mt−1 + S(k) mt = σt Σ−1 t−1Mt−1 + S(k) 0.72
(cid:16) t−1x(k) +(cid:0)P (k) (cid:16) t−1x(k) +(cid:0)P(k) 0.81
(cid:16) Σ−1 t−1 + S(k) Σt = t = M(cid:62) Ψ(k) t−1 := ψ−1(M(cid:62) (cid:16) s−1 t−1 + S(k) t = M(cid:62) t−1 := t−1(M(cid:62) 0.89
t x(k)(cid:17) (cid:0)x(k)(cid:1)(c id:0)x(k)(cid:1)(cid :62)(cid:17)−1 (cid:1)ψ(cid:48)(cid:0) ˆP (k) :=(cid:80)N (k) t x(k)(cid:17) (cid:0)x(k)(cid:1)(c id:0)x(k)(cid:1)(cid :62)(cid:17)−1(cid:1)\(cid:48)(ci d:0) ×P(k) :=(cid:80)N(k) 0.86
t − ˆP (k) t−1 t−1x(k)), and P (k) t − tP(k) t−1 t−1x(k)) および P(k) 0.94
t Ψ(k) t−1 t ψ(k) t−1 0.72
, , t (cid:16) , , t (cid:16) 0.83
t − M(cid:62) Ψ(k) t − M(cid:62) ^ (k) 0.97
t t−1x(k)(cid:17) (cid:0)x(k)(cid:1)(c id:0)x(k)(cid:1)(cid :62) t t−1x(k)(cid:17)(cid:0) x(k)(cid:1)(cid:0)x( k)(cid:62) 0.86
Σt−1 Σt−1,  Σt−1 Σt−1  0.65
(cid:1),  (cid:0)x(k)(cid:1), (cid:1), (cid:0)x(k)(cid:1), 0.99
. (2.4) (2.5) . (2.4) (2.5) 0.81
where S(k) t ここで S(k) t 0.85
:= N (k) t V (Ψ(k) :=N(k) t V (複数形 t Vs) 0.79
t ), ˆP (k) t P (k) である。 0.79
By using the Woodbury identity, (2.4) simplifies to Woodbury IDを使用することで (2.4) は単純化される 0.63
i=1 Q(k) i,t /N (k) i=1 Q(k) i,t /N (k) 0.92
t t where R(k) t t ここで R(k) 0.85
t = S(k) t t = S(k) t 0.85
(cid:46)(cid:16) (cid:46)(cid:16) 0.75
Mt = Mt−1 + R(k) Σt = Σt−1 − R(k) Mt = Mt−1 + R(k) Σt = Σt−1 − R(k) 0.87
t t Σt−1 (cid:17) t t Σt−1 (cid:17) 0.74
S(k) t (x(k))(cid:62)Σt−1 (x(k)) + 1 S(k) t (x(k))(cid:62)Σt−1(x(k)) + 1 0.89
. 3 Multi-armed bandit algorithms . 3 マルチアームバンディットアルゴリズム 0.81
In this There are a number of approaches commonly used to solve the multi-armed bandit problem. ここでは、多武装バンディット問題を解決するのによく使われるアプローチがいくつかある。 0.63
section, we present a few approaches which can be adapted for application to the multi-armed bandit with generalised linear observation. 本稿では, 一般化された線形観測により, マルチアームバンディットに適用可能ないくつかのアプローチを提案する。 0.67
We will implement these using the approximate posterior Θ|F U t ∼ N (Mt, Σt), where (Mt, Σt) is given by (2.5). これらを(Mt, t) を (2.5) で与えられる近似後位 ^|F U t t N (Mt, t) を用いて実装する。 0.74
3.1 A selection of multi-armed bandit algorithms 3.1 マルチアームバンディットアルゴリズムの選択 0.77
• -Greedy (Vermorel and Mohri [22]): With probability 1− , we choose an arm based on its maximal •-Greedy (Vermorel and Mohri [22]): 確率 1− の場合には、その最大値に基づいて腕を選択する。 0.84
expected reward and with probability , we choose an arm uniformly at random. 期待された報酬と確率で、私たちはランダムに腕を一様に選ぶ。 0.65
• Explore-then-commit (ETC) (Rusmevichientong and Tsitsiklis [15]): Let  ∈ (0, 1). •Explore-then-commit (ETC) (Rusmevichientong and Tsitsiklis [15]): \ ∈ (0, 1) とする。 0.88
We choose an arm uniformly at random in the first (cid:98)T(cid:99) trials and then choose an arm which maximises the estimated expected reward for each remaining trial. 最初の試験(cid:98)でランダムに腕を選択し(cid:99)、残りの試験ごとに予想される報酬を最大化するアームを選択します。 0.71
• Thompson Sampling (TS) (Thompson [21], Russo et al. • Thompson Sampling (TS) (Thompson [21], Russo et al。 0.78
[19])3: We select according to the posterior probability that each arm is ‘best’. 19])3:各アームが「ベスト」である可能性に応じて選択します。 0.64
In particular, we choose a randomised strategy Ut such that 特に ランダム化された戦略 ut を選択して 0.77
where A∗ := arg maxi∈A E(cid:0)R(k)(Y (k))(cid:12)(cid:12) Θ(cid:1). ここで A は := arg maxi∈A E(cid:0)R(k)(Y(k))(c id:12)(cid:12)\(cid: 1) である。 0.78
t = P(AT S U T S t = P(AT S U T S) 0.86
t = i|F U t−1) = P(A∗ = i|F U t = i|F U t−1) = P(A∗ = i|F U 0.81
t−1) This algorithm can be implemented by sampling ˆΘt at time t from its posterior distribution (i.e. t−1) このアルゴリズムは、その後分布(すなわち)から t を時間 t でサンプリングすることによって実装することができる。 0.68
conditional on F U t−1). F U 上の条件 t−1)。 0.78
We can then choose AT S その後、AT Sを選択できます。 0.56
t = arg maxi∈A E(cid:0)R(k)(Y (k))(cid:12)(cid:12) Θ = ˆΘt t = arg maxi∈A E(cid:0)R(k)(Y(k))(c id:12)(cid:12) 0.96
(cid:1). 3One may also see our parameter update (2.5) as the Laplace approximation method for Thompson Sampling (see [19, (cid:1)。 3パラメータ更新 (2.5) を Thompson Sampling の Laplace 近似方法として見ることもできます ([19] 参照)。 0.79
Chapter 5]) 5 第5章) 5 0.82
• Bayesian Upper Confidence Bound (Bayes-UCB) (Kaufmann et al. • bayesian upper confidence bound (bayes-ucb) (kaufmann et al.)。 0.68
[10], Filippi [8]) 4: This [10], Filippi [8]) 4:これ 0.70
is an optimistic strategy to choose the arm based on an upper bound of the reward. 報酬の上限に基づいて腕を選択する楽観的な戦略です。 0.60
ABayes−U CB ABayes-U CB 0.62
t = arg max t =arg max 0.79
i Q p, R(k)(Y (k) 私は Q p, R(k)(Y(k)) 0.76
t ) t−1 , (cid:16) t ) t−1 , (cid:16) 0.78
(cid:12)(cid:12)(cid :12)F U (cid:12)(cid:12)(cid :12)F U 0.78
(cid:17) where Q(p, X) is the p-quantile of X. (cid:17) ここで Q(p, X) は X の p-量子である。 0.79
(independence) Bernoulli bandit when p = 1 − 1/(cid:0)t(log(T ))c(cid:1) and c ≥ 5; their simulations suggest (独立)Bernoulli bandit when p = 1 − 1/(cid:0)t(log(T ))c(cid:1)およびc × 5;それらのシミュレーションは示唆している。
訳抜け防止モード: (独立 ) Bernoulli bandit if p = 1 − 1/(cid:0)t(log(T ) ) c(cid:1 ) c ≥ 5 である。 シミュレーションでは
[10] prove a theoretical guarantee of optimal order for the classical [10]古典の最適順序の理論的保証を証明する 0.80
Remark 2. Kaufmann et al. 備考2。 カウフマンとアル。 0.47
that c = 0 performs well in practice. c = 0 が実際にうまく機能すること。 0.81
We will use these values to implement the Bayes-UCB in our simulations. シミュレーションではこれらの値を用いてベイズUCBを実装します。 0.73
• Knowledge Gradient (KG) (Ryzhov et al. •知識グラデーション(KG)(Ryzhov et al。 0.73
[20]): At each time, we pretend that we will only update our posterior once, immediately after the current trial. [20]): 毎回、我々は、現在の裁判の直後に、一度だけ私たちの後部を更新するふりをします。 0.73
This simplifies the objective function (2.1) and suggests the choice これは目的関数(2.1)を単純化し、選択を提案する 0.73
t+1 = E(cid:104) t+1 = E(cid:104) 0.75
where ˜V (k) V (複数形 Vs) 0.59
AKG maxj R(j)(cid:0)Y (j) AKG maxj R(j)(cid:0)Y (j) 0.92
t+1 k (cid:1)(cid:12)(cid: 12)(cid:12)F U t+1 k (cid:1)(cid:12)(cid: 12)(cid:12)F U 0.74
t = arg max t = arg max 0.85
t , At = k t , At = k 0.85
. E(cid:104) . E(cid:104) 0.85
R(k)(cid:0)Y (k) (cid:105) R(k)(cid:0)Y(k)(cid: 105) 0.91
t (cid:16) β t (cid:16)β 0.83
(cid:1) + 1 − β (cid:1) + 1 − β 0.85
(cid:17) ˜V (k) (cid:17)v(k) 0.90
t+1 (cid:12)(cid:12)(cid :12)F U t+1 (cid:12)(cid:12)(cid :12)F U 0.69
t (cid:105) t (cid:105) 0.82
, The expectation can be computed using an appropriate quadrature or Monte Carlo approach if it is not available explicitly. , 期待は、明示的に利用できない場合、適切な二次数やモンテカルロ法を用いて計算することができる。
訳抜け防止モード: , 期待は計算できる もしそれが明示的に利用できないなら、適切な二次あるいはモンテカルロのアプローチを用いる。
• Information-Directed Sampling (IDS) (Russo and Roy [18], Kirschner and Krause [11]): This algorithm chooses based on the information ratio between the single-step regret and the information gain. • Information-Directed Sampling (IDS) (Russo and Roy [18], Kirschner and Krause [11]): このアルゴリズムは、単一ステップの後悔と情報獲得の間の情報比に基づいて選択される。 0.89
We define ukE(cid:16) where A∗ := arg maxk∈A E(cid:0)R(k)(Y (k))(cid:12)(cid:12) Θ(cid:1). 定義します ukE(cid:16) ここで、A∗ := arg maxk∂A E(cid:0)R(k)(Y)(k))( cid:12)(cid:12)*(cid :1)。 0.73
mation gain when the kth arm is chosen. k番目の腕が選ばれたとき メーションゲイン。 0.58
Define Gt(u) :=(cid:80)K Gt(u) :=(cid:80)K を定義する 0.80
t )-adapted process taking values in RK t ) RK で値を取るプロセス 0.79
Let H be an (F U H を (F U) とする 0.78
R(A∗)(Y (A∗) R(A)(Y(A)) 0.80
(cid:88) ∆t(u) := (cid:88) ~t(u) := 0.68
k∈A t ) − R(k)(cid:0)Y (k) k∈A t ) − R(k)(cid:0)Y(k) 0.80
t k=1 ukH (k) t k=1 ukH (k) 0.87
t . (cid:1)(cid:12)(cid: 12)(cid:12)Ft−1 t . (cid:1)(cid:12)(cid: 12)(cid:12)Ft−1 0.80
(cid:17) + whose kth component represents the infor- (cid:17) + の kth 成分が infor- 0.75
(cid:16) δt(u)2 (cid:16) δt(u)2 0.88
gt(u) (cid:17) gt(u) (cid:17) 0.82
. The IDS algorithm chooses an arm randomly according to the probabilities U IDS . IDSアルゴリズムは、確率U IDSに応じて腕をランダムに選択する 0.86
t = arg minu∈∆K t arg minu∈K です。 0.68
In Russo and Roy [18], H (k) posterior when the kth arm is chosen at time t. However, computing this H (k) in our simulation, we will consider Russo and Roy [18], H (k)after when the kth arm is chosen at time t. but this H (k) in our Simulation, we consider, we consider the H (k) when the kth arm is selected at time t. 0.74
is defined to be the improvement in the Shannon entropy of A∗’s is expensive. アシュのシャノンエントロピーの改善は高価であると定義されています。 0.60
Thus, t t t = E(cid:16)H(Θt−1) − H(Θt) よって、 t t t = E(cid:16)H(シュト−1) − H(シュト) 0.80
H (k) (cid:12)(cid:12)(cid :12)Ft−1, At = k H (k) (cid:12)(cid:12)(cid :12)Ft−1, At = k 0.81
(cid:17) where H(Θt) is the Shannon entropy of the posterior distribution of Θ at time t. This information gain is considered in Kirschner and Krause [11]. (cid:17) H(t) は t における t の後方分布のシャノンエントロピーである。この情報ゲインは、Kirschner と Krause [11] において考慮される。 0.78
• Asymptotic Randomised Control (ARC) [5]: We choose an arm to maximise the asymptotic •無症状ランダム化制御(ARC) [5]:我々は無症状を最大化する腕を選択する 0.74
value of our decision. We will summarise the required calculation in Section 3.2 我々の決定の価値だ 必要な計算を第3.2節にまとめます。 0.68
In our simulation, we will also consider the classical UCB and the UCB-tuned algorithm (Auer et al. シミュレーションでは,古典的 UCB と UCB 調整アルゴリズム (Auer et al) についても検討する。 0.81
[2]) as candidates, as considered in Misra et al. [2])はMisra et alで考慮された候補である。 0.71
[14]. These algorithms are similar to the Bayes-UCB algorithm but consider the problem from a frequentist perspective and ignore the correlation between outcomes. [14]. これらのアルゴリズムはベイズUCBアルゴリズムに似ているが、頻繁な観点から問題を考慮し、結果間の相関を無視する。 0.69
In particular, we do not use (2.5) to propagate our belief but we record the reward of each arm separately. 特に、信仰を広めるために(2.5)を使うのではなく、各腕の報酬を別々に記録する。 0.66
The reader may refer to Misra et al. 読者はMisra et alを参照することができます。 0.58
[14] or a survey by Burtini et al. ブルティーニらによる[14]または調査。 0.60
[3]. 4Filippi [8] consider the UCB algorithm with correlation under frequentist perspective where an additional rescaling on the bandwidth appears due to the presence of the link function. [3]. 4Filippi [8] は、リンク関数の存在により帯域幅に余分な再スケーリングが現れる、頻繁な視点で相関を持つ UCB アルゴリズムを考察する。 0.73
Nonetheless, their formulation only restricts to the case where the reward is the only observation. それにもかかわらず、それらの処方は、報酬が唯一の観察である場合にのみ制限されます。 0.58
6 6 0.85
3.2 Implementation of the ARC algorithm 3.2 ARCアルゴリズムの実装 0.91
The key idea of the ARC algorithm is to give an estimate of the optimal solution to (2.1) via a Markov decision process with (m, Σ) as an underlying state. ARCアルゴリズムの鍵となる考え方は、(m, Σ)を基底状態とするマルコフ決定過程を通じて(2.1)への最適解を推定することである。 0.88
A smooth approximation is obtained by introducing a preference for random decisions in the objective function (2.1), in particular adding a reward λH(At) to R(At) in (2.1), where H is a smooth entropy function (e.g. 目的関数 (2.1) においてランダム決定の選好を導入し、特に(2.1) において R(At) に報酬 λH(At) を付加することにより、滑らかな近似が得られる。 0.74
Shannon entropy, which we use here). shannon entropy (ここで使うシャノンエントロピー)。 0.68
The scale of this preference is controlled through the parameter λ, which is determined dynamically in order to have a negligible effect when uncertainty is low. この設定のスケールはパラメータλによって制御され、不確実性が低い場合に無視可能な効果を得るために動的に決定される。 0.78
This approximation results in a semi-index strategy which amounts to computing the solution a ∈ RK to the fixed point equation5: この近似は、定点方程式に対する ∈ RK の解の計算に等しい半インデックス戦略をもたらす5。 0.74
where the term f = (cid:2)E(cid:0)R(k)( Y (k))(cid:12)(cid:12) F U f = (cid:2)E(cid:0)R(k)( Y (k))(cid:12)(cid:12) F U 0.91
(cid:1)(cid:3) (cid:1)(cid:3) 0.75
(cid:16) β 1 − β (cid:16)β 1 − β 0.83
(cid:17) a = f + (cid:17) a = f + 0.82
Lλ(a) k=1,...,K is the vector of expected rewards over one time step (quantifying the gain from immediate exploitation) and Lλ(a) is an exploration term, given in (3.1) below. Lλ(a) k=1, ...,k は1つの時間ステップ(即時搾取によるゲインの定量化)で期待される報酬のベクトルであり、lλ(a) は3.1) で与えられる探索項である。 0.88
Intuitively, the term Lλ(a) combines the derivatives of f , with respect to the parameter estimate and its precision, to give an approximation of the expected increase in future payoffs which would be generated from the observations Y (k) 直感的には、Lλ(a) という用語は、パラメータ推定とその精度に関して f の導関数を結合し、Y(k) 観測から生じる将来のペイオフの予想値の増加の近似を与える。 0.80
, separately from the immediate reward. 即時報酬とは別物である。 0.59
t With this interpretation of f and Lλ, the components of a can be interpreted as measuring the immediate reward and the increase in total reward arising from each choice, taking into account the effect of learning on future rewards. t この f と lλ の解釈により、a の成分は、学習が将来の報酬に与える影響を考慮して、各選択から生じる即時報酬と総報酬の増加を測定するものとして解釈することができる。 0.80
The entropy term results in the ARC algorithm applying a softmax function to a, yielding conditional probabilities of choosing each arm, rather than a deterministic choice. エントロピー項は、ARCアルゴリズムが a にソフトマックス関数を適用し、決定論的選択よりも各アームを選択する条件付き確率を与える。 0.78
We refer to [5, Section 6] for a more detailed overview of this algorithm. このアルゴリズムのより詳細な概要については[5, section 6]を参照する。 0.86
t The implementation of the ARC algorithm requires the computation of the dynamics of the posterior parameter and the derivative of the expected one-period cost with respect to the underlying state (i.e., the posterior parameters). t ARCアルゴリズムの実装は、後パラメータのダイナミクスの計算と、基礎状態(すなわち後パラメータ)に関して予想される1周期コストの導出を必要とする。
訳抜け防止モード: t ARCアルゴリズムの実装には後続パラメータの動的計算が必要である そして、期待されているもの - 根底にある状態(すなわち、)に対する期間コスト - の導出 後部パラメーター)。
In our model, we use (2.5) to simplify our posterior dynamic for the generalised linear bandit, allowing us to estimate the relevant terms in the ARC algorithm for this case. 本モデルでは,一般化線形バンディットの後方ダイナミクスを簡略化するために (2.5) を用いており,この場合のARCアルゴリズムの関連項を推定することができる。 0.80
The implementation is given by the following steps: 実装は、次の手順で行われます。 0.65
Step I: Estimate the dynamics of posterior parameter. ステップI:後パラメータのダイナミクスを推定します。 0.82
The ARC algorithm requires the computation of how we expect the parameter estimate and its precision to change. ARCアルゴリズムは、パラメータ推定と精度の変化をどのように期待するかの計算を必要とする。 0.84
In the case of interest, we will treat the posterior mean m and variance Σ of the parameter Θ as the ‘estimator’ and ‘precision’ in the ARC algorithm. 興味のある場合は、パラメータθ の後方平均 m と分散 σ を、arcアルゴリズムの ‘推定’ と ‘予測’ として扱う。 0.55
Let m and Σ be the posterior mean and variance conditional on F U m と Σ を F U の後方平均と分散条件とする。 0.68
t and let M (k) and Σ(k) be their update after we choose the kth arm. t と M (k) と Σ(k) を k 番目の腕を選択した後のアップデートとする。 0.83
As discussed in Section 2.2.1, we can update M (k) and Σ(k) by (2.5). 2.2.1で述べたように、m (k) と σ(k) を (2.5) で更新することができる。 0.70
From (2.3), we estimate Ψ(k)|Θ ≈ N(cid:0)Θ(cid:62)x(k), 1/S(k)(cid:1). 2.3) から ψ(k)|θ, n(cid:0)θ(cid:62)x(k), 1/s(k)(cid:1) と推定する。 0.79
Assuming the posterior Θ ∼ N (m, Σ) gives 後方 θ n (m, σ) を仮定すると 0.61
. Hence, the conditional distribution of Ψ(k)|(m, Σ) can be approx- . したがって、(k)|(m, Σ) の条件分布は近似することができる。 0.82
(cid:16) Θ(cid:62)x(k) ∼ N imated by Ψ(k)|(m, Σ) ≈ N (cid:16) θ(cid:62)x(k) の n は ψ(k)|(m, σ) で模倣される。 0.80
m(cid:62)x(k),(cid:0 )x(k)(cid:1)(cid:62) (cid:16) m(cid:62)x(k),(cid:0 )x(k)(cid:1)(cid:62) (cid:16) 0.90
m(cid:62)x(k), m(cid:62)x(k) 0.86
Σ(cid:0)x(k)(cid:1)(c id:17) (cid:16) S(k)(x(k))(cid:62)Σ (x(k))+1 (cid:32) S(k)(cid:0)x(k)(cid: 1)(cid:62) Σ(cid:0)x(k)(cid:17) (cid:16) S(k)(x(k))(cid:62)Σ (x(k))+1 (cid:32) S(k)(cid:0)x(k)(cid: 62) 0.94
S(k) S(k) ∆M (k) ≈ S(k) S(k) M (k) です。 0.75
Σ(cid:0)x(k)(cid:1) + 1 Σ(cid:0)x(k)(cid:1) + 1 0.92
(cid:17)(cid:17) (cid:17)(cid:17) 0.75
. (cid:33)1/2 . (cid:33)1/2 0.75
Σ(cid:0)x(k)(cid:1)Z, Σ(cid:0)x(k)(cid:1)Z, 0.92
Therefore, (2.5) yields an approximate innovation representation したがって、(2.5) は近似的な革新表現を与える 0.64
where Z ∼ N (0, 1). Z は N (0, 1) である。 0.75
As Θ ∼ N (m, Σ), when Σ is small, we may estimate S(k) ≈ nkV(cid:0)m(cid:62)x (k)(cid:1) where nk = E(cid:0)N (k)(cid:1). θ n (m, σ) として、σ が小さいとき、s(k) の nkv(cid:0)m(cid:62)x (k)(cid:1) を nk = e(cid:0)n (k)(cid:1) と推定することができる。 0.77
Hence, in the notation of [5], the dynamics of our state (m, Σ) can be approximated by したがって、[5]の表記では、我々の状態(m, σ)のダイナミクスは近似することができる。 0.81
Em,Σ Varm,Σ Em,Σ Em,Σ Varm,Σ Em,Σ 0.85
(cid:0)∆M (k)(cid:1) ≈ ˜µ(k)(m, Σ) := 0, (cid:0)∆M (k)(cid:1) ≈(cid:0)˜σ˜σ(cid:62)(cid:1)(k) (m, d) := w(m, Σ, k)Σ(cid:0)x(k)(cid:1)(c id:0)x(k)(cid:1)(cid :62) (cid:0)∆Σ(k)(cid:1) ≈ ˜b(k)(m, d) := −w(m, Σ, k)Σ(cid:0)x(k)(cid:1)(c id:0)x(k)(cid:1)(cid :62) (cid:1). (cid:0) = M (k)(cid:1) シュ シュμ(k)(cid:) := 0, (cid:0) シュ M (k)(cid:1) シュ シュ シュσ(cid:62)(cid:1)(k) (m, d) := w(m, Σ, k)Σ(cid:0)x(k)(cid:1)(c id:62) (cid:0) Σ(k)(cid:1) (cid:62) (cid:0) Σ(k)(cid:1) シュ シュ シュb(k)(m, d) := −w(m, Σ, k)Σ(cid:0)x(cid:1)(cid: 62) 0.94
nkV (m(cid:62)x(k)) nkV (m(cid:62)x(k)) 0.99
Σ, Σ, nkV (m(cid:62)x(k))(x(k) )(cid:62)Σ (x(k))+1 Σ, Σ, nkV (m(cid:62)x(k))(x(k) )(cid:62)Σ (x(k))+1 0.90
where w(m, Σ, k) :=(cid:0) ここで w(m, Σ, k) :=(cid:0) 0.83
5This fixed-point calculation is the only computationally expensive part of the algorithm, and standard methods can be 5 この不動点計算はアルゴリズムの計算コストがかかる唯一の部分であり、標準的な計算方法である。
訳抜け防止モード: 5 この固定点計算はアルゴリズムの唯一の計算コストの高い部分である。 標準的な方法は
applied. 7 適用。 7 0.78
Step II: Compute the expected reward f and learning function Lλ using the estimated dynamics. ステップII: 予測報酬fと学習関数Lλを推定力学を用いて計算する。 0.85
We next compute the expected reward given the (estimate) posterior parameter, that is f : Rl × S l 次に、(推定)後続パラメータ、すなわち f : Rl × S l を与えられた期待報酬を計算する。 0.81
+ → RK with components 成分を持つ + → RK 0.89
where S l with components ここで S l コンポーネントです。 0.59
+ is the family of positive definite Rl×l matrices, and the learning function Lλ : RK ×Rl×S l + は正定値 Rl×l 行列の族であり、学習関数 Lλ : RK × Rl×S l である。 0.84
+ → RK k(a, m, Σ) := (cid:104)Bλ(a, m, Σ); Em,Σ Lλ + → RK k(a, m, Σ) := (cid:104)Bλ(a, m, Σ) Em,Σ Lλ 0.89
fk(m, Σ) := E(cid:16) fk(m, Σ) := E(cid:16) 0.98
R(k)(cid:0)Y (k)(cid:1)(cid:12)(c id:12)(cid:12)Θ ∼ N (m, Σ) (cid:17) (cid:0)∆Σ(k)(cid:1)(cid:105) + (cid:104)Mλ(a, m, Σ); Em,Σ R(k)(cid:0)Y(k)(cid: 1)(cid:12)(cid:12)(c id:12)(cid:12)(cid:1 2)(cid:17)(cid:0)(ci d:105)(cid:104)+(cid:104)Mλ(a, m, s);Em。 0.84
, (cid:0)∆M (k)(cid:1)(cid:105), , (cid:0)-M(k)(cid:1)( cid:105) 0.83
(cid:0)∆M (k)(cid:1)(cid:105) (cid:0)-M(k)(cid:1)( cid:105) 0.79
+ 1 2 (cid:104)Ξλ(a, m, Σ); Varm,Σ + 1 2 (cid:104) λ(a, m, Σ); Varm,Σ 0.88
(cid:88) k (cid:88) k 0.82
νλ k (a)(∂m fk), νλ k (a)(∂m fk) 0.85
ηλ jk(a)(∂m fj)(∂m fk) ηλ jk(a)(∂m fj)(∂m fk) 0.97
(cid:62) , (cid:62) , 0.82
and ηλ jk(a) そして ηλ jk(a) 0.86
(cid:88) exp(cid:0)aj/λ(cid:1), (cid:88) exp(cid:0)aj/λ(cid:1) 0.74
1 λ j,k (3.1) 1 λ j,k (3.1) 0.83
j (a)(cid:0)I(j = k) − νλ j (a)(cid:0)I(j = k) − νλ 0.99
k (a)(cid:1). k (a)(cid:1)。 0.86
:= νλ where we define Bλ := := νλ ここで bλ := を定義する。 0.76
k (a)(∂Σ fk), Mλ := νλ k (a)(∂σ fk), mλ := νλ 0.96
(cid:88) (cid:88) (cid:88)(cid:88) 0.74
k Ξλ := k (a) := exp(cid:0)ak/λ(cid:1)(cid:14)(cid: 88) k Ξλ := k (a) := exp(cid:0)ak/λ(cid:1)(cid:14)(cid: 88) 0.86
νλ k (a)(∂2 νλ k (a)(∂2) 0.84
k νλ m fk) + k νλ m fk) + 0.83
j if u, v ∈ Rl×l, then (cid:104)u; v(cid:105) = Tr(uv). j u, v ∈ Rl×l ならば (cid:104)u; v(cid:105) = Tr(uv) である。 0.89
by ˜f : Rl → RK with components f : rl → rk の成分による 0.61
The operator (cid:104)·;·(cid:105) is interpreted as an inner product of tensors, i.e. 作用素 (cid:104)·;·(cid:105) はテンソルの内部積として解釈される。 0.61
if u, v ∈ Rl, then (cid:104)u; v(cid:105) = u · v and u, v ∈ Rl ならば (cid:104)u; v(cid:105) = u · v 0.89
The ARC algorithm focuses on the regime where Σ is small. ARCアルゴリズムは、Σが小さい体制に焦点を当てている。 0.81
Hence, we estimate our expected reward ですから 期待する報酬を見積もって 0.72
fk(m, Σ) ≈ ˜fk(m) := E fk(m, σ) は fk(m) := e である。 0.78
(cid:18) R(k)(cid:16) (cid:0)m(cid:62)x(k) (cid:1), (cid:18) R(k)(cid:16) (cid:0)m(cid:62)x(k) (cid:1) 0.86
= hk N (k),(cid:0)Q(k) =hk N (k) (cid:0)Q(k) 0.80
i (cid:1)N (k) 私は (cid:1)N(k) 0.73
i=1 (cid:17)(cid:12)(cid :12)(cid:12)(cid:12) Θ = m (cid:19) i=1 (cid:17)(cid:12)(cid :12)(cid:12)(cid:12) = m (cid:19) 0.68
for some function hk. ある関数 hk に対して。 0.75
The last equality follows from the fact that {Q(k) and N (k) is independent of {Q(k) 最後の等式は {Q(k) と N(k) が {Q(k) とは独立であるという事実から従う。 0.86
i }i=1,...,∞. i=1, ...,∞ である。 0.66
i (3.2) |Θ = m}i=1,...,∞ ∼IID g(q; m(cid:62)x(k)) 私は (3.2) |* = m}i=1,...,∞ ×IID g(q; m(cid:62)x(k))) 0.72
Using the estimates ˜µ(k),(cid:0)˜σ˜σ(cid:62)(cid:1)(k) (cid:34) K(cid:88) (cid:32) K(cid:88) Σ(cid:0)x(k)(cid:1) . 推定値 (cid:0)、(cid:62)(cid:1)(k) (cid:34) K(cid:88) (cid:32) K(cid:88) Σ(cid:0)x(k)(cid:1) を用いる。 0.84
v(m, Σ, k) v(m, Σ, k) 0.85
νλ j (a) k := νλ j (a) k := 0.92
˜Lλ 1 λ 1 2 ○Lλ 1 λ 1 2 0.75
j=1 + , ˜b(k), and ˜fk, we can approximate Lλ in the ARC algorithm by j=1 + 、b(k)、fk は、アークアルゴリズムの lλ を近似することができる。 0.73
(cid:0)m(cid:62)x(j) (cid:1)(cid:0)rkj(Σ)(cid:1)2 (cid:17)2 − (cid:0)m(cid:62)x(j) (cid:1)rkj(Σ) (cid:0)m(cid:62)x(j) (cid:1)(cid:0)rkj(Σ)(cid:17)2 − (cid:0)m(cid:62)x(j) (cid:1)rkj(Σ) 0.94
j j (a)h(cid:48)(cid:48) νλ (cid:16) j j (a)h(cid:48)(cid:48) νλ(cid:16) 0.83
h(cid:48) (cid:18) K(cid:88) h(cid:48) (cid:18)K(cid:88) 0.81
(cid:0)m(cid:62)x(j) (cid:1)rkj(Σ) (cid:0)m(cid:62)x(j) (cid:1)rkj(\) 0.91
(cid:19)2(cid:33)(ci d:35) (cid:19)2(cid:33)(ci d:35) 0.76
j (a)h(cid:48) νλ j (a)h(cid:48) νλ 0.90
where rkj(Σ) :=(cid:0)x(j)(cid:1)(c id:62) uncertain. ここで rkj() :=(cid:0)x(j)(cid:1)(c id:62) は不確かです。 0.79
Here, we choose λρ(m, Σ) := ρ(cid:107)Σ(cid:107), using the Euclidean norm (cid:107)Σ(cid:107) =(cid:112)(cid:104)Σ; Σ(cid:105). ここで λρ(m, Σ) := ρ(cid:107)Σ(cid:107)Σ(cid:107)Σ(cid:107) = (cid:112)(cid:104)Σ; Σ(cid:105) を選択する。 0.83
We refer to [5] 私たちは[5]を参照します。 0.57
Step III: Use the ARC algorithm for the generalised linear bandit. ステップIII: 一般化線形バンドイットにARCアルゴリズムを使用する。 0.82
Finally, to apply the ARC algorithm, one also needs to choose a rescaling function to encourage randomisation when estimates are 最後に、ARCアルゴリズムを適用するには、推定値のランダム化を促進するために再スケーリング関数を選択する必要がある。 0.68
j=1 j=1 j j j=1 j=1 j j 0.72
for further discussion of the effect of this choice and alternatives. この選択と代替案の効果についてさらに議論する。 0.81
The implementation of this algorithm is then given by the pseudocode of Algorithm 1. このアルゴリズムの実装は、アルゴリズム1の擬似コードによって与えられる。 0.80
To run the ARC algorithm, we need to choose the parameters ρ > 0 and β ∈ (0, 1). ARCアルゴリズムを実行するには、パラメータ ρ > 0 と β ∈ (0, 1) を選択する必要があります。 0.89
Here ρ determines the randomness of our early choices, encouraging early exploration, while β is a discount factor, which is used to value the future reward. ここでρは初期の選択のランダム性を決定し、早期の探索を促し、一方βは将来の報酬を評価するための値引き因子である。 0.83
These parameters can be chosen by the user6. これらのパラメータはuser6で選択できます。 0.79
6It is suggested by Russo [16] for a related approach that β = 1 − 1/T , where T is the total number of trials, might be an 6) 関連するアプローチとしてRusso [16] が提案する β = 1 − 1/T で、T はトライアルの総数である。 0.69
appropriate choice. 8 , 適切な選択だ 8 , 0.82
(3.3) (3.3) 0.78
Algorithm 1 ARC Algorithm アルゴリズム1 ARCアルゴリズム 0.71
Input: ρ, β, m, Σ, T Let ˜f and ˜Lλ be function given in (3.2) and (3.3) for t = 1, ..., T do Define λ = ρ(cid:107)Σ(cid:107) 入力: ρ, β, m, Σ, T を t = 1, ..., T do Define λ = ρ(cid:107)Σ(cid:107) で与えられる関数とする。
訳抜け防止モード: 入力 : ρ, β, m, s, T は、(3.2 ) で与えられる関数である。 そして (3.3 ) for t = 1 , ... , T do Define λ = ρ(cid:107)\(cid:107 )
Solve a = ˜f (m) +(cid:0) β a = (m) +(cid:0) β を解く。 0.77
(cid:1) ˜Lλ(cid:0)a, m, Σ(cid:1) for a (cid:1 )lλ(cid:0)a, m, σ(cid:1) 0.86
1−β Sample At with P(At = k) = νλ Obtain observations (N, Q) and collect the reward Update the posterior parameter (m, Σ) as in (2.5) 1−β Sample At with P(At = k) = νλ Obtain observations (N, Q) and collect the reward Update the posterior parameters (m, s) as in (2.5) 0.74
k (a) end for 3.3 Theoretical Guarantee of the ARC algorithm k (a) 終止符 3.3 ARCアルゴリズムの理論的保証 0.79
It was shown in [5] that for a smooth function f and 滑らかな関数 f に対して[5] で示されました。 0.73
˜V (π, β, (Ut)) := Eπ πV(π, β, (Ut)) := Eπ 0.94
βt−1f (At, Mt−1, Σt−1) βt−1f(At, Mt−1, Σt−1) 0.59
(3.4) (cid:34) ∞(cid:88) (3.4) (cid:34) ∞(cid:88) 0.78
t=1 (cid:35) (cid:12)(cid:12)(cid :12) = O((cid:107)Σ0(cid:107)). t=1 (cid:35) (cid:12)(cid:12)(cid :12) = O((cid:107)Σ0(cid:107))。 0.67
, (cid:12)(cid:12)(cid :12) ˜V (π, β, (U ARC , (cid:12)(cid:12)(cid :12)(π,β,UARC) 0.86
t )) − sup U t ) − sup うう 0.60
˜V (π, β, (Ut)) πV (π, β, (Ut)) 0.84
we have In addition, they also showed that (cid:107)Σt(cid:107) → 0 as t → ∞ Pπ-a.s. (given that G is sufficiently nice). 我々は さらに、 (cid:107)σt(cid:107) → 0 as t → ∞ pπ-a.s. (g が十分良い) も示された。 0.77
For the multi-armed bandit problem, one may wish to consider the total discounted reward (2.1). 多武装バンディット問題に対して、合計割引報酬(2.1)を考えることができる。 0.68
However, when we do not have a prior-posterior conjugate pair, which is the case for this GLM framework, the equality between (2.1) and (3.4) cannot be guaranteed. ただし、このGLMフレームワークの場合である先行後共役ペアがない場合、(2.1)と(3.4)の等価性を保証することはできません。 0.72
Nonetheless, given that the batch size is relatively large, the difference between (2.1) and (3.4) is small. しかし、バッチサイズが比較的大きいことを考えると、(2.1)と(3.4)の違いは小さい。 0.81
4 Simulation of a bandit environment 4 バンディット環境のシミュレーション 0.62
As the strategy followed determines the observations available, we cannot directly use historical data to test the algorithm. その後の戦略が利用可能な観測値を決定するため、アルゴリズムをテストするために履歴データを直接使用することはできない。 0.67
However, we can use the data to construct an environment in which to run tests. しかし、テストを実行する環境を構築するためにデータを使うことができます。 0.80
We take a Bayesian view and build a simple hierarchical model (with an improper uniform prior). ベイズ的視点を採り、単純な階層的モデルを構築する(前もって不適切な一様である)。 0.60
Effectively, this assumes that our observations come from an exchangable copy of the world we would deploy our bandits in, with the same (unknown) realised value of Θ. これは事実上、我々の観察が、(知られていない)θ が実現されたのと同じ値で、私たちがバンディットを展開するであろう世界の交換可能なコピーから来ていると仮定している。
訳抜け防止モード: 効果的に、私たちの観察は、我々の盗賊を配置する世界の交換可能なコピーから来ていると仮定する。 同じ値 (未知の値) が実現した。
Then we will use Laplace approximation, as in Russo et al. 次に、Russo et alのようにLaplace近似を使用します。 0.73
[19, Chapter 5] or Chapelle and Li [4], to obtain a posterior sample to simulate the markets. [19,章5]又はChapelleとLi[4]は、市場をシミュレートする後続サンプルを取得する。
訳抜け防止モード: [19, 第5章]またはチャペルと李 [4] 市場をシミュレートするために後部のサンプルを得るため。
Remark 3. It is worth emphasising that when implementing the algorithm in the simulation, we do not assume that our algorithms know the distribution that we use to simulate the parameter, Θ. 備考3。 シミュレーションでアルゴリズムを実装するとき、我々のアルゴリズムがパラメータθをシミュレートするのに使用する分布を知っているとは考えていないことを強調する価値がある。 0.65
Instead the simulations are initialised with an almost uninformative prior. 代わりにシミュレーションは、ほとんど非形式的な事前で初期化される。 0.62
To construct a posterior for Θ given historical data, we assume that we have a collection of observations i=1, (q(2) )rK )r1 i=1 from an exponential family modeled by (2.2). ヒストリカルデータに対する後続データを構築するために、 (2.2) でモデル化された指数族から i=1, (q(2) )rK )r1 i=1 の観測コレクションがあると仮定する。 0.74
We denote the corresponding 対応するものを示します 0.54
i=1, ..., (q(K) )r2 i=1, ..., (q(K) )r2 0.99
i i i (q(1) 私は 私は 私は (q(1)) 0.63
the log-likelihood function by log-likelihood (複数形 log-likelihoods) 0.32
log-likelihood function of Θ by (cid:96)(cid:0)θ;(cid:0)q(k) (cid:1)(cid:1). log-likelihood function of (cid:96)(cid:0)θ; (cid:0)q(k) (cid:1) (cid:1)。 0.81
Let ˆθ be the maximum likelihood estimator. θ を最大確率推定器とする。 0.75
i.e. ˆθ = arg maxθ (cid:96)(cid:0)θ;(cid:0)q(k) (cid:1)(cid:17) ≈ 1 θ (cid:96)(cid:0)ˆθ;(cid:0)q(k) (cid:1)(cid:1)(θ − ˆθ) + c, θ;(cid:0)q(k) )(cid:1)(cid:17)−1(cid:17) (cid:16)ˆθ, θ (cid:96)(cid:0)ˆθ; (q(k) i.e. θ = arg maxθ (cid:96)(cid:0)θ;(cid:0)q(k) (cid:17) (cid:17) (cid:96)(cid:0) θ;(cid:0)q(k) (cid:1)(cid:1)(cid:1 )(θ − zyθ) + c, θ;(cid:0)q(k) )(cid:1)(cid:17)−1(cid:17) (cid:16) θ, θ (cid:96)(cid:0) θ; (q(k)) 0.78
(cid:16) − ∂2 (cid:16) − 2 0.84
(θ − ˆθ)(cid:62) ∂2 (θ − θ)(cid:62) ∂2 0.90
Θ ∼ N (cid:16) は、N。 (cid:16) 0.71
2 (cid:96) 2 (cid:96) 0.82
. i i i . 私は 私は 私は 0.61
i i for c independent of θ. 私は 私は θ から独立している c に対して。 0.54
Therefore, starting from the uninformative (improper, uniform) prior, we can estimate the posterior of the parameter Θ by したがって、事前の非情報的(不適切な、均一な)から始めて、パラメータの後方を推定することができます。 0.65
(cid:1)(cid:1). (cid:1)(cid:1)。 0.72
Then we may approximate (4.1) では 近似して (4.1) 0.65
9 9 0.85
In particular, if the parameter for the exponential family is given in its canonical form, i.e. 特に、指数関数族に対するパラメータが正準形式、すなわち正準形式で与えられる場合。 0.71
when φ in (2.2) is the identity, then the observed Fisher information is φ in (2.2) が id であるとき、観測されたフィッシャー情報は 0.81
θ (cid:96)(cid:0)ˆθ; (q(k) θ (cid:96)(cid:0) =θ; (q(k) 0.87
i )(cid:1) = 私は )(cid:1) = 0.71
K(cid:88) − ∂2 K(cid:88) − ∂2 0.86
rkG(cid:48)(cid:48)( cid:0)ˆθ(cid:62)x(k)(cid:1)( cid:0)x(k)(cid:1)(ci d:0)x(k)(cid:1)(cid: 62) rkG(cid:48)(cid:48)( cid:0)\(cid:62)x(k)( cid:1)(cid:0)x(k)(ci d:0)x(k)(cid:62) 0.96
. We will use the simulated values of Θ as the (hidden) realisations with which to test our algorithms. . 我々は、アルゴリズムをテストするための(隠れた)実現法として、シュミレーションされた値を用いる。 0.78
k=1 4.1 Dynamic Pricing Simulation k=1 4.1 ダイナミック価格シミュレーション 0.69
Finally, we can implement the multi-armed bandit algorithm to run a simulation for the dynamic online pricing problem. 最後に、動的オンライン価格問題に対するシミュレーションを実行するために、マルチアームバンディットアルゴリズムを実装できる。 0.72
Recall that in this model, at each time t, we need to choose x(k) = (1, ck) ∈ R2 where ck is the price and whether each customer buys the このモデルでは、毎回 t で x(k) = (1, ck) ∈ R2 を選択する必要があることを思い出してください。
訳抜け防止モード: このモデルでは、t の度に ck が値である x(k ) = ( 1, ck ) ∈ R2 を選択する必要があることを思い出してください。 それぞれの顧客が購入するかどうか
of the product. We then observe the number of customers N (k) 商品の1つです その後、顧客数 N (k) を観察します。 0.67
product or not in terms of a binary random variable (cid:0)Q(k) (cid:1)N (k) i,t . 製品またはバイナリランダム変数(cid:0)Q(k) (cid:1)N(k) i、tの観点で。 0.71
We will model(cid:0)Q(k) step is given by R(k)(cid:0)N (k) (cid:17)(cid:17) = nkckG(cid:48)(cid:0) θ(cid:62)x(k)(cid:1), モデル(cid:0)q(k)ステップは r(k)(cid:0)n (k) (cid:17)(cid:17) = nkckg(cid:48)(cid:0) θ(cid:62)x(k)(cid:1) で与えられる。 0.85
G(z) = log(1 + ez) and φ(z) = z for the functions φ and G in (2.2). G(z) = log(1 + ez) および (2.2) の函数 φ と G に対する φ(z) = z である。 0.93
We can now write down the expected reward, 期待した報酬を 書き留めることができます 0.61
(cid:1) := ck (cid:1) := ck 0.92
R(k)(cid:16) R(k)(cid:16) 0.94
(cid:80)N (k) (cid:80)N(k) 0.93
1,t , ..., Q(k) Nt,t 1,t , ..., Q(k) Nt,t 0.79
i=1 Q(k) , Q(k) i=1 Q(k) , Q(k) 0.87
(cid:16) i,t (cid:16) 私は... 0.59
i,t t t t 私は... t t t 0.74
t i=1 . The reward that we receive in each t i=1。 それぞれが受ける報酬です。 0.58
(cid:1) by a logistic model, i.e. (cid:1) ロジスティックモデルによる。 0.66
Eθ ). In particular, the function hk in (3.2) and (3.3) is given by hk(y) = nkckG(cid:48)(cid:0) y(cid:1). Eθ ). 特に、3.2 および 3.3 の函数 hk は hk(y) = nkckg(cid:48)(cid:0) y(cid:1) によって与えられる。 0.84
1,t , ..., Q(k) N (k) 1,t , ..., Q(k) N(k) 0.79
, Q(k) N (k) , Q(k) N (k) 0.85
,t t t where nk = E(N (k) t.t. t t ここで nk = E(N (k)) 0.75
t 4.1.1 Market data and simulation environment t 4.1.1 市場データとシミュレーション環境 0.79
In Dub´e and Misra [6], in stage one of their experiment, they randomly assigned one of ten experimental pricing cells to 7,867 different customers who reached Ziprecruiter’s paywall. Dub ́eとMisra [6]では、実験のステージ1で、Ziprecruiterのペイウォールに到達した7,867の異なる顧客に10の実験価格セルのうちの1つをランダムに割り当てました。 0.67
The exact numbers of customers that were assigned to each price are not reported. 各価格に割り当てられた顧客の正確な数は報告されません。 0.86
Hence, we will assume that there are exactly 787 customers for each price. したがって、価格ごとにちょうど787の顧客がいると仮定します。 0.82
We then use their reported subscription rate to estimate the exact numbers of customers who decided to subscribe given each price. 次に、報告されたサブスクリプションレートを使用して、各価格の加入を決めた顧客の正確な数を見積もる。 0.65
Using this data, we apply (4.1) to infer an approximate posterior distribution: このデータを用いて(4.1)近似的な後方分布を推定する。 0.77
Θ(cid:12)(cid:12)(cid :0)q(k) θ(cid:12)(cid:12)(cid :0)q(k) 0.76
i (cid:1) ∼ N 私は (cid:1) 0.59
(cid:32)(cid:18)−6.42 × 10−1 (cid:32)(cid:18)−6.42 × 10−1 0.62
−4.03 × 10−3 −4.03 × 10−3 0.52
(cid:19) (cid:18) 1.90 × 10−3 −8.86 × 10−6 (cid:19) (cid:18) 1.90 × 10−3 −8.86 × 10−6 0.67
, −8.86 × 10−6 , −8.86 × 10−6 0.69
6.82 × 10−8 6.82 × 10−8 0.59
(cid:19)(cid:33) (cid:19)(cid:33) 0.75
. (4.2) In order to compare performance, we will consider each algorithm over a period of one year (365 days) and only allow the agent to change the price at the end of each day. . (4.2) パフォーマンスを比較するために、各アルゴリズムを1年(365日)の期間で検討し、エージェントが一日の終わりに価格を変更できるようにします。 0.77
We assume that a common price must be shown to all customers on each day. 私達は共通の価格が毎日すべての顧客に示されなければならないと仮定します。 0.72
We will also assume that the chosen price does not affect the number of customers reaching the paywall. また、選択された価格がペイウォールに到達する顧客数に影響しないと仮定する。 0.72
i.e. we assume that N (k) We run 5 × 103 independent simulations of the different market situations, where for each simulation t=1 ∼ Poisson(270) to represent the parameter Θ is sampled from (4.2). i.e. 我々は、N(k) 異なる市場状況の5 × 103 独立シミュレーションを実行すると仮定し、各シミュレーション t=1 × Poisson(270) に対してパラメータ y を表すために(4.2) からサンプリングする。 0.79
We also independently sample (Nt)365 the number of visitors on each day7. また、1日あたりの訪問者数(nt)365を独立にサンプリングした。 0.71
The simulated subscription probability and the simulated expected revenue per customer, for each price level, are illustrated in Figure 2. シミュレーションされたサブスクリプションの確率と、各価格レベルの顧客当たりのシミュレーションされた予想収益を図2に示します。 0.75
t ≡ Nt. 4.1.2 Simulation Results 略称はNt。 4.1.2 シミュレーション結果 0.53
We apply each algorithm described in Section 3, with m0 = (0, 0) and Σ0 = I2 as an initial prior for Θ and use (2.5) to propagate the prior. セクション3で記述された各アルゴリズムに、m0 = (0, 0) と Σ0 = I2 を初期先行として適用し、前項を伝搬するために (2.5) を使用する。 0.78
To assess the performance of each algorithm, one often compares the cumulative pseudo-regret of each 各アルゴリズムの性能を評価するために、各アルゴリズムの累積擬似回帰をしばしば比較する 0.81
algorithm given the true parameter Θ: 真のパラメータが与えられたアルゴリズム: 0.80
R(cid:0)θ, T, (At)(cid:1) := R(cid:0) , T, (At)(cid:1) := 0.99
T(cid:88) (cid:16) T(cid:88) (cid:16) 0.81
t=1 max k t=1 マックス k 0.71
(cid:17) hk(θ) − hAt(θ) (cid:17) hk(θ) − hAt(θ) 0.98
, 7In [6], they observed that ZipRecruiter.com had roughly 8, 000 visitors per month. , 7in[6]でziprecruiter.comの月間訪問者は約8万人であった。 0.82
Hence, it is reasonable to assume that したがって、それを仮定するのは合理的です。 0.63
there are roughly 270 visitors per day. 1日あたりの訪問者は270人です 0.70
10 10 0.85
Figure 2: (a): The average subscription rate in our simulation, with two standard deviation bands. 図2: (a): 2つの標準偏差帯域を持つシミュレーションの平均購読率。 0.72
(b): The average reward per customer in our simulation, with two standard deviation bands. (b)2つの標準偏差帯域を持つシミュレーションにおいて,顧客毎の平均報酬。 0.79
where hk(θ) := E(cid:2)R(k)(cid:0)Y (k) hk(θ) := E(cid:2)R(k)(cid:0)Y (k) 0.88
t (cid:1)(cid:12)(cid: 12)Θ = θ(cid:3) = nckG(cid:48)(cid:0)θ(cid:62)x(k)(cid:1), G(y) = log(1 + ey), (At) is the sequence of actions t (cid:1)(cid:12)(cid: 12) ) = nckG(cid:48)(cid:0) ) = (cid:62)x(k)(cid:1), G(y) = log(1 + ey), (At) はアクションのシーケンスである。 0.88
that the algorithm chooses and n = E(N (k) アルゴリズムが選択し、n = E(N(k)) 0.78
). t Figure 3 shows the mean, median, 0.75 quantile and 0.90 quantile of cumulative pseudo-regret of each algorithm described in Section 3. ). t 図3は、セクション3で記述された各アルゴリズムの平均、中央値、0.75量子と累積擬似回帰の0.90量子を示している。 0.77
We see that most algorithms outperform the classical UCB and the UCB-tuned used in Misra et al. ほとんどのアルゴリズムは、古典的な UCB や、Misra などで使われている UCB-tuned よりも優れています。 0.57
[14], which is unsurprising as these approaches ignore correlation between demand at different prices. これらのアプローチは異なる価格での需要間の相関を無視しているため、驚くにあたらない。 0.59
We also see that the ARC algorithm outperforms all other algorithms both on average and in extreme cases (as shown by the quantile plots). また、ARCアルゴリズムは、平均および極端な場合(量子プロットで示されるように)において、他の全てのアルゴリズムよりも優れています。 0.70
In addition to the regret criteria, when displaying the price, the agent may not want to change the price too frequently. 後悔の基準に加えて、価格を表示する場合、エージェントは頻繁に価格を変更することを望まないかもしれない。 0.67
This is why the Explore-Then-Commit (ETC) algorithm is often preferred when considering a pricing problem. そのため、価格問題を考える場合、ETC(Explore-Then-Com mit)アルゴリズムが好まれる。 0.71
Figure 4 shows that the ARC algorithm and KG algorithm typically require a small number of price changes but still achieve a reasonably low regret (as shown in Figure 3) whereas, Thompson sampling and the UCB type algorithms require a larger number of price changes. 図4は、ARCアルゴリズムとKGアルゴリズムは、典型的には少数の価格変更を必要とするが、(図3に示すように)相変わらず低い後悔を達成する一方で、トンプソンサンプリングとUPB型アルゴリズムはより多くの価格変更を必要とすることを示している。 0.75
11 0100200300400500Pric e0. 50.300.35Subscriptio n Rate(a)0100200300400 500Price010203040Exp ected Reward per customer(b) 11 0100200400500Price0. bscription Rate(a)0100200400500 Price0102030Expected Reward per customer(b) 0.68
Figure 3: (a): Mean, (b): Median, (c): 0.75 quantile and (d): 0.90 quantile of cumulative expected-expected pseudo regret 図3: (a): Mean, (b): Median, (c): 0.75 Quantile and (d): 0.90 Quantile of cumulative expected-expected pseudo regret 0.92
12 05010015020025030035 0Trials0100002000030 00040000500006000070 00080000Expected-Exp ected Regret(a)05010015020 0250300350Trials(b) 05010015020025030035 0Trials0100002000030 00040000500006000070 00080000Expected-Exp ected Regret(c) 05010015020025030035 0Trials(d) ARC: =0.1, = 0.997ARC: =1, = 0.997ARC: =5, = 0.997ARC: =10, = 0.997ETC: =0.005ETC: =0.01ETC: =0.05ETC: =0.1Bayes-UCB: c=0Bayes-UCB: c=5Classic UCBUCB-tunedGreedy: =0Greedy: =0.05Greedy: =0.1KG: = 0.997ThompsonIDS 12 0501001502002350350T rials010000200003000 04000050000000700008 0000Expected-expecte d Regret(a)05010015020 02350Trials(b)050100 150350Trials01000000 00400005000000000000 00000000000700008000 0Expected-expected Regret(c)05015035035 0Trials(d)ARC:=0.1, = 0.997ARC: =1, = 0.997ARC: =0.997ARC: =10, = 0.997ETC: =0.005ETC: =0.01ETC: =0.05ETC: = 0.1Bayes-UCB:=0Bayes-B: c=c=c=c=c-c-c-c:5Gyed:=0.5GyedGyed=0GyedGyd:=0.0.1, = 0.997ARC:0.0Smpson =0。
訳抜け防止モード: 12 050100150350350Trial s0100002000030000400 00500000007000080000 Expected - Expected Regret(a)05010015035 0350Trials(b) 050100150350Trials01 00000300004000050000 0007000080000Expecte d - Expected Regret(c) 050100150350350Trial s(d)ARC : = 0.1。 0997ARC : = 1 = 0.997ARC : = 5 0997ARC : = 10 , = 0.997ETC : = 0.005ETC : = 0.01ETC : = 0.05ETC : = 0.1Bayes - UCB : c=0Bayes - UCB : c=5Classic UCBUCB - tunedGreedy : = 0Greedy : = 0.05Greedy : = 0.1KG : = 0.997ThompsonIDS
Figure 4: (a): Mean, (b): Median, (c): 0.75 quantile and (d): 0.90 quantile of the number of price changes 図4: (a): Mean, (b): Median, (c): 0.75 Quantile, (d): 0.90 Quantile of the number of price change 0.85
Acknowledgements: Samuel Cohen thanks the Oxford-Man Institute for research support and acknowledges the support of The Alan Turing Institute under the Engineering and Physical Sciences Research Council grant EP/N510129/1. 謝辞:samuel cohenはoxford-man institute for research supportに感謝し、engineering and physical sciences research council grant ep/n510129/1のalan turing instituteの支援を認めている。 0.65
Tanut Treetanthiploet acknowledges support of the Development and Promotion of Science and Technology Talents Project (DPST) of the Government of Thailand. Tanut Treetanthiploetは、タイ政府の科学技術人材プロジェクト(DPST)の開発と促進の支援を認めています。 0.74
References [1] R. Agrawal. 参考文献 [1] R. Agrawal。 0.77
Sample mean based index policies by O(log N ) regret for the multi-armed bandit problem. マルチアームドバンディット問題に対する o(log n ) regret によるサンプル平均ベースのインデックスポリシー。 0.73
Advances in Applied Probability, pages 1054–1078, 1995. 応用確率の進歩、1054-1078ページ、1995。 0.77
[2] P. Auer, N. Cesa-Bianchi, and P. Fischer. [2] P. Auer, N. Cesa-Bianchi, P. Fischer 0.89
Finite-time analysis of the multiarmed bandit problem. マルチアームバンディット問題の有限時間解析。 0.62
Machine Learning, pages 235–256, 2002. 機械学習、2002年235-256ページ。 0.85
13 05010015020025030035 0Trials020406080100T he number of price changes(a)0501001502 00250300350Trials(b) 05010015020025030035 0Trials020406080100T he number of price changes(c) 05010015020025030035 0Trials(d) ARC: =0.1, = 0.997ARC: =1, = 0.997ARC: =5, = 0.997ARC: =10, = 0.997ETC: =0.005ETC: =0.01ETC: =0.05ETC: =0.1Bayes-UCB: c=0Bayes-UCB: c=5Classic UCBUCB-tunedGreedy: =0Greedy: =0.05Greedy: =0.1KG: = 0.997ThompsonIDS 13 05010015020025030035 0Trials020406080100価格変更(a)050100150350350Tr ials020506080100価格変更(c)050100150350350Tr ials(d)ARC: =0.1, = 0.997ARC: =0.997ARC: =5, = 0.997ARC: =10, = 0.997ETC: =0.005ETC: =0.01ETC: =0.05ETC: =0.1Bayes-UCB: c=0Bayes-UCB: c=5Classic UCBUCB-tunedGreed: =0.1Bayes-UCB: c=0Bayes-UCB: c=5Classic UCBUCB-tunedGreed: =0.5Gyed: =0.5Gyed: = 0.997Gyed: = 0.997EmpSson
訳抜け防止モード: 13 05010015020025030035 0Trials020406080100価格変更(a)050100150350350Tr ials(b)050100150350T rials020406080100価格変更(c)050150350350Trial s(d)ARC := 0.1。 0997ARC : = 1 = 0.997ARC : = 5 = 0.997ARC : = 10, 0997ETC : = 0.005ETC : = 0.01ETC : = 0.05ETC : = 0.1Bayes - UCB : c=0Bayes - UCB : c=5Classic UCBUCB - tunedGreedy : = 0Greedy : = 0.05Greedy : = 0.1KG : = 0.997ThompsonIDS
[3] G. Burtini, J. Loeppky, and R. Lawrence. 3] G. Burtini、J. Loeppky、R. Lawrence。 0.80
A survey of online experiment design with the stochastic 確率を用いたオンライン実験設計に関する調査 0.79
multi-armed bandit. マルチ武装のバンディット。 0.56
arXiv:1510.00757v4, 2015. arXiv:1510.00757v4, 2015 0.55
[4] O. Chapelle and L. Li. 4] O. ChapelleおよびL. Li。 0.87
An empirical evaluation of thompson sampling. トンプソンサンプリングの実験的評価 0.50
Advances in Neural Information Processing Systems 24, page 2249–2257, 2011. 神経情報技術の進歩 処理システム 24, ページ 2249–2257, 2011。 0.77
[5] S. N. Cohen and T. Treetanthiploet. [5]S. N. CohenとT. Treetanthiploet。 0.80
Asymptotic Randomised Control with applications to bandits. バンディットへの応用による漸近的ランダム化制御 0.65
arXiv:2010.07252, 2020. arXiv:2010.07252, 2020 0.70
[6] J-P. Dub´e and S. Misra. 6] J-P. Dub と S. Misra。 0.82
Scalable price targeting. スケーラブルな価格ターゲティング。 0.63
NBER working paper No. nber作業用紙 no. 0.78
w23775, National Bureau w23775 国立局 0.70
of Economic’ Research, 2017. 2017年「経済研究」。 0.70
[7] L. Fahrmeir. 7] L. Fahrmeir。 0.74
Posterior mode estimation by extended kalman filtering for multivariate dynamic gener- 多変量動的ジェネラに対する拡張カルマンフィルタによる後方モード推定- 0.78
alized linear models. Journal of the American Statistical Association, pages 501–509, 1992. アル化線形モデル。 Journal of the American Statistical Association, Page 501–509, 1992年。 0.83
[8] S. Filippi, O. Capp´e, A. Garivier, and C. Szepesv´ari. [8]S. Filippi, O. Capp ́e, A. Garivier, C. Szepesv ́ari. 0.80
Parametric bandits: the Generalized Linear case. Parametric bandits: Generalized Linear case。 0.66
In NIPS’10: Proceedings of the 23rd International Conference on Neural Information Processing Systems, page 586–594, 2010. NIPS’10: Proceedings of the 23rd International Conference on Neural Information Processing Systems, page 586–594, 2010 0.85
[9] J. C. Gittins and D. M. Jones. 9] J.C. GittinsとD.M. Jones。 0.87
A dynamic allocation index for the sequential design of experiments. 実験の逐次設計のための動的割り当てインデックス。 0.75
In J. Gani, editor, Progress in Statistics, pages 241–266, Amsterdam: North Holland, 1974. J. Gani, editor, Progress in Statistics, page 241–266, Amsterdam: North Holland, 1974. (英語) 0.88
[10] E. Kaufmann, O. Capp´e, and Aurelien Garivier. [10] E. Kaufmann, O. Capp ́e, and Aurselien Garivier. 0.90
On Bayesian upper confidence bounds for bandit バンディットに対するベイズ上層信頼境界について 0.55
problems. In Artificial intelligence and statistics, pages 592–600, 2012. 問題だ 人工知能と統計』592-600頁、2012年。 0.68
[11] J. Kirschner and A. Krause. 11] J. KirschnerとA. Krause。 0.86
Information Directed Sampling and bandits with heteroscedastic noise. 異方性雑音によるサンプリングと包帯情報 0.56
Proceedings of Machine Learning Research, pages 1–28, 2018. Proceedings of Machine Learning Research, page 1–28, 2018 0.84
[12] T. L. Lai and H. Robbins. 12] T.L. LaiとH. Robbins。 0.89
Asymptotically efficient adaptive allocation rules. 漸近的に効率的な適応割当規則。 0.54
Advances in Applied Mathematics, pages 4–22, 1985. 応用の進歩 数学、1985年4-22ページ。 0.68
[13] T. Lattimore and C. Szepesv´ari. 13] T. Lattimore と C. Szepesv ́ari. 0.87
Bandit Algorithms. バンディットアルゴリズム。 0.62
Cambridge University Press, 2019. ケンブリッジ大学出版局、2019年。 0.60
[14] K. Misra, E. M. Schwartz, and J. Abernethy. 14] K. Misra、E.M. Schwartz、J. Abernethy。 0.81
Dynamic online pricing with incomplete information 不完全な情報を含む動的オンライン価格 0.65
using multiarmed bandit experiments. マルチアームのバンディット実験で 0.68
Marketing Science, pages 226–252, 2019. マーケティング科学、2019年226-252ページ。 0.74
[15] P. Rusmevichientong and J. N. Tsitsiklis. [15]P. RusmevichientongとJ. N. Tsitsiklis 0.87
Linearly parameterized bandits. 線形パラメータ化バンド。 0.57
Mathematics of Operations Research, pages 395–411, 2009. 操作の数学 調査, ページ 395–411, 2009。 0.77
[16] D. Russo. 16] D. Russo。 0.78
A note on the equivalence of upper confidence bounds and Gittins indices for patient agents. 患者エージェントに対する上信頼度とジチン指数の等価性についての一考察 0.79
arXiv:1904.04732, 2019. arXiv:1904.04732, 2019 0.71
[17] D. Russo and B. 17] D. RussoおよびB。 0.77
Van Roy. An information-theoreti c analysis of Thompson Sampling. ヴァン・ロイ。 Thompson Samplingの情報理論解析 0.66
Journal of Machine Learning Research, pages 1–30, 2016. 日誌 機械学習研究、2016年1-30ページ。 0.64
[18] D. Russo and B. 18] D. RussoおよびB。 0.77
Van Roy. Learning to optimize via Information-Directed Sampling. ヴァン・ロイ。 情報指向サンプリングによる最適化の学習。 0.69
Operations Research, pages 1–23, 2017. 作戦 研究、2017年1-23ページ。 0.64
[19] D. J. Russo, B. V. Roy, A. Kazerouni, I. Osband, and Z. Wen. [19]D. J. Russo, B. V. Roy, A. Kazerouni, I. Osband, Z. Wen 0.91
A tutorial on Thompson Sampling. Thompson Samplingのチュートリアル。 0.62
Foundations and Trends in Machine Learning, 11(1):1–96, 2018. 機械学習の基礎とトレンド - 11(1):1-96, 2018年。 0.76
[20] I. O. Ryzhov, W. B. Powell, and P. I. Frazier. 20] i. o. ryzhov, w. b. powell, p. i. frazier. 0.68
The Knowledge Gradient algorithm for a general class 一般クラスにおける知識勾配アルゴリズム 0.77
of online learning problems. オンライン学習の問題です 0.79
Operations Research, pages 180–195, 2012. 運用調査, ページ 180–195, 2012。 0.79
[21] W. R. Thompson. 21] W.R.トンプソン。 0.70
On the likelihood that one unknown probability exceeds another in view of the ある未知の確率が別の確率を超える可能性について 0.77
evidence of two samples. 2つのサンプルの証拠だ 0.74
Biometrika, pages 285–294, 1933. Biometrika, ページ 285–294, 1933。 0.84
[22] J. Vermorel and M. Mohri. 22] J. VermorelとM. Mohri。 0.84
Multi-armed bandit algorithms and empirical evaluation. マルチアームバンディットアルゴリズムと経験的評価 0.49
In European Conference on Machine Learning., pages 437–448, 2005. ヨーロッパでは 英語) Conference on Machine Learning., page 437–448, 2005 0.79
14 14 0.85

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