text: 7 To maintain redundancy, whenever a storage node fails, it is instantly replaced with a newcomer node that is randomly chosen from the empty nodes present in the cluster. This newcomer node ≤ − contacts any d n 1 storage nodes, downloads β units of data from each and stores α units of data. Note that the new content in the newcomer node does not need to be exactly the data that were lost in the failed node. Hence, we consider functional repair, which ensures that both the MDS and the regeneration property hold after an arbitrary failure. Throughout this paper, we assume instant repair after failures so that no matter which coding method is used, there are always n caching nodes in the cluster as long as the Markov chain in Figure 2 never goes to a state lower than n, which we deem a valid assumption as we only (cid:28) investigate the case n m, and thus the probability of ﬁnding the chain in small states is extremely small2. A DSS is determined by the tuple (n, k, d, α, γ), whereof the triple (n, k, d) consists of the storage degree, reconstruction degree and repair degree. In other words, reconstructing the data ﬁle requires contacting k out of total n storage nodes, while repairing the contents of a lost node requires contacting d nodes. In addition, the parameter tuple (α, γ) consists of the fragment size α stored in each of the n storage nodes, and the repair bandwidth γ, that is the total number of units of data that a newcomer needs to download for repairing a lost node. Note that when repairing, each storage node involved in the repair process transmits β units of data to the newcomer node, so that γ = dβ. A given tuple of parameters (n, k, d, α, γ) is feasible if a code with such α and γ exists. For a result on the existence of feasible parameter tuples, we refer to [29, Thm. 1]. More importantly, there is a natural tradeoff between α and γ given by a piecewise linear function. Codes lying on this tradeoff curve are called regenerating codes. Hence, regenerating codes offer an optimal tradeoff between storage space consumption and repair bandwidth, while maintaining the MDS property. Furthermore, any d nodes can be contacted to resurrect a lost node while maintaining these properties after repairs. Hence, regenerating codes are an attractive choice. In this work, we consider two types of regenerating codes: codes attaining one of the two extremal points, i.e., the points where either the storage space consumption or repair bandwidth is 2For example, if m = 100 and n = 6, values which we will later use in our simulations, the probability that the number of × − nodes in the cluster drops to n or below is approximately 5.5 10 35.

text: To

text: maintain

text: redundancy,

text: whenever

text: a

text: storage

text: node

text: fails,

text: it

text: is

text: instantly

text: replaced

text: with

text: a

text: newcomer

text: node

text: that

text: is

text: randomly

text: chosen

text: from

text: the

text: empty

text: nodes

text: present

text: in

text: the

text: cluster.

text: This

text: newcomer

text: node

text: contacts

text: any

text: d

text: n

text: storage

text: nodes,

text: downloads

text: β

text: units

text: of

text: data

text: from

text: each

text: and

text: stores

text: α

text: units

text: of

text: data.

text: Note

text: that

text: the

text: new

text: content

text: in

text: the

text: newcomer

text: node

text: does

text: not

text: need

text: to

text: be

text: exactly

text: the

text: data

text: that

text: were

text: lost

text: in

text: the

text: failed

text: node.

text: Hence,

text: we

text: consider

text: functional

text: repair,

text: which

text: ensures

text: that

text: both

text: the

text: MDS

text: and

text: the

text: regeneration

text: property

text: hold

text: after

text: an

text: arbitrary

text: failure.

text: Throughout

text: this

text: paper,

text: we

text: assume

text: instant

text: repair

text: after

text: failures

text: so

text: that

text: no

text: matter

text: which

text: coding

text: method

text: is

text: used,

text: there

text: are

text: always

text: n

text: caching

text: nodes

text: in

text: the

text: cluster

text: as

text: long

text: as

text: the

text: Markov

text: chain

text: in

text: Figure

text: never

text: goes

text: to

text: a

text: state

text: lower

text: than

text: n,

text: which

text: we

text: deem

text: a

text: valid

text: assumption

text: as

text: we

text: only

text: investigate

text: the

text: case

text: n

text: m,

text: and

text: thus

text: the

text: probability

text: of

text: ﬁnding

text: the

text: chain

text: in

text: small

text: states

text: is

text: extremely

text: A

text: DSS

text: is

text: determined

text: by

text: the

text: tuple

text: (n,

text: k,

text: d,

text: α,

text: γ),

text: whereof

text: the

text: triple

text: (n,

text: k,

text: d)

text: consists

text: of

text: the

text: storage

text: degree,

text: reconstruction

text: degree

text: and

text: repair

text: degree.

text: In

text: other

text: words,

text: reconstructing

text: the

text: data

text: ﬁle

text: requires

text: contacting

text: k

text: out

text: of

text: total

text: n

text: storage

text: nodes,

text: while

text: repairing

text: the

text: contents

text: of

text: a

text: lost

text: node

text: requires

text: contacting

text: d

text: nodes.

text: In

text: addition,

text: the

text: parameter

text: tuple

text: (α,

text: γ)

text: consists

text: of

text: the

text: fragment

text: size

text: α

text: stored

text: in

text: each

text: of

text: the

text: n

text: storage

text: nodes,

text: and

text: the

text: repair

text: bandwidth

text: γ,

text: that

text: is

text: the

text: total

text: number

text: of

text: units

text: of

text: data

text: that

text: a

text: newcomer

text: needs

text: to

text: download

text: for

text: repairing

text: a

text: lost

text: node.

text: Note

text: that

text: when

text: repairing,

text: each

text: storage

text: node

text: involved

text: in

text: the

text: repair

text: process

text: transmits

text: β

text: units

text: of

text: data

text: to

text: the

text: newcomer

text: node,

text: so

text: that

text: γ

text: dβ.

text: A

text: given

text: tuple

text: of

text: parameters

text: (n,

text: k,

text: d,

text: α,

text: γ)

text: is

text: feasible

text: if

text: a

text: code

text: with

text: such

text: α

text: and

text: γ

text: exists.

text: For

text: a

text: result

text: on

text: the

text: existence

text: of

text: feasible

text: parameter

text: tuples,

text: we

text: refer

text: to

text: Thm.

text: More

text: importantly,

text: there

text: is

text: a

text: natural

text: tradeoff

text: between

text: α

text: and

text: γ

text: given

text: by

text: a

text: piecewise

text: linear

text: function.

text: Codes

text: lying

text: on

text: this

text: tradeoff

text: curve

text: are

text: called

text: regenerating

text: codes.

text: Hence,

text: regenerating

text: codes

text: offer

text: an

text: optimal

text: tradeoff

text: between

text: storage

text: space

text: consumption

text: and

text: repair

text: bandwidth,

text: while

text: maintaining

text: the

text: MDS

text: property.

text: Furthermore,

text: any

text: d

text: nodes

text: can

text: be

text: contacted

text: to

text: resurrect

text: a

text: lost

text: node

text: while

text: maintaining

text: these

text: properties

text: after

text: repairs.

text: Hence,

text: regenerating

text: codes

text: are

text: an

text: attractive

text: choice.

text: In

text: this

text: work,

text: we

text: consider

text: two

text: types

text: of

text: regenerating

text: codes:

text: codes

text: attaining

text: one

text: of

text: the

text: two

text: extremal

text: points,

text: i.e.,

text: the

text: points

text: where

text: either

text: the

text: storage

text: space

text: consumption

text: or

text: repair

text: bandwidth

text: is

text: example,

text: if

text: m

text: and

text: n

text: values

text: which

text: we

text: will

text: later

text: use

text: in

text: our

text: simulations,

text: the

text: probability

text: that

text: the

text: number

text: of

text: nodes

text: in

text: the

text: cluster

text: drops

text: to

text: n

text: or

text: below

text: is

text: approximately


text: 10 For further details on circle intersection calculations, see e.g. [32]. Now let P (t) be a node in the cluster, where t denotes its distance from the origin of the disk. Using the computed area of intersection, we can ﬁnd the probabilities needed for our calculations. Of interest for our purposes is the expected distance between the node P (t) and it’s qth nearest node out of n nodes, which can be computed as (see [33] for further details) (cid:32) (cid:33) (cid:90) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:88) r − − q 1 n A(r, x, t) i − A(r, x, t) n i E(n, q, r, t) = (cid:32) 1 (cid:33)dx (cid:90) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:88) i πr2 πr2 i=0 0 r+t − − q 1 n A(x, r, t) i − A(x, r, t) n i + 1 dx. i πr2 πr2 i=0 r Moreover, we are interested in the expected value of the Γth power of the distance between P (t) and its qth nearest neighbor, which becomes (cid:32) (cid:33) (cid:90) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:88)  r − − E − q 1 n A(r, x, t) i − A(r, x, t) n i (n, q, r, t) = Γ xΓ (cid:32)1 1 (cid:33) dx Γ (cid:90) (cid:88) (cid:18) (cid:19)i (cid:18) πr2 (cid:19) (cid:18) πr2 (cid:19) 0 i=0  r+t − − − q 1 n A(x, r, t) i − A(x, r, t) n i + xΓ 1 1 dx , i πr2 πr2 i=0 r the expected value of which is given by (cid:90) r 2 E L (q, n) = t (n, q, r, t)dt, (5) r,Γ r2 Γ 0 ≤ ≤ where we have used the probability density function f(t) = 2t (0 t r) corresponding r2 to the random variable representing the distance between a randomly chosen point in a disk of radius r and the center of the disk. Lastly, to measure the performance of simple caching, we ﬁnd the expectation of the Γth power of the distance from a node in the cluster to the base BS station by integrating the complementary cumulative density function of the distance: ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: For

text: further

text: details

text: on

text: circle

text: intersection

text: calculations,

text: see

text: e.g.

text: Now

text: let

text: P

text: (t)

text: be

text: a

text: node

text: in

text: the

text: cluster,

text: where

text: t

text: denotes

text: its

text: distance

text: from

text: the

text: origin

text: of

text: the

text: disk.

text: Using

text: the

text: computed

text: area

text: of

text: intersection,

text: we

text: can

text: ﬁnd

text: the

text: probabilities

text: needed

text: for

text: our

text: calculations.

text: Of

text: interest

text: for

text: our

text: purposes

text: is

text: the

text: expected

text: distance

text: between

text: the

text: node

text: P

text: (t)

text: and

text: it’s

text: qth

text: nearest

text: node

text: out

text: of

text: n

text: nodes,

text: which

text: can

text: be

text: computed

text: as

text: (see

text: for

text: further

text: details)

label: equation

text: r

text: q

text: n

text: A(r,

text: x,

text: t)

text: i

text: A(r,

text: x,

text: t)

text: n

text: i

text: E(n,

text: q,

text: r,

text: t)

text: i

text: r+t

text: q

text: n

text: A(x,

text: r,

text: t)

text: i

text: A(x,

text: r,

text: t)

text: n

text: i

text: dx.

text: i

text: r

text: Moreover,

text: we

text: are

text: interested

text: in

text: the

text: expected

text: value

text: of

text: the

text: Γth

text: power

text: of

text: the

text: distance

text: between

text: P

text: (t)

text: and

text: its

text: qth

text: nearest

text: neighbor,

text: which

text: becomes

text: r

text: E

text: q

text: n

text: A(r,

text: x,

text: t)

text: i

text: A(r,

text: x,

text: t)

text: n

text: i

text: (n,

text: q,

text: r,

text: t)

text: Γ

text: xΓ

text: dx

text: Γ

text: r+t

text: q

text: n

text: A(x,

text: r,

text: t)

text: i

text: A(x,

text: r,

text: t)

text: n

text: i

text: xΓ

text: dx

text: i

text: r

text: the

text: expected

text: value

text: of

text: which

text: is

text: given

text: by

text: r

text: E

text: L

text: (q,

text: n)

text: t

text: (n,

text: q,

text: r,

text: t)dt,

text: r,Γ

text: Γ

text: where

text: we

text: have

text: used

text: the

text: probability

text: density

text: function

text: f(t)

text: t

text: r)

text: corresponding

text: to

text: the

text: random

text: variable

text: representing

text: the

text: distance

text: between

text: a

text: randomly

text: chosen

text: point

text: in

text: a

text: disk

text: of

text: radius

text: r

text: and

text: the

text: center

text: of

text: the

text: disk.

text: Lastly,

text: to

text: measure

text: the

text: performance

text: of

text: simple

text: caching,

text: we

text: ﬁnd

text: the

text: expectation

text: of

text: the

text: Γth

text: power

text: of

text: the

text: distance

text: from

text: a

text: node

text: in

text: the

text: cluster

text: to

text: the

text: base

text: BS

text: station

text: by

text: integrating

text: the

text: complementary

text: cumulative

text: density

text: function

text: of

text: the

text: distance:

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: CARPENTIER LOCATELLI one, since this closes a gap that had been open since the introduction of the ﬁxed conﬁdence best arm identiﬁcation problem by Audibert and Bubeck (2010). Acknowledgement This work is supported by the DFG’s Emmy Noether grant MuSyAD (CA 1488/1-1). References Jean-Yves Audibert and Se´bastien Bubeck. Best arm identiﬁcation in multi-armed bandits. In COLT - 23rd Conference on Learning Theory - 2010, 2010. Se´bastien Bubeck, Tengyao Wang, and Nitin Viswanathan. Multiple identiﬁcations in multi-armed bandits. Se´bastien Bubeck, Re´mi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits prob- lems. In Algorithmic Learning Theory, pages 23–37. Springer, 2009. Florentina Bunea, Alexandre Tsybakov, Marten Wegkamp, et al. Sparsity oracle inequalities for the lasso. Electronic Journal of Statistics, 1:169–194, 2007. Wei Cao, Jian Li, Yufei Tao, and Zhize Li. On top-k selection in multi-armed bandits and hidden bipartite graphs. In Advances in Neural Information Processing Systems, pages 1036–1044, 2015. Lijie Chen and Jian Li. On the optimal sample complexity for best arm identiﬁcation. arXiv preprint arXiv:1511.03774, 2015. Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure explo- ration of multi-armed bandits. In Advances in Neural Information Processing Systems, pages 379–387, 2014. Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory, pages 255–270. Springer, 2002. Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identiﬁcation: A uniﬁed approach to ﬁxed budget and ﬁxed conﬁdence. In Advances in Neural Information Pro- cessing Systems, pages 3212–3220, 2012. Kevin Jamieson and Robert Nowak. Best-arm identiﬁcation algorithms for multi-armed bandits in the ﬁxed conﬁdence setting. In Information Sciences and Systems (CISS), 2014 48th Annual Conference on, pages 1–6. IEEE, 2014. Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sebastien Bubeck. On ﬁnding the largest mean among many. arXiv preprint arXiv:1306.3917, 2013a. Kevin Jamieson, Matthew Malloy, Robert Nowak, and Se´bastien Bubeck. lil’ucb: An optimal exploration algorithm for multi-armed bandits. arXiv preprint arXiv:1312.7308, 2013b. Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In Proceedings of the 29th International Conference on Machine Learning (ICML-12), pages 655–662, 2012. 14

text: CARPENTIER

text: LOCATELLI

text: one,

text: since

text: this

text: closes

text: a

text: gap

text: that

text: had

text: been

text: open

text: since

text: the

text: introduction

text: of

text: the

text: ﬁxed

text: conﬁdence

text: best

text: arm

text: identiﬁcation

text: problem

text: by

text: Audibert

text: and

text: Bubeck

text: Acknowledgement

text: This

text: work

text: is

text: supported

text: by

text: the

text: DFG’s

text: Emmy

text: Noether

text: grant

text: MuSyAD

text: (CA

text: References

label: reference

text: Jean-Yves

text: Audibert

text: and

text: Se´bastien

text: Bubeck.

text: Best

text: arm

text: identiﬁcation

text: in

text: multi-armed

text: bandits.

text: In

text: COLT

text: Conference

text: on

text: Learning

text: Theory

text: Se´bastien

text: Bubeck,

text: Tengyao

text: Wang,

text: and

text: Nitin

text: Viswanathan.

text: Multiple

text: identiﬁcations

text: in

text: multi-armed

text: bandits.

text: Se´bastien

text: Bubeck,

text: Re´mi

text: Munos,

text: and

text: Gilles

text: Stoltz.

text: Pure

text: exploration

text: in

text: multi-armed

text: bandits

text: prob-

text: lems.

text: In

text: Algorithmic

text: Learning

text: Theory,

text: pages

text: Springer,

text: Florentina

text: Bunea,

text: Alexandre

text: Tsybakov,

text: Marten

text: Wegkamp,

text: et

text: al.

text: Sparsity

text: oracle

text: inequalities

text: for

text: the

text: lasso.

text: Electronic

text: Journal

text: of

text: Statistics,

text: Wei

text: Cao,

text: Jian

text: Li,

text: Yufei

text: Tao,

text: and

text: Zhize

text: Li.

text: On

text: top-k

text: selection

text: in

text: multi-armed

text: bandits

text: and

text: hidden

text: bipartite

text: graphs.

text: In

text: Advances

text: in

text: Neural

text: Information

text: Processing

text: Systems,

text: pages

text: Lijie

text: Chen

text: and

text: Jian

text: Li.

text: On

text: the

text: optimal

text: sample

text: complexity

text: for

text: best

text: arm

text: identiﬁcation.

text: arXiv

text: preprint

text: Shouyuan

text: Chen,

text: Tian

text: Lin,

text: Irwin

text: King,

text: Michael

text: R

text: Lyu,

text: and

text: Wei

text: Chen.

text: Combinatorial

text: pure

text: explo-

text: ration

text: of

text: multi-armed

text: bandits.

text: In

text: Advances

text: in

text: Neural

text: Information

text: Processing

text: Systems,

text: pages

text: Eyal

text: Even-Dar,

text: Shie

text: Mannor,

text: and

text: Yishay

text: Mansour.

text: Pac

text: bounds

text: for

text: multi-armed

text: bandit

text: and

text: markov

text: decision

text: processes.

text: In

text: Computational

text: Learning

text: Theory,

text: pages

text: Springer,

text: Victor

text: Gabillon,

text: Mohammad

text: Ghavamzadeh,

text: and

text: Alessandro

text: Lazaric.

text: Best

text: arm

text: identiﬁcation:

text: A

text: uniﬁed

text: approach

text: to

text: ﬁxed

text: budget

text: and

text: ﬁxed

text: conﬁdence.

text: In

text: Advances

text: in

text: Neural

text: Information

text: Pro-

text: cessing

text: Systems,

text: pages

text: Kevin

text: Jamieson

text: and

text: Robert

text: Nowak.

text: Best-arm

text: identiﬁcation

text: algorithms

text: for

text: multi-armed

text: bandits

text: in

text: the

text: ﬁxed

text: conﬁdence

text: setting.

text: In

text: Information

text: Sciences

text: and

text: Systems

text: (CISS),

text: Annual

text: Conference

text: on,

text: pages

text: IEEE,

text: Kevin

text: Jamieson,

text: Matthew

text: Malloy,

text: Robert

text: Nowak,

text: and

text: Sebastien

text: Bubeck.

text: On

text: ﬁnding

text: the

text: largest

text: mean

text: among

text: many.

text: arXiv

text: preprint

text: Kevin

text: Jamieson,

text: Matthew

text: Malloy,

text: Robert

text: Nowak,

text: and

text: Se´bastien

text: Bubeck.

text: lil’ucb:

text: An

text: optimal

text: exploration

text: algorithm

text: for

text: multi-armed

text: bandits.

text: arXiv

text: preprint

text: Shivaram

text: Kalyanakrishnan,

text: Ambuj

text: Tewari,

text: Peter

text: Auer,

text: and

text: Peter

text: Stone.

text: Pac

text: subset

text: selection

text: in

text: stochastic

text: multi-armed

text: bandits.

text: In

text: Proceedings

text: of

text: the

text: International

text: Conference

text: on

text: Machine

text: Learning

text: pages


text: FIXED BUDGET BEST ARM IDENTIFICATION Fixed budget setting The ﬁxed budget has also been studied intensively, but to the best of our knowledge, an important gap still remains between upper and lower bound results. The best known (up to constants) upper bounds are in the paper Audibert and Bubeck (2010), while the best lower bound can be found in Kaufmann et al. (2014), and they are as follows. • Upper bound : Assume that an upper bound a on the complexity H of the problem is known to the learner. There exists an algorithm that, at the end of the budget T , fails selecting an (cid:16) (cid:17) (cid:16) (cid:17) optimal arm with probability upper bounded as − P kˆ (cid:54)∈ A∗ ≤ 2T K exp − T K . T 18a Even if no upper bound on the complexity H is known to the learner, there exists an algorithm (cid:16) (cid:17) (cid:16) (cid:17) that, at the end of the budget T , fails selecting an optimal arm with probability upper bounded as − − P kˆ (cid:54)∈ A∗ ≤ K(K 1) exp − T K . T 2 log(2K)H 2 • Lower bound : Even if an upper bound on H, H is known to the learner, any algorithm, at (cid:16) (cid:17) 2 (cid:16) (cid:17) the end of the budget T , fails selecting an optimal arm with probability lower bounded as P kˆ (cid:54)∈ A∗ ≥ exp − 4T . T H Several papers exhibit other strategies for the ﬁxed budget problem (in general in combination with a ﬁxed conﬁdence strategy), see e.g. Gabillon et al. (2012); Jamieson et al. (2013b); Karnin et al. (2013), but their theoretical results do not outperform the ones recalled here and coming from Audibert and Bubeck (2010). Note that these results highlight a gap between upper and lower bounds. In the case where an upper bound a on the complexity H is known to the learner, the gap is related to the distance between a and H. Beyond the fact that H is always smaller than H, we 2 would like to emphasize here that if the upper bound a on H is not tight enough, the algorithm’s performance will be sub-optimal compared to the hypothetical performance of an oracle algorithm that has access to H - as the non-oracle algorithm will over explore. Now in the case where one does not want to assume the knowledge of H, the gap between known upper and lower bounds becomes even larger and is related to the distance between H and log(2K)H . Unlike in the ﬁxed conﬁdence 2 setting, this gap remains also for T large (which corresponds to δ small in the ﬁxed conﬁdence setting). We would like to emphasize that although this gap is often belittled in the literature, as it is “only” a a gap up to a log(K) factor, this log(K) factor has an effect in the exponential, and in some sense it is much larger than the gap that was remaining in the ﬁxed conﬁdence setting after the (cid:16) (cid:17) seminal papers Even-Dar et al. (2002); Mannor and Tsitsiklis (2004), and over which many valuable works have further improved. Indeed, in order to compare the bounds in the ﬁxed conﬁdence setting with the bounds in the ﬁxed budget setting, one can set δ := P kˆ (cid:54)∈ A∗ , and compute the ﬁxed T budget T for which a precision of at least δ is achieved for both upper and lower bounds. Inverting the upper bounds in the ﬁxed budget setting, one would get the upper bounds on T (cid:46) (cid:46) T a log(KT/δ), or T H log(K) log(K/δ)), 2 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FIXED

text: BUDGET

text: BEST

text: ARM

text: IDENTIFICATION

text: Fixed

text: budget

text: setting

text: The

text: ﬁxed

text: budget

text: has

text: also

text: been

text: studied

text: intensively,

text: but

text: to

text: the

text: best

text: of

text: our

text: knowledge,

text: an

text: important

text: gap

text: still

text: remains

text: between

text: upper

text: and

text: lower

text: bound

text: results.

text: The

text: best

text: known

text: (up

text: to

text: constants)

text: upper

text: bounds

text: are

text: in

text: the

text: paper

text: Audibert

text: and

text: Bubeck

text: while

text: the

text: best

text: lower

text: bound

text: can

text: be

text: found

text: in

text: Kaufmann

text: et

text: al.

text: and

text: they

text: are

text: as

text: follows.

label: list

text: Upper

text: bound

text: Assume

text: that

text: an

text: upper

text: bound

text: a

text: on

text: the

text: complexity

text: H

text: of

text: the

text: problem

text: is

text: known

text: to

text: the

text: learner.

text: There

text: exists

text: an

text: algorithm

text: that,

text: at

text: the

text: end

text: of

text: the

text: budget

text: T

text: fails

text: selecting

text: an

text: optimal

text: arm

text: with

text: probability

text: upper

text: bounded

text: as

text: P

text: kˆ

text: A∗

text: K

text: exp

text: T

text: K

text: T

text: Even

text: if

text: no

text: upper

text: bound

text: on

text: the

text: complexity

text: H

text: is

text: known

text: to

text: the

text: learner,

text: there

text: exists

text: an

text: algorithm

text: that,

text: at

text: the

text: end

text: of

text: the

text: budget

text: T

text: fails

text: selecting

text: an

text: optimal

text: arm

text: with

text: probability

text: upper

text: bounded

text: as

text: P

text: kˆ

text: A∗

text: K(K

text: exp

text: T

text: K

text: T

text: Lower

text: bound

text: Even

text: if

text: an

text: upper

text: bound

text: on

text: H,

text: H

text: is

text: known

text: to

text: the

text: learner,

text: any

text: algorithm,

text: at

text: the

text: end

text: of

text: the

text: budget

text: T

text: fails

text: selecting

text: an

text: optimal

text: arm

text: with

text: probability

text: lower

text: bounded

text: as

text: P

text: kˆ

text: A∗

text: exp

text: T

text: H

text: Several

text: papers

text: exhibit

text: other

text: strategies

text: for

text: the

text: ﬁxed

text: budget

text: problem

text: (in

text: general

text: in

text: combination

text: with

text: a

text: ﬁxed

text: conﬁdence

text: strategy),

text: see

text: e.g.

text: Gabillon

text: et

text: al.

text: Jamieson

text: et

text: al.

text: Karnin

text: et

text: al.

text: but

text: their

text: theoretical

text: results

text: do

text: not

text: outperform

text: the

text: ones

text: recalled

text: here

text: and

text: coming

text: from

text: Audibert

text: and

text: Bubeck

text: Note

text: that

text: these

text: results

text: highlight

text: a

text: gap

text: between

text: upper

text: and

text: lower

text: bounds.

text: In

text: the

text: case

text: where

text: an

text: upper

text: bound

text: a

text: on

text: the

text: complexity

text: H

text: is

text: known

text: to

text: the

text: learner,

text: the

text: gap

text: is

text: related

text: to

text: the

text: distance

text: between

text: a

text: and

text: H.

text: Beyond

text: the

text: fact

text: that

text: H

text: is

text: always

text: smaller

text: than

text: H,

text: we

text: would

text: like

text: to

text: emphasize

text: here

text: that

text: if

text: the

text: upper

text: bound

text: a

text: on

text: H

text: is

text: not

text: tight

text: enough,

text: the

text: algorithm’s

text: performance

text: will

text: be

text: sub-optimal

text: compared

text: to

text: the

text: hypothetical

text: performance

text: of

text: an

text: oracle

text: algorithm

text: that

text: has

text: access

text: to

text: H

text: as

text: the

text: non-oracle

text: algorithm

text: will

text: over

text: explore.

text: Now

text: in

text: the

text: case

text: where

text: one

text: does

text: not

text: want

text: to

text: assume

text: the

text: knowledge

text: of

text: H,

text: the

text: gap

text: between

text: known

text: upper

text: and

text: lower

text: bounds

text: becomes

text: even

text: larger

text: and

text: is

text: related

text: to

text: the

text: distance

text: between

text: H

text: and

text: Unlike

text: in

text: the

text: ﬁxed

text: conﬁdence

text: setting,

text: this

text: gap

text: remains

text: also

text: for

text: T

text: large

text: (which

text: corresponds

text: to

text: δ

text: small

text: in

text: the

text: ﬁxed

text: conﬁdence

text: setting).

text: We

text: would

text: like

text: to

text: emphasize

text: that

text: although

text: this

text: gap

text: is

text: often

text: belittled

text: in

text: the

text: literature,

text: as

text: it

text: is

text: “only”

text: a

text: a

text: gap

text: up

text: to

text: a

text: log(K)

text: factor,

text: this

text: log(K)

text: factor

text: has

text: an

text: effect

text: in

text: the

text: exponential,

text: and

text: in

text: some

text: sense

text: it

text: is

text: much

text: larger

text: than

text: the

text: gap

text: that

text: was

text: remaining

text: in

text: the

text: ﬁxed

text: conﬁdence

text: setting

text: after

text: the

text: seminal

text: papers

text: Even-Dar

text: et

text: al.

text: Mannor

text: and

text: Tsitsiklis

text: and

text: over

text: which

text: many

text: valuable

text: works

text: have

text: further

text: improved.

text: Indeed,

text: in

text: order

text: to

text: compare

text: the

text: bounds

text: in

text: the

text: ﬁxed

text: conﬁdence

text: setting

text: with

text: the

text: bounds

text: in

text: the

text: ﬁxed

text: budget

text: setting,

text: one

text: can

text: set

text: δ

text: P

text: kˆ

text: A∗

text: and

text: compute

text: the

text: ﬁxed

text: T

text: budget

text: T

text: for

text: which

text: a

text: precision

text: of

text: at

text: least

text: δ

text: is

text: achieved

text: for

text: both

text: upper

text: and

text: lower

text: bounds.

text: Inverting

text: the

text: upper

text: bounds

text: in

text: the

text: ﬁxed

text: budget

text: setting,

text: one

text: would

text: get

text: the

text: upper

text: bounds

text: on

text: T

text: T

text: a

text: log(KT/δ),

text: or

text: T

text: H

text: log(K)

text: log(K/δ)),

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:88) SPCE = y 2/DPCE, A = {α ∈ A | α > 0, α (cid:54) = 0} (40) i α i i j=i ∈A α i and (cid:88) ST,PCE = y 2/DPCE, AT = {α ∈ A | α > 0}. (41) i α i i ∈A α T i 5 Sobol’ sensitivity analysis using low-rank tensor approx- imations 5.1 Formulation and construction of low-rank tensor approximations Let us consider again the mapping in Eq. (1). A rank-one function of the input vector X has the form: (cid:89) M w(X) = v(i)(X ), (42) i i=1 where v(i) denotes a univariate function of X . A representation of M as a sum of a ﬁnite i number of rank-one functions constitutes a canonical decomposition with rank equal to the number of rank-one components. Naturally, of interest are representations where the exact response is approximated with suﬃcient accuracy by using a relatively small number of terms, leading to the name low-rank approximations. (cid:32) (cid:33) A meta-model of Y = M(X) belonging to the class of LRA can be written as: (cid:88) (cid:89) R M Y LRA = MLRA(X) = b v(i)(X ) , (43) l l i l=1 i=1 (i) where R is the rank of the approximation, v is a univariate function of X in the l-th rank- l i one component and {b , l = 1, . . . , R} are scalars that can be viewed as normalizing constants. l (i) In order to obtain a representation in terms of polynomial functions, we expand v onto a l polynomial basis that is orthonormal with respect to f , i.e. satisﬁes the condition in Eq. (27). Xi This leads to the expression: (cid:88) pi (i) (i) (i) v (X ) = z P (X ), (44) l i k,l k i k=0 14

text: SPCE

text: y

text: A

text: {α

text: A

text: α

text: α

font: default

text: i

text: α

text: i

text: i

text: j=i

text: ∈A

text: α

text: i

text: and

text: ST,PCE

text: y

text: AT

text: {α

text: A

text: α

text: i

text: α

text: i

text: i

text: ∈A

text: α

text: T

text: i

label: section

text: Sobol’

text: sensitivity

text: analysis

text: using

text: low-rank

text: tensor

text: approx-

text: imations

text: Formulation

text: and

text: construction

text: of

text: low-rank

text: tensor

text: approximations

text: Let

text: us

text: consider

text: again

text: the

text: mapping

text: in

text: Eq.

text: A

text: rank-one

text: function

text: of

text: the

text: input

text: vector

text: X

text: has

text: the

text: form:

text: M

text: w(X)

text: v(i)(X

text: i

text: where

text: v(i)

text: denotes

text: a

text: univariate

text: function

text: of

text: X

text: A

text: representation

text: of

text: M

text: as

text: a

text: sum

text: of

text: a

text: ﬁnite

text: i

text: number

text: of

text: rank-one

text: functions

text: constitutes

text: a

text: canonical

text: decomposition

text: with

text: rank

text: equal

text: to

text: the

text: number

text: of

text: rank-one

text: components.

text: Naturally,

text: of

text: interest

text: are

text: representations

text: where

text: the

text: exact

text: response

text: is

text: approximated

text: with

text: suﬃcient

text: accuracy

text: by

text: using

text: a

text: relatively

text: small

text: number

text: of

text: terms,

text: leading

text: to

text: the

text: name

text: low-rank

text: approximations.

text: A

text: meta-model

text: of

text: Y

text: M(X)

text: belonging

text: to

text: the

text: class

text: of

text: LRA

text: can

text: be

text: written

text: as:

text: R

text: M

text: Y

text: LRA

text: MLRA(X)

text: b

text: v(i)(X

text: l

text: l

text: i

text: (i)

text: where

text: R

text: is

text: the

text: rank

text: of

text: the

text: approximation,

text: v

text: is

text: a

text: univariate

text: function

text: of

text: X

text: in

text: the

text: l-th

text: rank-

text: l

text: i

text: one

text: component

text: and

text: {b

text: l

text: R}

text: are

text: scalars

text: that

text: can

text: be

text: viewed

text: as

text: normalizing

text: constants.

text: l

text: (i)

text: In

text: order

text: to

text: obtain

text: a

text: representation

text: in

text: terms

text: of

text: polynomial

text: functions,

text: we

text: expand

text: v

text: onto

text: a

text: l

text: polynomial

text: basis

text: that

text: is

text: orthonormal

text: with

text: respect

text: to

text: f

text: i.e.

text: satisﬁes

text: the

text: condition

text: in

text: Eq.

text: Xi

text: This

text: leads

text: to

text: the

text: expression:

text: pi

text: (i)

text: (i)

text: (i)

text: v

text: (X

text: z

text: P

text: (X

text: l

text: i

text: k,l

text: k

text: i


text: Rai, P. (2014). Sparse Low Rank Approximation of Multivariate Functions – Applications in uncertainty quantiﬁcation. Ph. D. thesis, Ecole Centrale Nantes, France. Saltelli, A. (2002). Making best use of model evaluations to compute sensitivity indices. Comput. Phys. Comm. 145, 280–297. Saltelli, A., P. Annoni, V. Azzini, F. Campolongo, M. Ratto, and S. Tarantola (2010). Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index. Comput. Phys. Comm. 181, 259–270. Saltelli, A., M. Ratto, T. Andres, F. Campolongo, J. Cariboni, D. Gatelli, M. Saisana, and S. Tarantola (2008). Global Sensitivity Analysis – The Primer. Wiley. Saltelli, A., S. Tarantola, and K. Chan (1999). A quantitative, model independent method for global sensitivity analysis of model output. Technometrics 41(1), 39–56. Sobol’, I. (2001). Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates. Mathematics and Computers in Simulation 55(1-3), 271–280. Sobol’, I. and S. Kucherenko (2005). Global sensitivity indices for nonlinear mathematical mod- els. Review. Wilmott magazine 1, 56–61. Sobol’, I. and S. Kucherenko (2009). Derivative based global sensitivity measures and their link with global sensitivity indices. Math. Comput. Simul. 79(10), 3009–3017. Sobol’, I. M. (1993). Sensitivity estimates for nonlinear mathematical models. Math. Modeling & Comp. Exp. 1, 407–414. Sobol, I. M., S. Tarantola, D. Gatelli, S. S. Kucherenko, and W. Mauntz (2007). Estimating the approximation error when ﬁxing unessential factors in global sensitivity analysis. Reliab. Eng. Sys. Safety 92(7), 957–960. Storlie, C. B., L. P. Swiler, J. C. Helton, and C. J. Sallaberry (2009). Implementation and evaluation of nonparametric regression procedures for sensitivity analysis of computationally demanding models. Reliab. Eng. Sys. Safety 94, 1735–1763. Sudret, B. (2007). Uncertainty propagation and sensitivity analysis in mechanical models – contributions to structural reliability and stochastic spectral methods. Technical report. Ha- bilitation `a diriger des recherches, Universit´e Blaise Pascal, Clermont-Ferrand, France (229 pages). Sudret, B. (2008). Global sensitivity analysis using polynomial chaos expansions. Reliab. Eng. Sys. Safety 93, 964–979. 43

text: Rai,

text: P.

text: Sparse

text: Low

text: Rank

text: Approximation

text: of

text: Multivariate

text: Functions

text: Applications

text: in

text: uncertainty

text: quantiﬁcation.

text: Ph.

text: D.

text: thesis,

text: Ecole

text: Centrale

text: Nantes,

text: France.

text: Saltelli,

text: A.

text: Making

text: best

text: use

text: of

text: model

text: evaluations

text: to

text: compute

text: sensitivity

text: indices.

text: Comput.

text: Phys.

text: Comm.

text: Saltelli,

text: A.,

text: P.

text: Annoni,

text: V.

text: Azzini,

text: F.

text: Campolongo,

text: M.

text: Ratto,

text: and

text: S.

text: Tarantola

text: Variance

text: based

text: sensitivity

text: analysis

text: of

text: model

text: output.

text: Design

text: and

text: estimator

text: for

text: the

text: total

text: sensitivity

text: index.

text: Comput.

text: Phys.

text: Comm.

text: Saltelli,

text: A.,

text: M.

text: Ratto,

text: T.

text: Andres,

text: F.

text: Campolongo,

text: J.

text: Cariboni,

text: D.

text: Gatelli,

text: M.

text: Saisana,

text: and

text: S.

text: Tarantola

text: Global

text: Sensitivity

text: Analysis

text: The

text: Primer.

text: Wiley.

text: Saltelli,

text: A.,

text: S.

text: Tarantola,

text: and

text: K.

text: Chan

text: A

text: quantitative,

text: model

text: independent

text: method

text: for

text: global

text: sensitivity

text: analysis

text: of

text: model

text: output.

text: Technometrics

text: Sobol’,

text: I.

text: Global

text: sensitivity

text: indices

text: for

text: nonlinear

text: mathematical

text: models

text: and

text: their

text: Monte

text: Carlo

text: estimates.

text: Mathematics

text: and

text: Computers

text: in

text: Simulation

text: Sobol’,

text: I.

text: and

text: S.

text: Kucherenko

text: Global

text: sensitivity

text: indices

text: for

text: nonlinear

text: mathematical

text: mod-

text: els.

text: Review.

text: Wilmott

text: magazine

text: Sobol’,

text: I.

text: and

text: S.

text: Kucherenko

text: Derivative

text: based

text: global

text: sensitivity

text: measures

text: and

text: their

text: link

text: with

text: global

text: sensitivity

text: indices.

text: Math.

text: Comput.

text: Simul.

text: Sobol’,

text: I.

text: M.

text: Sensitivity

text: estimates

text: for

text: nonlinear

text: mathematical

text: models.

text: Math.

text: Modeling

text: Comp.

text: Exp.

text: Sobol,

text: I.

text: M.,

text: S.

text: Tarantola,

text: D.

text: Gatelli,

text: S.

text: S.

text: Kucherenko,

text: and

text: W.

text: Mauntz

text: Estimating

text: the

text: approximation

text: error

text: when

text: ﬁxing

text: unessential

text: factors

text: in

text: global

text: sensitivity

text: analysis.

text: Reliab.

text: Eng.

text: Sys.

text: Safety

text: Storlie,

text: C.

text: B.,

text: L.

text: P.

text: Swiler,

text: J.

text: C.

text: Helton,

text: and

text: C.

text: J.

text: Sallaberry

text: Implementation

text: and

text: evaluation

text: of

text: nonparametric

text: regression

text: procedures

text: for

text: sensitivity

text: analysis

text: of

text: computationally

text: demanding

text: models.

text: Reliab.

text: Eng.

text: Sys.

text: Safety

text: Sudret,

text: B.

text: Uncertainty

text: propagation

text: and

text: sensitivity

text: analysis

text: in

text: mechanical

text: models

text: contributions

text: to

text: structural

text: reliability

text: and

text: stochastic

text: spectral

text: methods.

text: Technical

text: report.

text: Ha-

text: bilitation

text: `a

text: diriger

text: des

text: recherches,

text: Universit´e

text: Blaise

text: Pascal,

text: Clermont-Ferrand,

text: France

text: pages).

text: Sudret,

text: B.

text: Global

text: sensitivity

text: analysis

text: using

text: polynomial

text: chaos

text: expansions.

text: Reliab.

text: Eng.

text: Sys.

text: Safety


text: (cid:18) (cid:90) (cid:19) · (cid:48) (cid:48) (cid:48) (cid:48) (cid:48) (cid:48) · Z(s) = (X, Y, R)(s) = Γ x + b(t + t , ν(t + t ), X(t ), γ(t , X(t )))dt + σB( ) (s), (3.12) 0 ∈ − F {F } P F s [0, T t], namely there is a system Ξ = (Ω, , , , B) on which is given a -adapted t (cid:48) (cid:48) F(cid:48) {Fs(cid:48)} P(cid:48) (cid:48) continuous process Z = (X, Y, R) solving the above equation and if Ξ = (Ω , , , , B ) F(cid:48) (cid:48) (cid:48) (cid:48) t(cid:48) is another system on which is given a -adapted continuous process Z = (X , Y , R ) solving s (cid:48) (cid:48) (cid:48) P◦ − P(cid:48)◦ (cid:48) − the above equation with (Z, X, B) replaced by (Z , X , B ) then Z 1 = (Z ) 1. Note also ∈ A that with α(s) = γ(s, X(s)), (α, Z) (Ξ, t, x, ν). We refer to the function γ as a feedback control and we call it an optimal feedback control for the stochastic control problem in (3.3) if V (t, x) = J (t, x, α, Z). ν ν The following result which is a consequence of Theorem 13.24 of [62] says that the HJB equa- tion (3.5) with BC (3.6) admits a unique classical solution which can be characterized as the value function V . Moreover, there exists an optimal feedback control with certain regularity ν ∈ properties. We follow the notation from [62]. Let for δ (0, 1], H be the collection of maps × → R δ ψ : (0, T ) (0, L) such that | − (cid:48) (cid:48) | ψ(t, x) ψ(t , x ) ∞ sup | − (cid:48)| | − (cid:48)| < . (cid:48) (cid:48) t t δ/2 + x x δ 0<t<t <T,0<x<x <L × Note that such a function can be continuously extended to [0, T ] [0, L] and we denote the extension by the same symbol. Also, let H be the collection of continuous real functions × (cid:55)→ 2+12 ψ on [0, T ] [0, L] such that x ψ(t, x) is twice continuously diﬀerentiable on (0, L) for all ∈ (cid:55)→ ∈ t (0, T ), t ψ(t, x) is continuously diﬀerentiable on (0, T ) for all x (0, L), the functions ψ, D ψ, Dψ D2ψ, t × are bounded on (0, T ) (0, L) and the functions D ψ, D2ψ are in H . t 1/2 ∈ M ∈ Proposition 3.1 Fix ν and suppose that Assumption 3.1 holds. Then V H and 0 ν 2+1 2 it is the unique solution of (3.5)–(3.6). Furthermore, with αˆ as introduced in Assumption 3.1, (cid:48) (cid:55)→ (cid:48) (cid:48) (cid:48) . the map (s, x ) αˆ(s, ν(s), x , DV (s, x )) is continuous and the feedback control γˆ(u, x ) = (cid:48) (cid:48) ν ∈ αˆ(u + t, ν(u + t), x , DV (u + t, x )) is an optimal feedback control for (3.3) for every t (0, T ). ν ⊗ P Moreover, any optimal control α for (3.3) satisﬁes α(u, ω) = γˆ(u, X(u, ω)), λt almost − T surely (a.s.), where λt denotes the Lebesgue measure on [0, T t]. T Proof: From [62, Theorem 13.24] and the paragraph following its statement it follows that (3.5)–(3.6) admits a solution in H . We remark that the key conditions needed to appeal 1 2+ 2 to this theorem are that | − (cid:48) (cid:48) | | − (cid:48) (cid:48) | y(t, ν(t)) y(t , ν(t )) + r(t, ν(t)) r(t , ν(t )) ∞ sup | − (cid:48)| < , (cid:48) t t 1/2 0<t<t <T ∈ ∞ and for each M (0, ) | − (cid:48) (cid:48) (cid:48) (cid:48) | H(t, ν(t), x, p) H(t , ν(t ), x , p ) ∞ sup | − (cid:48)| | − (cid:48)| | − (cid:48)| < . (cid:48)∈ (cid:48)∈ (cid:48)∈ − t t 1/2 + x x + p p t,t [0,T],x,x [0,L],p,p [ M,M], (cid:54) (cid:48) (cid:54) (cid:48) (cid:54) (cid:48) t=t ,x=x ,p=p 12 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Z(s)

text: (X,

text: Y,

text: R)(s)

text: Γ

text: x

text: b(t

text: t

text: ν(t

text: t

text: X(t

text: γ(t

text: X(t

text: )))dt

text: σB(

text: (s),

text: F

text: {F

text: P

text: F

text: s

text: T

text: t],

text: namely

text: there

text: is

text: a

text: system

text: Ξ

text: (Ω,

text: B)

text: on

text: which

text: is

text: given

text: a

text: -adapted

text: t

text: continuous

text: process

text: Z

text: (X,

text: Y,

text: R)

text: solving

text: the

text: above

text: equation

text: and

text: if

text: Ξ

text: (Ω

text: B

text: is

text: another

text: system

text: on

text: which

text: is

text: given

text: a

text: -adapted

text: continuous

text: process

text: Z

text: (X

text: Y

text: R

text: solving

text: s

text: P◦

text: the

text: above

text: equation

text: with

text: (Z,

text: X,

text: B)

text: replaced

text: by

text: (Z

text: X

text: B

text: then

text: Z

text: (Z

text: Note

text: also

text: A

text: that

text: with

text: α(s)

text: γ(s,

text: X(s)),

text: (α,

text: Z)

text: (Ξ,

text: t,

text: x,

text: ν).

text: We

text: refer

text: to

text: the

text: function

text: γ

text: as

text: a

text: feedback

text: control

text: and

text: we

text: call

text: it

text: an

text: optimal

text: feedback

text: control

text: for

text: the

text: stochastic

text: control

text: problem

text: in

text: if

text: V

text: (t,

text: x)

text: J

text: (t,

text: x,

text: α,

text: Z).

text: ν

text: ν

text: The

text: following

text: result

text: which

text: is

text: a

text: consequence

text: of

text: Theorem

text: of

text: says

text: that

text: the

text: HJB

text: equa-

text: tion

text: with

text: BC

text: admits

text: a

text: unique

text: classical

text: solution

text: which

text: can

text: be

text: characterized

text: as

text: the

text: value

text: function

text: V

text: Moreover,

text: there

text: exists

text: an

text: optimal

text: feedback

text: control

text: with

text: certain

text: regularity

text: ν

text: properties.

text: We

text: follow

text: the

text: notation

text: from

text: Let

text: for

text: δ

text: H

text: be

text: the

text: collection

text: of

text: maps

text: R

text: δ

text: ψ

text: T

text: L)

text: such

text: that

text: ψ(t,

text: x)

text: ψ(t

text: x

text: sup

text: t

text: t

text: x

text: x

text: δ

text: <L

text: Note

text: that

text: such

text: a

text: function

text: can

text: be

text: continuously

text: extended

text: to

text: T

text: L]

text: and

text: we

text: denote

text: the

text: extension

text: by

text: the

text: same

text: symbol.

text: Also,

text: let

text: H

text: be

text: the

text: collection

text: of

text: continuous

text: real

text: functions

text: ψ

text: on

text: T

text: L]

text: such

text: that

text: x

text: ψ(t,

text: x)

text: is

text: twice

text: continuously

text: diﬀerentiable

text: on

text: L)

text: for

text: all

text: t

text: T

text: t

text: ψ(t,

text: x)

text: is

text: continuously

text: diﬀerentiable

text: on

text: T

text: for

text: all

text: x

text: L),

text: the

text: functions

text: ψ,

text: D

text: ψ,

text: Dψ

text: t

text: are

text: bounded

text: on

text: T

text: L)

text: and

text: the

text: functions

text: D

text: ψ,

text: are

text: in

text: H

text: t

text: M

text: Proposition

text: Fix

text: ν

text: and

text: suppose

text: that

text: Assumption

text: holds.

text: Then

text: V

text: H

text: and

text: ν

text: it

text: is

text: the

text: unique

text: solution

text: of

text: Furthermore,

text: with

text: αˆ

text: as

text: introduced

text: in

text: Assumption

text: the

text: map

text: (s,

text: x

text: αˆ(s,

text: ν(s),

text: x

text: DV

text: (s,

text: x

text: is

text: continuous

text: and

text: the

text: feedback

text: control

text: γˆ(u,

text: x

text: ν

text: αˆ(u

text: t,

text: ν(u

text: t),

text: x

text: DV

text: (u

text: t,

text: x

text: is

text: an

text: optimal

text: feedback

text: control

text: for

text: for

text: every

text: t

text: T

text: ν

text: P

text: Moreover,

text: any

text: optimal

text: control

text: α

text: for

text: satisﬁes

text: α(u,

text: ω)

text: γˆ(u,

text: X(u,

text: ω)),

text: λt

text: almost

text: T

text: surely

text: (a.s.),

text: where

text: λt

text: denotes

text: the

text: Lebesgue

text: measure

text: on

text: T

text: t].

text: T

text: Proof:

text: From

text: Theorem

text: and

text: the

text: paragraph

text: following

text: its

text: statement

text: it

text: follows

text: that

text: admits

text: a

text: solution

text: in

text: H

text: We

text: remark

text: that

text: the

text: key

text: conditions

text: needed

text: to

text: appeal

text: to

text: this

text: theorem

text: are

text: that

text: y(t,

text: ν(t))

text: y(t

text: ν(t

text: r(t,

text: ν(t))

text: r(t

text: ν(t

text: sup

text: t

text: t

text: <T

text: and

text: for

text: each

text: M

text: H(t,

text: ν(t),

text: x,

text: p)

text: H(t

text: ν(t

text: x

text: p

text: sup

text: t

text: t

text: x

text: x

text: p

text: p

text: t,t

text: M,M],

text: t=t

text: ,x=x

text: ,p=p

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: M B Lemma 3.1 Let be a non-empty convex subset of a normed space . Let Φ be a continuous M K ⊂ M ∈ K mapping of into a compact set . Then Φ has a ﬁxed point, namely there exists x such that Φ(x) = x. B Proof of Theorem 3.1: We will apply Lemma 3.1 to the space of ﬁnite signed measures C on ([0, T ] : [0, L]) wh(cid:40)ic(cid:12)(cid:12)h(cid:90) is equipped with the(cid:12)(cid:12)Kantorovich-Rubinstein norm(cid:41) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:107) (cid:107) ∈ C ∈ B ν = sup F (ω)dν(ω) : F Lip ( ([0, T ] : [0, L])) , ν . KR C 1 ([0,T]:[0,L]) P The distance driven by the norm, restricted to , coincides with the Wasserstein’s T,L distance of order 1 (see [68, Remark 6.5]), which due to compactness of [0, L] generates the P same topology on as that for weak convergence. T,L M We now introduce a mapping Φ on the non-empty and convex set that satisﬁes the 0 conditions stated in Lemma 3.1. ∈ M Deﬁnition of Φ. For ν , let α denote the optimal feedback control γˆ for (3.3) (with 0 ν t = 0) given through Proposition 3.1. Let Zν = (Xν, Y ν, Rν) denote the unique weak solution F {F } P of (3.12) with γ replaced with α given on some system Ξ = (Ω, , , , B). Deﬁne Φ(ν) = P ◦ − ν t (Xν) 1. M ∈ M ≤ ≤ Invariance of . For ν and 0 s t < T 0 0 (cid:18) (cid:19) ≤ E| − | W (Φ(ν)(t), Φ(ν)(s)) Xν(t) Xν(s) (3.17) 1 ≤ { } − E | − | c max c , σ (t s) + sup B(u) B(s) S B ≤ ≤ s u t ≤ − 4Cˆ(t s)1/2, . { } where Cˆ = c max c , σ , and the last inequality uses Doob’s maximal inequality. This S∈ M B ∈ M shows that Φ(ν) for all ν . 0 M 0 P M We now show that Φ( ) is contained in a compact set in , i.e. Φ( ) is relatively 0 T,L 0 compact. M ∈ C R Relative compactness of Φ( ). For f ([0, T ] : ) and δ > 0, let 0 | − | (cid:36) (δ) = sup f(t) f(s) . f ∈ | − |≤ s,t [0,T]: t s δ ∈ M Then for ε, δ, (cid:37) > 0 and ν , similar to the estimate in (3.17), 0 ≥ ≤ 1E(cid:32) | − | (cid:33) Φ(ν)(Xν : (cid:36) (δ) (cid:37)) sup Xν(t) Xν(s) Xν (cid:37) ≤ ≤ ≤ ≤ 0 s t s+δ T ≤ Cˆ E | − | δ + sup sup B(u) B(s) (cid:37) ≤ ≤ ≤ ≤ ≤ ≤ 0 s t s+δ T s u t ≤ Cˆ E (δ + (cid:36) (δ)). B (cid:37) 15 ##LTLine## ##LTLine## ##LTLine##

text: M

text: B

text: Lemma

text: Let

text: be

text: a

text: non-empty

text: convex

text: subset

text: of

text: a

text: normed

text: space

text: Let

text: Φ

text: be

text: a

text: continuous

text: M

text: K

text: M

text: K

text: mapping

text: of

text: into

text: a

text: compact

text: set

text: Then

text: Φ

text: has

text: a

text: ﬁxed

text: point,

text: namely

text: there

text: exists

text: x

text: such

text: that

text: Φ(x)

text: x.

text: B

text: Proof

text: of

text: Theorem

text: We

text: will

text: apply

text: Lemma

text: to

text: the

text: space

text: of

text: ﬁnite

text: signed

text: measures

text: C

text: on

text: T

text: L])

text: is

text: equipped

text: with

text: C

text: B

text: ν

text: sup

text: F

text: (ω)dν(ω)

text: F

text: Lip

text: T

text: L]))

text: ν

text: KR

text: C

text: P

text: The

text: distance

text: driven

text: by

text: the

text: norm,

text: restricted

text: to

text: coincides

text: with

text: the

text: Wasserstein’s

text: T,L

text: distance

text: of

text: order

text: (see

text: Remark

text: which

text: due

text: to

text: compactness

text: of

text: L]

text: generates

text: the

text: P

text: same

text: topology

text: on

text: as

text: that

text: for

text: weak

text: convergence.

text: T,L

text: M

text: We

text: now

text: introduce

text: a

text: mapping

text: Φ

text: on

text: the

text: non-empty

text: and

text: convex

text: set

text: that

text: satisﬁes

text: the

text: conditions

text: stated

text: in

text: Lemma

text: M

text: Deﬁnition

text: of

text: Φ.

text: For

text: ν

text: let

text: α

text: denote

text: the

text: optimal

text: feedback

text: control

text: γˆ

text: for

text: (with

text: ν

text: t

text: given

text: through

text: Proposition

text: Let

text: Zν

text: (Xν,

text: Y

text: ν,

text: Rν)

text: denote

text: the

text: unique

text: weak

text: solution

text: F

text: {F

text: P

text: of

text: with

text: γ

text: replaced

text: with

text: α

text: given

text: on

text: some

text: system

text: Ξ

text: (Ω,

text: B).

text: Deﬁne

text: Φ(ν)

text: P

text: ν

text: t

text: (Xν)

text: M

text: M

text: Invariance

text: of

text: For

text: ν

text: and

text: s

text: t

text: T

text: E|

text: W

text: (Φ(ν)(t),

text: Φ(ν)(s))

text: Xν(t)

text: Xν(s)

text: E

text: c

text: max

text: c

text: σ

text: (t

text: s)

text: sup

text: B(u)

text: B(s)

text: S

text: B

text: s

text: u

text: t

text: where

text: Cˆ

text: c

text: max

text: c

text: σ

text: and

text: the

text: last

text: inequality

text: uses

text: Doob’s

text: maximal

text: inequality.

text: This

text: S∈

text: M

text: B

text: M

text: shows

text: that

text: Φ(ν)

text: for

text: all

text: ν

text: M

text: P

text: M

text: We

text: now

text: show

text: that

text: Φ(

text: is

text: contained

text: in

text: a

text: compact

text: set

text: in

text: i.e.

text: Φ(

text: is

text: relatively

text: T,L

text: compact.

text: M

text: C

text: R

text: Relative

text: compactness

text: of

text: Φ(

text: For

text: f

text: T

text: and

text: δ

text: let

text: (δ)

text: sup

text: f(t)

text: f(s)

text: f

text: s,t

text: t

text: s

text: δ

text: M

text: Then

text: for

text: ε,

text: δ,

text: and

text: ν

text: similar

text: to

text: the

text: estimate

text: in

text: Φ(ν)(Xν

text: (δ)

text: sup

text: Xν(t)

text: Xν(s)

text: Xν

text: s

text: t

text: s+δ

text: T

text: Cˆ

text: E

text: δ

text: sup

text: sup

text: B(u)

text: B(s)

text: s

text: t

text: s+δ

text: T

text: s

text: u

text: t

text: Cˆ

text: E

text: (δ

text: (δ)).

text: B

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Then, (3.22)(cid:90)and (3.23) imply, T (cid:90) (cid:90) ∆V n(t) + σ ∆DV n(s)dB(s) t (cid:90) T T = ∆gn(T ) + ∆yn(s)dY 0(s) + ∆rn(s)dR0(s) t t (cid:90) T − + [H(s, νn(s), X0(s), DV (s, X0(s))) H(s, νn(s), X0(s), DV (s, X0(s)))]ds νn ν t T − + [H(s, νn(s), X0(s), DV (s, X0(s))) H(s, ν(s), X0(s), DV (s, X0(s)))]ds. ν ν t Squaring both sid(cid:20)e(cid:90)s and then taking(cid:21)expectations gives E (cid:104) (cid:90) E T (cid:105) [(∆V n(t))2] + σ2 (∆DV n(s))2ds (3.24) t ≤ − E T − 2(T t) [H(s, νn(s), X0(s), DV (s, X0(s))) H(s, νn(s), X0(s), DV (s, X0(s)))]2ds νn ν (cid:104)t (cid:90) (cid:105) + 2Cn(t) ≤ − E T 2c2 (T t) (∆DV n(s))2ds + 2Cn(t), B t where (cid:104) (cid:90) (cid:90) E (cid:90) T T (cid:105) Cn(t) = ∆gn(T ) + ∆yn(s)dY 0(s) + ∆rn(s)dR0(s) t t T − 2 + [H(s, νn(s), X0(s), DV (s, X0(s))) H(s, ν(s), X0(s), DV (s, X0(s)))]ds . ν ν t ∈ − Letting δ = σ2/(4c2 ), we get from (3.2(cid:20)4(cid:90)) that for every t (cid:21) [T δ, T ], B E σ2 E T ≤ [(∆V n(t))2] + (∆DV n(s))2ds 4Cn(t). (3.25) 2 t ∈ ∞ We now show that lim sup →∞ sup ≤ ≤ Cn(t) = 0. Note that there exists C (0, ) n 0 t T ∈ N 1 such that the followi(cid:2)ng inequali(cid:3)ty hol(cid:2)ds for all n(cid:3) . (cid:2) (cid:3) 1 ≤ E (cid:20)(cid:90) E (cid:21) (cid:20)(cid:90) (cid:90) E (cid:21) sup Cn(t) (∆gn(T ))2 + (Y 0(T ))2 sup (∆yn(t))2 + (R0(T ))2 sup (∆rn(t))2 C ≤ ≤ ≤ ≤ ≤ ≤ 1 0 t T 0 t T 0 t T T T T E E + (∆fn(s))2ds + (∆bn(s))2ds (DV (s, X0(s)))2ds . ν 0 0 0 (3.26) 17 ##LTLine## ##LTLine##

text: Then,

text: imply,

text: T

text: ∆V

text: n(t)

text: σ

text: ∆DV

text: n(s)dB(s)

text: t

text: T

text: T

text: ∆gn(T

text: ∆yn(s)dY

text: t

text: t

text: T

text: [H(s,

text: νn(s),

text: DV

text: (s,

text: H(s,

text: νn(s),

text: DV

text: (s,

text: νn

text: ν

text: t

text: T

text: [H(s,

text: νn(s),

text: DV

text: (s,

text: H(s,

text: ν(s),

text: DV

text: (s,

text: ν

text: ν

text: t

text: Squaring

text: both

text: and

text: then

text: gives

text: E

text: E

text: T

text: [(∆V

text: σ2

text: (∆DV

text: t

text: E

text: T

text: t)

text: [H(s,

text: νn(s),

text: DV

text: (s,

text: H(s,

text: νn(s),

text: DV

text: (s,

text: νn

text: ν

text: E

text: T

text: (T

text: t)

text: (∆DV

text: B

text: t

text: where

text: E

text: T

text: T

text: Cn(t)

text: ∆gn(T

text: ∆yn(s)dY

text: t

text: t

text: T

text: [H(s,

text: νn(s),

text: DV

text: (s,

text: H(s,

text: ν(s),

text: DV

text: (s,

text: ν

text: ν

text: t

text: Letting

text: δ

text: we

text: get

text: from

text: that

text: for

text: every

text: t

text: [T

text: δ,

text: T

text: B

text: E

text: σ2

text: E

text: T

text: [(∆V

text: (∆DV

text: t

text: We

text: now

text: show

text: that

text: lim

text: sup

text: sup

text: Cn(t)

text: Note

text: that

text: there

text: exists

text: C

text: n

text: t

text: T

text: N

text: such

text: that

text: the

text: for

text: all

text: E

text: E

text: E

text: sup

text: Cn(t)

text: (∆gn(T

text: (Y

text: sup

text: sup

text: C

text: t

text: T

text: t

text: T

text: t

text: T

text: T

text: T

text: T

text: E

text: E

text: (DV

text: (s,

text: ν

text: ##LTLine##

text: ##LTLine##


text: (cid:2) (cid:3) Using the properties of the Skorohod map (Lemma 2.1) it follows that E ∞ (Y 0(T ))2 + (R0(T ))2 < . The convergence of the right side of (3.26) to 0 is now immediate from Assumption 3.1(a), the boundedn(cid:20)e(cid:90)ss of DVν, and (3.20). Thus from (3.25)(cid:21)we have that E T | − | E − lim DV (t, X0(t)) DV (t, X0(t)) dt = 0, lim [(∆V n(T δ))2] = 0. (3.27) n→∞ − νn ν n→∞ T δ ∈ − Using the second convergence in (3.27) and repeating the above argument for t [T δ, T ] − − − to the interval [T 2δ, T δ], we see that (3.27) holds with T replaced with T δ. Proceeding recursively in this manner we have (3.21). Hence we have shown that → × P α0 α0 in λ - measure. (3.28) νn ν T → → ∞ Using the above property we will now argue that Φ(νn) Φ(ν) as n , completing the (cid:48) ∈ M proof of continuity of Φ. Let for ν , 0 (cid:48) (cid:48) ∈ × γ (cid:48)(t, x) = αˆ(t, ν (t), x, DV (cid:48)(t, x)), ˆb (cid:48)(t, x) = b(t, ν (t), x, γ (cid:48)(t, x)), (t, x) [0, T ] [0, L] ν ν ν ν P (cid:48) F and let ν be a probabil(cid:20)ity m(cid:90) easure on (Ω, ) deﬁned as(cid:90) (cid:21) dPν(cid:48) = exp 1 T ˆb (cid:48)(t, X0(t))dB(t) − 1 T ˆb2(cid:48)(t, X0(t))dt dP. (3.29) σ ν 2σ2 ν 0 0 P (cid:48) ◦ − (cid:48) → By Girsanov’s theorem ν (X0) (cid:18)1 = Φ(ν )(cid:19). Thus(cid:18)to show Φ(νn(cid:19)) Φ(ν) it suﬃces to P → P P (cid:107)P → → ∞ argue that νn ν. We will in fact show that R( ν νn) 0 as n , where P P P R(Pν(cid:107)Pνn) = Eν log dP ν = E d Pν log dP ν d νn d d νn P P is the relative entropy of ν with respect to νn, which due to Pinsker’s inequality (see [67, P P Page 132]) gives the convergence of νn to ν. Let − − ∈ × ∆ˆb (t, x) = ˆb (t, x) ˆb (t, x), ∆ˆb2(t, x) = ˆb2(t, x) ˆb2 (t, x), (t, x) [0, T ] [0, L]. n ν νn n ν νn (cid:90) (cid:90) With this notation, P d ν 1 T − 1 T log dPνn = σ ∆ˆbn(t, X0(t))dB(t) 2σ2 ∆ˆb2n(t, X0(t))dt. 0 0 Also, noting that since b is bounded E(dPPν )2 =. κ < ∞, we have from Cauchy-Schwarz inequal- d ity 18 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Using

text: the

text: properties

text: of

text: the

text: Skorohod

text: map

text: (Lemma

text: it

text: follows

text: that

text: E

text: (Y

text: The

text: convergence

text: of

text: the

text: right

text: side

text: of

text: to

text: is

text: now

text: immediate

text: from

text: Assumption

text: the

text: of

text: DVν,

text: and

text: Thus

text: from

text: have

text: that

text: E

text: T

text: E

text: lim

text: DV

text: (t,

text: DV

text: (t,

text: dt

text: lim

text: [(∆V

text: n(T

text: n→∞

text: νn

text: ν

text: n→∞

text: T

text: δ

text: Using

text: the

text: second

text: convergence

text: in

text: and

text: repeating

text: the

text: above

text: argument

text: for

text: t

text: [T

text: δ,

text: T

text: to

text: the

text: interval

text: [T

text: T

text: δ],

text: we

text: see

text: that

text: holds

text: with

text: T

text: replaced

text: with

text: T

text: δ.

text: Proceeding

text: recursively

text: in

text: this

text: manner

text: we

text: have

text: Hence

text: we

text: have

text: shown

text: that

text: P

text: α0

text: α0

text: in

text: λ

text: measure.

text: νn

text: ν

text: T

text: Using

text: the

text: above

text: property

text: we

text: will

text: now

text: argue

text: that

text: Φ(νn)

text: Φ(ν)

text: as

text: n

text: completing

text: the

text: M

text: proof

text: of

text: continuity

text: of

text: Φ.

text: Let

text: for

text: ν

text: γ

text: x)

text: αˆ(t,

text: ν

text: (t),

text: x,

text: DV

text: x)),

text: ˆb

text: x)

text: b(t,

text: ν

text: (t),

text: x,

text: γ

text: x)),

text: (t,

text: x)

text: T

text: L]

text: ν

text: ν

text: ν

text: ν

text: P

text: F

text: and

text: let

text: ν

text: be

text: a

text: easure

text: on

text: (Ω,

text: deﬁned

text: exp

text: T

text: ˆb

text: T

text: dP.

text: σ

text: ν

text: ν

text: P

text: By

text: Girsanov’s

text: theorem

text: ν

text: Φ(ν

text: show

text: Φ(ν)

text: it

text: suﬃces

text: to

text: P

text: P

text: P

text: argue

text: that

text: νn

text: ν.

text: We

text: will

text: in

text: fact

text: show

text: that

text: R(

text: ν

text: νn)

text: as

text: n

text: where

text: P

text: P

text: P

text: Eν

text: log

text: dP

text: ν

text: E

text: d

text: Pν

text: log

text: dP

text: ν

text: d

text: νn

text: d

text: d

text: νn

text: P

text: P

text: is

text: the

text: relative

text: entropy

text: of

text: ν

text: with

text: respect

text: to

text: νn,

text: which

text: due

text: to

text: Pinsker’s

text: inequality

text: (see

text: P

text: P

text: Page

text: gives

text: the

text: convergence

text: of

text: νn

text: to

text: ν.

text: Let

text: ∆ˆb

text: (t,

text: x)

text: ˆb

text: (t,

text: x)

text: ˆb

text: (t,

text: x),

text: x)

text: x)

text: (t,

text: x),

text: (t,

text: x)

text: T

text: L].

text: n

text: ν

text: νn

text: n

text: ν

text: νn

text: With

text: this

text: notation,

text: P

text: d

text: ν

text: T

text: T

text: log

text: dPνn

text: σ

text: ∆ˆbn(t,

text: Also,

text: noting

text: that

text: since

text: b

text: is

text: bounded

text: E(dPPν

text: κ

text: we

text: have

text: from

text: Cauchy-Schwarz

text: inequal-

text: d

text: ity

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: { } R [T ] For every t in some dense subset of [0, T ], Xn(t) ∈N is a tight sequence of valued 1 n random variables. { } { } Then by Rebolledo’s theorem (see [49, Theorem 2.3.2]) A˜n,i ≥ and D˜√n,i ≥ are tight in D (cid:82) R n 1 n 1 ([0, T ] : ) for each i. Also since the jumps of A˜n,i and D˜n,i are of size 1/ e , these processes C n are -tight (namely all weak limit points are continuous a.s.). From boundedness of b we see that { · ˜bn,i(s)ds} ∈N is tight in C([0, T ] : R). Combining this with Assumption 4.1(b) we 0 { } n C D R see that ζn,i ∈N is -tight in ([0, T ] : ). Using now the continuity of the Skorohod map n { } (Lemma 2.1) we have the desired tightness of G˜n,i ∈N. n . Suppose now that, along some subsequence, G˜n converges to G˜ = (ζi, Q˜i, Y˜ i, R˜i), in dis- D R ⊗∞ ∈ C R ⊗∞ tribution, in ([0, T ] : ( 4) ). Then G˜ ([0, T ] : ( 4) ) a.s. and from [50, Lemma { } { }∞ 4.2] and the exchangeability of G˜n,i n it follows that G˜i is exchangeable and(along the i=2 i=2 subsequence), ⇒ (G˜n, Ξn) (G˜, Ξ) (cid:80) (4.5) D R ⊗∞ × P D R . in ([0, T ] : ( 4) ) ( ([0, T ] : 4)) where Ξ = lim →∞ 1− m δ . { } m m 1 i=2 G˜i{ } { W}e will now(cid:90) characterize the distribution of Q˜(cid:90)i . From tightness of Y˜ n,i n∈N and R˜n,i ∈ argued above and (2.6) it follows that n N 1 t → 1 t → 1{ }µn,i(s)ds 0, and 1{ }λn,i(s)ds 0, e Q˜n,i(s)=0 e Q˜n,i(s)=L n 0 n 0 (cid:20)(cid:12) (cid:12) (cid:12) (cid:12)(cid:21) (cid:12) (cid:12) (cid:12) (cid:12) uniformly on [0, T ], in probabili(cid:12)ty. Also, fro(cid:12)m (cid:12)(2.1) it follo(cid:12)ws that (cid:12) (cid:12) (cid:12) (cid:12) λn,i(t) − µn,i(t) − → sup λˆ + µˆ 0 a.s. ≤ ≤ e e 0 t T n n → ∞ as n . Thus from (2.4) (and the relation λˆ = µˆ), for all i, j, (cid:104) (cid:105) → (cid:104) (cid:105) → (cid:104) (cid:105) → A˜n,i, A˜n,j (t) δ λˆ, D˜n,i, D˜n,j (t) δ λˆ, A˜n,i, D˜n,j (t) 0 ij ij → ∞ in probability, uniformly on [0, T ], as n . By standard martingale techniques it now follows that { − } ⇒ { } A˜n,i D˜n,i ≥ σBi ≥ , i 1 i 1 R∞ { } in D([0, T ] : ), where (cid:18)Bi are mu(cid:90)tually independent standard Browni(cid:19)an motions. Also, ≥ since for i 2 · · − · ∈ (Q˜n,i, Y˜ n,i, R˜n,i)(t) = Γ Q˜n,i(0) + ˜bn,i(s)ds + A˜n,i( ) D˜n,i( ) + o(1) (t), t [0, T ], 0 where ˜bn,i(t) = b(t, Q˜n,i(t), αˆ(t, ν¯(t), Q˜n,i(t), DV (t, Q˜n,i(t)))), ν¯ ≥ we have from the con(cid:18)tinuity(cid:90) of b (Assumption 3.1), αˆ, and DV , for i 2, (cid:19) ν¯ · · (Q˜i, Y˜ i, R˜i)(t) = Γ x + b(t, Q˜i(t), αˆ(t, ν¯(t), Q˜i(t), DV (t, Q˜i(t))))dt + σBi( ) (t). (4.6) ν¯ 0 24 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: R

text: [T

text: For

text: every

text: t

text: in

text: some

text: dense

text: subset

text: of

text: T

text: Xn(t)

text: ∈N

text: is

text: a

text: tight

text: sequence

text: of

text: valued

text: n

text: random

text: variables.

text: Then

text: by

text: Rebolledo’s

text: theorem

text: (see

text: Theorem

text: A˜n,i

text: and

text: D˜√n,i

text: are

text: tight

text: in

text: D

text: R

text: n

text: n

text: T

text: for

text: each

text: i.

text: Also

text: since

text: the

text: jumps

text: of

text: A˜n,i

text: and

text: D˜n,i

text: are

text: of

text: size

text: e

text: these

text: processes

text: C

text: n

text: are

text: -tight

text: (namely

text: all

text: weak

text: limit

text: points

text: are

text: continuous

text: a.s.).

text: From

text: boundedness

text: of

text: b

text: we

text: see

text: that

text: ˜bn,i(s)ds}

text: ∈N

text: is

text: tight

text: in

text: T

text: R).

text: Combining

text: this

text: with

text: Assumption

text: we

text: n

text: C

text: D

text: R

text: see

text: that

text: ζn,i

text: ∈N

text: is

text: -tight

text: in

text: T

text: Using

text: now

text: the

text: continuity

text: of

text: the

text: Skorohod

text: map

text: n

text: (Lemma

text: we

text: have

text: the

text: desired

text: tightness

text: of

text: G˜n,i

text: ∈N.

text: n

text: Suppose

text: now

text: that,

text: along

text: some

text: subsequence,

text: G˜n

text: converges

text: to

text: G˜

text: (ζi,

text: Q˜i,

text: Y˜

text: i,

text: R˜i),

text: in

text: dis-

text: D

text: R

text: C

text: R

text: tribution,

text: in

text: T

text: Then

text: G˜

text: T

text: a.s.

text: and

text: from

text: Lemma

text: and

text: the

text: exchangeability

text: of

text: G˜n,i

text: n

text: it

text: follows

text: that

text: G˜i

text: is

text: exchangeable

text: and(along

text: the

text: subsequence),

text: (G˜n,

text: Ξn)

text: (G˜,

text: Ξ)

text: D

text: R

text: P

text: D

text: R

text: in

text: T

text: T

text: where

text: Ξ

text: lim

text: 1−

text: m

text: δ

text: m

text: m

text: G˜i{

text: W}e

text: will

text: characterize

text: the

text: distribution

text: of

text: From

text: tightness

text: of

text: Y˜

text: n,i

text: n∈N

text: and

text: R˜n,i

text: argued

text: above

text: and

text: it

text: follows

text: that

text: n

text: N

text: t

text: t

text: }µn,i(s)ds

text: and

text: }λn,i(s)ds

text: e

text: e

text: Q˜n,i(s)=L

text: n

text: n

text: uniformly

text: on

text: T

text: in

text: Also,

text: it

text: that

text: λn,i(t)

text: µn,i(t)

text: sup

text: λˆ

text: µˆ

text: a.s.

text: e

text: e

text: t

text: T

text: n

text: n

text: as

text: n

text: Thus

text: from

text: (and

text: the

text: relation

text: λˆ

text: µˆ),

text: for

text: all

text: i,

text: j,

text: A˜n,i,

text: A˜n,j

text: (t)

text: δ

text: λˆ,

text: D˜n,i,

text: D˜n,j

text: (t)

text: δ

text: λˆ,

text: A˜n,i,

text: D˜n,j

text: (t)

text: ij

text: ij

text: in

text: probability,

text: uniformly

text: on

text: T

text: as

text: n

text: By

text: standard

text: martingale

text: techniques

text: it

text: now

text: follows

text: that

text: A˜n,i

text: D˜n,i

text: σBi

text: i

text: i

text: R∞

text: in

text: T

text: where

text: are

text: independent

text: standard

text: motions.

text: Also,

text: since

text: for

text: i

text: (Q˜n,i,

text: Y˜

text: n,i,

text: R˜n,i)(t)

text: Γ

text: ˜bn,i(s)ds

text: A˜n,i(

text: D˜n,i(

text: (t),

text: t

text: T

text: where

text: ˜bn,i(t)

text: b(t,

text: Q˜n,i(t),

text: αˆ(t,

text: ν¯(t),

text: Q˜n,i(t),

text: DV

text: (t,

text: Q˜n,i(t)))),

text: ν¯

text: we

text: have

text: from

text: the

text: of

text: b

text: (Assumption

text: αˆ,

text: and

text: DV

text: for

text: i

text: ν¯

text: (Q˜i,

text: Y˜

text: i,

text: R˜i)(t)

text: Γ

text: x

text: b(t,

text: Q˜i(t),

text: αˆ(t,

text: ν¯(t),

text: Q˜i(t),

text: DV

text: (t,

text: Q˜i(t))))dt

text: σBi(

text: (t).

text: ν¯

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∈ D R ≤ ≤ (cid:107) (cid:107) . (cid:107) (cid:107) topology. For f ([0, T ] : d) and 0 t T , f = sup ≤ ≤ f(s) . In case that d = 1, | | S t 0 s t S we often use f . We will denote by Lip ( ) the space of real Lipschitz functions on whose t 1 S → R Lipschitz norm is bounded by 1, namely the class of functions f : with | − | ≤ ∈ S f(x) f(y) d(x, y), x, y S P S S where d denotes the metric on . Denote by ( ) the space of probability measures on . We P S endow ( ) with the topology of weak convergence of measures. Convergence in distribution ⇒ ∈ ∞ of S valued random variable X to X will be denoted as X X. For T, L (0, ), the P C n P n space ( ([0, T ] : [0, L])) will be denoted as . The Wasserstein distance of order 1 on P S S T,L ( ), where is a co(cid:26)m(cid:20)p(cid:90)act metric space,(cid:21)is deﬁned as (cid:27) (cid:48) ∈ P S × S (cid:48) W (η , η) = inf d(x, y)dπ(x, y) : π ( ) with marginals η and η , 1 S (cid:48) ∈ P S C × × where η, η ( ). We denote by 1,2([0, T ] [0, L]) the space of functions f : (0, T ) → R (0, L) that are continuously diﬀerentiable (resp., twice continuously diﬀerentiable) with respect to (w.r.t.) the ﬁrst (resp., second) variable and are such that the function and the × ∈ C × derivatives extend continuously to [0, T ] [0, L]. For φ 1,2([0, T ] [0, L]), D φ, Dφ, D2φ will t ∈ S denote the time derivative and the ﬁrst two space derivatives of φ, respectively. For x , ∈ P S δ ( ) denotes the Dirac measure at x. x 2 The n-server queuing control problem ∈ { } We consider a symmetric n-server stochastic queueing system. Each server i 1, . . . , n is associated with a queue with a ﬁnite capacity and is able to control the rates of the service and arrivals of jobs to its queue. The rates can also depend on the state of the queue and on the empirical measure of the states of all the n-queues. We will consider a regime where the arrival and processing rates are approximately the same and are of the same order as the number of queues in the system. We now describe our precise scaling regime and introduce the various processes that determine the evolution of the state of the system. 2.1 Diﬀusion scaling ∈ N Fix T, L > 0 and n . Here T denotes the terminal time of our ﬁnite time horizon and R [0, L] will be the state space of the scaled queue length process. Let U be a compact subset of . We will denote by λn,i and µn,i the (controlled) arrival and service rates associated with queue { } → ∞ → ∞ i. Fix an arbitrary s√equence of scaling parameters e that satisfy e when n . O n n n O The rates will be ( e ) perturbations of certain nominal (uncontrolled) (e ) overall rates. n n More precisely, we assume that there exist λˆ, µˆ > 0, and bounded and measurable functions × P × × → R λ, µ : [0, T ] ([0, L]) [0, L] U such that √ √ λn,i(t) = λˆen + λ(t, ν˜n(t), Q˜n,i(t), αn,i(t))√en + o(√en), µn,i(t) = µˆe + µ(t, ν˜n(t), Q˜n,i(t), αn,i(t)) e + o( e ), (2.1) n n n 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: D

text: R

text: topology.

text: For

text: f

text: T

text: d)

text: and

text: t

text: T

text: f

text: sup

text: f(s)

text: In

text: case

text: that

text: d

text: S

text: t

text: s

text: t

text: S

text: we

text: often

text: use

text: f

text: We

text: will

text: denote

text: by

text: Lip

text: the

text: space

text: of

text: real

text: Lipschitz

text: functions

text: on

text: whose

text: t

text: S

text: R

text: Lipschitz

text: norm

text: is

text: bounded

text: by

text: namely

text: the

text: class

text: of

text: functions

text: f

text: with

text: S

text: f(x)

text: f(y)

text: d(x,

text: y),

text: x,

text: y

text: S

text: P

text: S

text: S

text: where

text: d

text: denotes

text: the

text: metric

text: on

text: Denote

text: by

text: the

text: space

text: of

text: probability

text: measures

text: on

text: We

text: P

text: S

text: endow

text: with

text: the

text: topology

text: of

text: weak

text: convergence

text: of

text: measures.

text: Convergence

text: in

text: distribution

text: of

text: S

text: valued

text: random

text: variable

text: X

text: to

text: X

text: will

text: be

text: denoted

text: as

text: X

text: X.

text: For

text: T,

text: L

text: the

text: P

text: C

text: n

text: P

text: n

text: space

text: T

text: L]))

text: will

text: be

text: denoted

text: as

text: The

text: Wasserstein

text: distance

text: of

text: order

text: on

text: P

text: S

text: S

text: T,L

text: where

text: is

text: a

text: metric

text: deﬁned

text: as

text: P

text: S

text: S

text: W

text: (η

text: η)

text: inf

text: d(x,

text: y)dπ(x,

text: y)

text: π

text: with

text: marginals

text: η

text: and

text: η

text: S

text: P

text: S

text: C

text: where

text: η,

text: η

text: We

text: denote

text: by

text: T

text: L])

text: the

text: space

text: of

text: functions

text: f

text: T

text: R

text: L)

text: that

text: are

text: continuously

text: diﬀerentiable

text: (resp.,

text: twice

text: continuously

text: diﬀerentiable)

text: with

text: respect

text: to

text: (w.r.t.)

text: the

text: ﬁrst

text: (resp.,

text: second)

text: variable

text: and

text: are

text: such

text: that

text: the

text: function

text: and

text: the

text: C

text: derivatives

text: extend

text: continuously

text: to

text: T

text: L].

text: For

text: φ

text: T

text: L]),

text: D

text: φ,

text: Dφ,

text: will

text: t

text: S

text: denote

text: the

text: time

text: derivative

text: and

text: the

text: ﬁrst

text: two

text: space

text: derivatives

text: of

text: φ,

text: respectively.

text: For

text: x

text: P

text: S

text: δ

text: denotes

text: the

text: Dirac

text: measure

text: at

text: x.

text: x

text: The

text: n-server

text: queuing

text: control

text: problem

text: We

text: consider

text: a

text: symmetric

text: n-server

text: stochastic

text: queueing

text: system.

text: Each

text: server

text: i

text: n

text: is

text: associated

text: with

text: a

text: queue

text: with

text: a

text: ﬁnite

text: capacity

text: and

text: is

text: able

text: to

text: control

text: the

text: rates

text: of

text: the

text: service

text: and

text: arrivals

text: of

text: jobs

text: to

text: its

text: queue.

text: The

text: rates

text: can

text: also

text: depend

text: on

text: the

text: state

text: of

text: the

text: queue

text: and

text: on

text: the

text: empirical

text: measure

text: of

text: the

text: states

text: of

text: all

text: the

text: n-queues.

text: We

text: will

text: consider

text: a

text: regime

text: where

text: the

text: arrival

text: and

text: processing

text: rates

text: are

text: approximately

text: the

text: same

text: and

text: are

text: of

text: the

text: same

text: order

text: as

text: the

text: number

text: of

text: queues

text: in

text: the

text: system.

text: We

text: now

text: describe

text: our

text: precise

text: scaling

text: regime

text: and

text: introduce

text: the

text: various

text: processes

text: that

text: determine

text: the

text: evolution

text: of

text: the

text: state

text: of

text: the

text: system.

text: Diﬀusion

text: scaling

text: N

text: Fix

text: T,

text: L

text: and

text: n

text: Here

text: T

text: denotes

text: the

text: terminal

text: time

text: of

text: our

text: ﬁnite

text: time

text: horizon

text: and

text: R

text: L]

text: will

text: be

text: the

text: state

text: space

text: of

text: the

text: scaled

text: queue

text: length

text: process.

text: Let

text: U

text: be

text: a

text: compact

text: subset

text: of

text: We

text: will

text: denote

text: by

text: λn,i

text: and

text: µn,i

text: the

text: (controlled)

text: arrival

text: and

text: service

text: rates

text: associated

text: with

text: queue

text: i.

text: Fix

text: an

text: arbitrary

text: s√equence

text: of

text: scaling

text: parameters

text: e

text: that

text: satisfy

text: e

text: when

text: n

text: O

text: n

text: n

text: n

text: O

text: The

text: rates

text: will

text: be

text: e

text: perturbations

text: of

text: certain

text: nominal

text: (uncontrolled)

text: (e

text: overall

text: rates.

text: n

text: n

text: More

text: precisely,

text: we

text: assume

text: that

text: there

text: exist

text: λˆ,

text: µˆ

text: and

text: bounded

text: and

text: measurable

text: functions

text: P

text: R

text: λ,

text: µ

text: T

text: L])

text: L]

text: U

text: such

text: that

text: λn,i(t)

text: λˆen

text: λ(t,

text: ν˜n(t),

text: Q˜n,i(t),

text: αn,i(t))√en

text: o(√en),

text: µn,i(t)

text: µˆe

text: µ(t,

text: ν˜n(t),

text: Q˜n,i(t),

text: αn,i(t))

text: e

text: o(

text: e

text: n

text: n

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: this section we give a precise description of this MFG in the current context and give our main results on existence and uniqueness of solutions. 3.1 Description of the MFG The basic idea in the formulation of the MFG is to approximate the scaled queue length process for a typical queue by a suitable drift-controlled reﬂected Brownian motion. We next F {F } P introduce this controlled process. Let (Ω, , , ) be a ﬁltered probability space on which F t is given a one dimensional standard -Brownian motion B. We will refer to the collection F {F } P t ∈ ∈ ∈ P (Ω, , , , B) as a system and denote it by Ξ. Given x [0, L], t [0, T ], and ν , t A { } T,L we denote by (Ξ, t, x, ν) the collection of all pairs (α, Z) where α = α(s) ≤ ≤ − is a U- F { } × R0 s×TRt valued -progressively measurable process, Z = Z(s) ≤ ≤ − is a [0, L] valued F s 0 s T t + + -adapted continuous process such(cid:18)that, (cid:90)Z = (X, Y, R) and(cid:19) s · · ∈ − Z(s) = (X, Y, R)(s) = Γ x + ¯b(u)du + σB( ) (s), s [0, T t], (3.1) 0 where . ∈ − ¯b(u) = b(t + u, ν(t + u), X(u), α(u)), u(cid:112) [0, T t], ν(s) is the marginal of ν at time instant s and σ = 2λˆ. We now introduce the cost ∈ P ∈ ∈ function in the MFG. Given ν , x [0, L], t [0, T ], and a system Ξ as above, let ∈ A T,L (α, Z) (Ξ, t, x, ν). D(cid:104) (cid:90)eﬁne − . E (cid:90) T t (cid:90) − (cid:105) J (t, x, α, Z) = f(s + t, ν(s + t), X(s), α(s))ds + g(ν(T ), X(T t)) ν 0 − − T t T t + y(s + t, ν(s + t))dY (s) + r(s + t, ν(s + t))dR(s) . (3.2) 0 0 We deﬁne the value function associated with the above cost as: V (t, x) = inf inf J (t, x, α, Z). (3.3) ν ∈A ν Ξ (α,Z) (Ξ,t,x,ν) ∈ Deﬁnition 3.1 A solution to the MFG with initial condition x [0, L] is deﬁned to be a ∈ P ∈ A ν such that there exist a system Ξ and an (α, Z) (Ξ, 0, x, ν) such that Z = (X, Y, R) T,LP ◦ − satisﬁes X 1 = ν and V (0, x) = J (0, x, α, Z). (3.4) ν ν If there exists a unique such ν, we refer to V (0, x) as the value of the MFG with initial ν condition x. 9 ##LTLine##

text: this

text: section

text: we

text: give

text: a

text: precise

text: description

text: of

text: this

text: MFG

text: in

text: the

text: current

text: context

text: and

text: give

text: our

text: main

text: results

text: on

text: existence

text: and

text: uniqueness

text: of

text: solutions.

text: Description

text: of

text: the

text: MFG

text: The

text: basic

text: idea

text: in

text: the

text: formulation

text: of

text: the

text: MFG

text: is

text: to

text: approximate

text: the

text: scaled

text: queue

text: length

text: process

text: for

text: a

text: typical

text: queue

text: by

text: a

text: suitable

text: drift-controlled

text: reﬂected

text: Brownian

text: motion.

text: We

text: next

text: F

text: {F

text: P

text: introduce

text: this

text: controlled

text: process.

text: Let

text: (Ω,

text: be

text: a

text: ﬁltered

text: probability

text: space

text: on

text: which

text: F

text: t

text: is

text: given

text: a

text: one

text: dimensional

text: standard

text: -Brownian

text: motion

text: B.

text: We

text: will

text: refer

text: to

text: the

text: collection

text: F

text: {F

text: P

text: t

text: P

text: (Ω,

text: B)

text: as

text: a

text: system

text: and

text: denote

text: it

text: by

text: Ξ.

text: Given

text: x

text: L],

text: t

text: T

text: and

text: ν

text: t

text: A

text: T,L

text: we

text: denote

text: by

text: (Ξ,

text: t,

text: x,

text: ν)

text: the

text: collection

text: of

text: all

text: pairs

text: (α,

text: Z)

text: where

text: α

text: α(s)

text: is

text: a

text: U-

text: F

text: s×TRt

text: valued

text: -progressively

text: measurable

text: process,

text: Z

text: Z(s)

text: is

text: a

text: L]

text: valued

text: F

text: s

text: s

text: T

text: t

text: -adapted

text: continuous

text: process

text: (X,

text: Y,

text: R)

text: s

text: Z(s)

text: (X,

text: Y,

text: R)(s)

text: Γ

text: x

text: ¯b(u)du

text: σB(

text: (s),

text: s

text: T

text: t],

text: where

text: ¯b(u)

text: b(t

text: u,

text: ν(t

text: u),

text: X(u),

text: α(u)),

text: T

text: t],

text: ν(s)

text: is

text: the

text: marginal

text: of

text: ν

text: at

text: time

text: instant

text: s

text: and

text: σ

text: 2λˆ.

text: We

text: now

text: introduce

text: the

text: cost

text: P

text: function

text: in

text: the

text: MFG.

text: Given

text: ν

text: x

text: L],

text: t

text: T

text: and

text: a

text: system

text: Ξ

text: as

text: above,

text: let

text: A

text: T,L

text: (α,

text: Z)

text: (Ξ,

text: t,

text: x,

text: ν).

text: E

text: T

text: t

text: J

text: (t,

text: x,

text: α,

text: Z)

text: f(s

text: t,

text: ν(s

text: t),

text: X(s),

text: α(s))ds

text: g(ν(T

text: X(T

text: t))

text: ν

text: T

text: t

text: T

text: t

text: y(s

text: t,

text: ν(s

text: t))dY

text: (s)

text: r(s

text: t,

text: ν(s

text: t))dR(s)

text: We

text: deﬁne

text: the

text: value

text: function

text: associated

text: with

text: the

text: above

text: cost

text: as:

text: V

text: (t,

text: x)

text: inf

text: inf

text: J

text: (t,

text: x,

text: α,

text: Z).

text: ν

text: ∈A

text: ν

text: Ξ

text: (α,Z)

text: (Ξ,t,x,ν)

text: Deﬁnition

text: A

text: solution

text: to

text: the

text: MFG

text: with

text: initial

text: condition

text: x

text: L]

text: is

text: deﬁned

text: to

text: be

text: a

text: P

text: A

text: ν

text: such

text: that

text: there

text: exist

text: a

text: system

text: Ξ

text: and

text: an

text: (α,

text: Z)

text: (Ξ,

text: x,

text: ν)

text: such

text: that

text: Z

text: (X,

text: Y,

text: R)

text: T,LP

text: satisﬁes

text: X

text: ν

text: and

text: V

text: x)

text: J

text: x,

text: α,

text: Z).

text: ν

text: ν

text: If

text: there

text: exists

text: a

text: unique

text: such

text: ν,

text: we

text: refer

text: to

text: V

text: x)

text: as

text: the

text: value

text: of

text: the

text: MFG

text: with

text: initial

text: ν

text: condition

text: x.

text: ##LTLine##


text: [28] T.-H. Ho, C. Camerer, and K. Weigelt. Iterated dominance and iterated best response in experimental ‘p-beauty contests’. American Economic Review, 88(4):947–969, 1998. [29] K. Jain and V. V. Vazirani. Eisenberg-gale markets: Algorithms and game-theoretic properties. Games and Economic Behavior, 70(1):84–106, 2010. [30] T. Kneeland. Identifying higher-order rationality. Econometrica, 83(5):2065–2079, 2015. [31] B. Lemmens and R. Nussbaum. Nonlinear Perron-Frobenius Theory. Cambridge University Press, 2012. Cambridge Books Online. [32] L. McKenzie. On equilibrium in Graham’s model of world trade and other competitive systems. Econo- metrica, 22:147–161, 1954. [33] L. W. McKenzie. Classical general equilibrium theory. MIT Press, 2002. [34] V. S. Mirrokni and A. Vetta. Convergence issues in competitive games. In K. Jansen, S. Khanna, J. D. P. Rolim, and D. Ron, editors, Proceedings APPROX and RANDOM, LNCS 3122, pages 183–194. Springer, 2004. [35] D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14(1):124–143, 1996. [36] A. Mukherji. An introduction to general equilibrium analysis. Oxford U Press, 2002. [37] R. Nagel. Unraveling in guessing games: An experimental study. American Economic Review, 85(5):1313–1326, 1995. [38] N. Nisan, M. Schapira, G. Valiant, and A. Zohar. Best-response mechanisms. In Innovations in Com- puter Science - ICS 2010, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 155–165, 2011. [39] T. Roughgarden. Intrinsic robustness of the price of anarchy. J. ACM, 62(5):32:1–32:42, November 2015. [40] A. Saha and A. Tewari. On the nonasymptotic convergence of cyclic coordinate descent methods. SIAM Journal on Optimization, 23(1):576–601, 2013. [41] P. A. Samuelson. The stability of equilibrium: Comparative statics and dynamics. Econometrica, 9:97–120, 1941. [42] Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009. [43] D. O. Stahl and P. W. Wilson. Experimental evidence on players’ models of other players. Journal of Economic Behavior and Organization, 25(3):309–327, 1994. [44] D. O. Stahl and P. W. Wilson. On players’ models of other players: Theory and experimental evidence. Games and Economic Behavior, 10(1):218–254, 1995. [45] T. Strzalecki. Depth of reasoning and higher order beliefs. Journal of Economic Behavior & Organiza- tion, 108:108–122, 2014. [46] P. Tseng. Convergence of a block coordinate descent method for nondiﬀerentiable minimization. Journal of optimization theory and applications, 109(3):475–494, 2001. [47] L. Walras. El´ements d’Economie Politique Pure. Corbaz, 1874. (1st ed. 1874; revised ed. 1926; Transl. W. Jaﬀ´e, Elements of Pure Economics, Irwin, 1954). 13

text: T.-H.

text: Ho,

text: C.

text: Camerer,

text: and

text: K.

text: Weigelt.

text: Iterated

text: dominance

text: and

text: iterated

text: best

text: response

text: in

text: experimental

text: ‘p-beauty

text: contests’.

text: American

text: Economic

text: Review,

text: K.

text: Jain

text: and

text: V.

text: V.

text: Vazirani.

text: Eisenberg-gale

text: markets:

text: Algorithms

text: and

text: game-theoretic

text: properties.

text: Games

text: and

text: Economic

text: Behavior,

text: T.

text: Kneeland.

text: Identifying

text: higher-order

text: rationality.

text: Econometrica,

text: B.

text: Lemmens

text: and

text: R.

text: Nussbaum.

text: Nonlinear

text: Perron-Frobenius

text: Theory.

text: Cambridge

text: University

text: Press,

text: Cambridge

text: Books

text: Online.

text: L.

text: McKenzie.

text: On

text: equilibrium

text: in

text: Graham’s

text: model

text: of

text: world

text: trade

text: and

text: other

text: competitive

text: systems.

text: Econo-

text: metrica,

text: L.

text: W.

text: McKenzie.

text: Classical

text: general

text: equilibrium

text: theory.

text: MIT

text: Press,

text: V.

text: S.

text: Mirrokni

text: and

text: A.

text: Vetta.

text: Convergence

text: issues

text: in

text: competitive

text: games.

text: In

text: K.

text: Jansen,

text: S.

text: Khanna,

text: J.

text: D.

text: P.

text: Rolim,

text: and

text: D.

text: Ron,

text: editors,

text: Proceedings

text: APPROX

text: and

text: RANDOM,

text: LNCS

text: pages

text: Springer,

text: D.

text: Monderer

text: and

text: L.

text: S.

text: Shapley.

text: Potential

text: games.

text: Games

text: and

text: Economic

text: Behavior,

text: A.

text: Mukherji.

text: An

text: introduction

text: to

text: general

text: equilibrium

text: analysis.

text: Oxford

text: U

text: Press,

text: R.

text: Nagel.

text: Unraveling

text: in

text: guessing

text: games:

text: An

text: experimental

text: study.

text: American

text: Economic

text: Review,

text: N.

text: Nisan,

text: M.

text: Schapira,

text: G.

text: Valiant,

text: and

text: A.

text: Zohar.

text: Best-response

text: mechanisms.

text: In

text: Innovations

text: in

text: Com-

text: puter

text: Science

text: ICS

text: Tsinghua

text: University,

text: Beijing,

text: China,

text: January

text: Proceedings,

text: pages

text: T.

text: Roughgarden.

text: Intrinsic

text: robustness

text: of

text: the

text: price

text: of

text: anarchy.

text: J.

text: ACM,

text: November

text: A.

text: Saha

text: and

text: A.

text: Tewari.

text: On

text: the

text: nonasymptotic

text: convergence

text: of

text: cyclic

text: coordinate

text: descent

text: methods.

text: SIAM

text: Journal

text: on

text: Optimization,

text: P.

text: A.

text: Samuelson.

text: The

text: stability

text: of

text: equilibrium:

text: Comparative

text: statics

text: and

text: dynamics.

text: Econometrica,

text: Y.

text: Shoham

text: and

text: K.

text: Leyton-Brown.

text: Multiagent

text: Systems:

text: Algorithmic,

text: Game-Theoretic,

text: and

text: Logical

text: Foundations.

text: Cambridge

text: University

text: Press,

text: D.

text: O.

text: Stahl

text: and

text: P.

text: W.

text: Wilson.

text: Experimental

text: evidence

text: on

text: players’

text: models

text: of

text: other

text: players.

text: Journal

text: of

text: Economic

text: Behavior

text: and

text: Organization,

text: D.

text: O.

text: Stahl

text: and

text: P.

text: W.

text: Wilson.

text: On

text: players’

text: models

text: of

text: other

text: players:

text: Theory

text: and

text: experimental

text: evidence.

text: Games

text: and

text: Economic

text: Behavior,

text: T.

text: Strzalecki.

text: Depth

text: of

text: reasoning

text: and

text: higher

text: order

text: beliefs.

text: Journal

text: of

text: Economic

text: Behavior

text: Organiza-

text: tion,

text: P.

text: Tseng.

text: Convergence

text: of

text: a

text: block

text: coordinate

text: descent

text: method

text: for

text: nondiﬀerentiable

text: minimization.

text: Journal

text: of

text: optimization

text: theory

text: and

text: applications,

text: L.

text: Walras.

text: El´ements

text: d’Economie

text: Politique

text: Pure.

text: Corbaz,

text: ed.

text: revised

text: ed.

text: Transl.

text: W.

text: Jaﬀ´e,

text: Elements

text: of

text: Pure

text: Economics,

text: Irwin,


text: Figure 1: Various collective mental models for one round of play in a 3-seller market. A leaf (level 1) denotes best-response dynamics. In level 2 dynamics everyone best-responds to everyone’s best-response to current prices. Players’ beliefs can be far more complex. In the last example C plays by a level 2 model while A and B have more elaborate mental models. 3 ##LTFigure##

text: Figure

text: Various

label: caption

text: collective

text: mental

text: models

text: for

text: one

text: round

text: of

text: play

text: in

text: a

text: market.

text: A

text: leaf

text: (level

text: denotes

text: best-response

text: dynamics.

text: In

text: level

text: dynamics

text: everyone

text: best-responds

text: to

text: everyone’s

text: best-response

text: to

text: current

text: prices.

text: Players’

text: beliefs

text: can

text: be

text: far

text: more

text: complex.

text: In

text: the

text: last

text: example

text: C

text: plays

text: by

text: a

text: level

text: model

text: while

text: A

text: and

text: B

text: have

text: more

text: elaborate

text: mental

text: models.

text: ##LTFigure##

label: figure