# Bandit PDF Free Download

The Whispering Bandit. Download full The Whispering Bandit Book or read online anytime anywhere, Available in PDF, ePub and Kindle. Click Get Books and find your favorite books in the online library. Create free account to access unlimited books, fast download and ads free! We cannot guarantee that The Whispering Bandit book is in the library. Bandit is a tool designed to find common security issues in Python code. To do this Bandit processes each file, builds an AST from it, and runs appropriate plugins against the AST nodes. Once Bandit has finished scanning all the files it generates a report. The multi-armed bandit problem was already studied by several authors. We refer to Mandelbaum (1987, 1988) in which time is replaced by a partially ordered set, or, more recently, Kaspi and Mandelbaum (1998) for motivation and description of the state of art.

### Bandit Pdf Free Download Adobe Reader

The set-indexed bandit problem Giacomo Alettia; ∗; 1 , Ely Merzbachb a Department

of Mathematics, University of Milan, via Saldini no 50, 20133 Milan, Italy of Mathematics, Bar-Ilan University, Ramat Gan 52900, Israel

b Department

Received 6 May 2001; received in revised form 22 February 2002; accepted 1 March 2002

Abstract Motivated by spatial problems of allocations, we give a proof of the existence of an optimal solution to a set-indexed formulation of the bandit problem. The proof is based on a compactization of collections of fuzzy stopping sets and fuzzy optional increasing paths, and a construction c 2002 Elsevier Science B.V. All rights reserved. of set-indexed integrals. 0002 MSC: primary 60g40; secondary 93e20 Keywords: Set-indexed processes; Bandit problem; Stochastic control; Randomization

1. Formulation of the problem The aim of this paper is to present a formulation of the Bandit problem in the framework of set-indexed processes, and to prove the existence of an optimal solution to this problem. The multi-armed bandit problem was already studied by several authors. We refer to Mandelbaum (1987, 1988) in which time is replaced by a partially ordered set, or, more recently, Kaspi and Mandelbaum (1998) for motivation and description of the state of art. In this section, we give the notation and state the main existence result. In order to prove it, we need two kinds of tools: the 9rst one are fuzzy stopping sets and fuzzy optional increasing paths that will be the subject of the next section. The other tool is a kind of set-indexed integration; it will be developed in Section 3. In Section 4, we study an extension of the Baxter–Chacon topology (see Baxter and Chacon, 1977) and we prove that fuzzy sets and fuzzy optional increasing paths are compact. The last section is devoted to the proof of the main theorem. ∗

Corresponding author. E-mail addresses: [email protected] (G. Aletti), [email protected] (E. Merzbach). 1 Work done at a stay at Bar-Ilan University.

c 2002 Elsevier Science B.V. All rights reserved. 0304-4149/02/$ - see front matter 0001 PII: S 0 3 0 4 - 4 1 4 9 ( 0 2 ) 0 0 1 2 5 - 4

128

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

Our framework can be applied to many diAerent examples. A simple motivation in which a natural model is provided by processes indexed by a collection of subsets of a general space was already suggested by Gittins (1989) in the following close example: A prospector looking for gold in some region, has to decide where to look and if he prospects for any size of piece of land must repeatedly take further decisions in the light of his successes to date. His decision problem is how to allocate the prospection of the region in a sequential manner, so as to maximize his likely reward. This problem is spatio-temporal since at each “instant”, the prospector has to decide where to excavate. Another kind of example is concerned with the theory of optimal search for the location of a speci9c object. Another example is related with aerial photography (see IvanoA and Merzbach, 2002), in which at each time, an airplane pilot must decide what is the optimal direction permitting better pictures. The instantaneous decisions maker has to take into consideration diAerent random constraints like clouds, draughts, etc. Our notation follows that of IvanoA and Merzbach (2000). Let (T; d) be a compact complete metric space. Throughout the whole paper, if A∗ is any class of subsets of T , A∗ (u) denotes the class of 9nite union of elements in A∗ ; ◦ “( ” indicates strict inclusion and “(·)” and “(·) ” denotes, respectively, the closure and ∗ the interior of a set. A (u) denotes the class of countable intersections of elements in A∗ (u). Under an assumption that is always satis9ed when T is a metric space, it is proved in Aletti (2001) that A∗ (u) is equal to the class of the closures of countable unions of elements in A∗ (u), when A∗ is an indexing collection as de9ned below. De0016nition 1. A nonempty class A of compact; connected subsets of T is called an indexing collection if it satis9es the following: ◦ (1) ∅; T ∈ A; and A 0004= A if A 0004= ∅ or T and A ∈ A. (2) A is closed under arbitrary intersections and if 0001 A; B 0004= ∅ and A; B ∈ A; then A ∩ B 0004= ∅. If (Ai )i∈N is increasing and Ai ∈ A; then i Ai ∈ A. (3) (A) = BT ; where BT is the collection of all Borel sets of T . (4) Separability from above There exists an increasing sequence of 9nite subclasses An ⊆ A; An ={An1 ; : : : ; Ankn } closed under intersections with ∅; T ∈ An ; and a sequence of functions gn : A → An (u) such that: 0002 (a) gn preserves arbitrary intersections and 9nite unions (i.e. gn ( A∈A0002 A) = 0001 0001 0001 0002 k m k 0003 0003 0002 gn (A) for any A ⊆ A; and if i=1 Ai = j=1 Aj ; then i=1 gn (Ai ) = 0001A∈A m 0003 j=1 gn (Aj )); ◦ (b) for each A ∈ A; A ⊆ (gn (A)) ; (c) gn (A) ⊆ gm (A) if n ¿0002m; (d) for each A ∈ A; A = n gn (A); (e) if A ∈ A and A0003 ∈ An ; then gn (A) ∩ A0003 ∈ An ; (f) gn (∅) = ∅ ∀n. 0002 0002 0002 Remark 1. Denote ∅0003 = n A∈An ;A0004=∅ A = A∈A; A0004=∅ A. (The second equality is a result of separability.) We have that ∅0003 ∈ A and ∅0003 0004= ∅; by the 9nite intersection property for compact sets.

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

129

Remark 2. Since gn preserves 9nite unions; A ⊆ B ⇒ gn (A) ⊆ gn (B). As well; gn has 0001 a unique extension to A(u) which is de9ned0002as follows: for B 0003∈ A(u); gn (B) = A∈A; A⊆B gn (B). If B ∈ A(u); we de9ne gn (B) = B0002 ∈A(u); B⊆B0002 gn (B ). In IvanoA and Merzbach (2000) it is proved that gn : A(u) → An (u) is well de9ned. It preserves ◦ countable intersections and 9nite unions and B ⊆ (gn (B)) . We de9ne the HausdorA metric on the nonempty compact subsets of T : dH (A; B) = inf {0010: B ⊆ A0010 and A ⊆ B0010 }; where A0010 ={t ∈ T : d(t; A) 6 0010}, for any 0010 ¿ 0 and d(t; A)= inf {d(t; s): s ∈ A}. We require that A be compact in the HausdorA metric. Remark 3. For the sake of simplicity; we required that T is compact and T ∈ A. Using AlexandroA compacti9cation; all our results will still hold supposing only that T is locally compact. Let (0014; F; P) be a complete probability space. A set-indexed 4ltration is a family {FA ; A ∈ A} of sub--algebras of F which is: • complete (F∅ contains all the P-null sets); • increasing (if A ⊆ B, A; B ∈ A, 0002∞then FA ⊆ FB ); • outer-continuous (F∩∞ = A n n=1 FAn , where {An } is a decreasing sequence in A). n=1 0002 Remark 4. Let FrB := n ∨A∈A; A⊆gn (B) FA . In IvanoA and Merzbach (2000; Lemma 1.4.1) it is stated that {FrB ; B ∈ A(u)} is (complete) monotone outer continuous and FrA = FA ; for any A ∈ A. This allows us to naturally speak about a 9ltration indexed by A(u). De0016nition 2. A random set 0016 : 0014 → A(u) is called a stopping set if {A ⊆ 0016} ∈ FA ; for any A ∈ A. A random set 0016 : 0014 → A(u) is called a generalized stopping set if {A ⊆ 0016} ∈ FA ; for any A ∈ A. An optional increasing path (o.i.p.) is a family 0001 = {0016t ; t ∈ [0; 1]} of generalized stopping sets s.t. (1) 00160 = ∅0003 ; (2) 00161 = T ; (3) 0016s ⊆ 0016t if s 6 t a.s.; (4) ∀! ∈ 0014; 0016t (!) ⊆ gn (gn (0016s (!))) =: gn2 (0016s )(!); if s 6 t ¡ s + 2−0019(n) ; where limn→∞ 0019(n) = ∞ a.s. The set of all o.i.p.’s will be denoted by 0002. Remark 5. Following IvanoA and Merzbach (2000); our de9nition is “opposite” to that of Kurtz (1980) and HMurzeler (1985); 2 and hence this paper is not a direct extension of Dalang (1990). The formulation of the bandit problem will be done here for set-indexed processes. Condition 4 relates to Zu = u in Dalang (1990). It states that the speed of o.i.p.’s growing is bounded. It will be necessary in Lemma 18 as Zu = u is in Dalang (1990). 2

We require that {A ⊆ 0016} ∈ FA instead of requiring {0016 ⊆ A} ∈ FA .

130

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

Following the formulation of the bandit problem given in Dalang (1990), let X = {XA : A ∈ A(u)} be a real-valued set-indexed process de9ned on (0014; F; P) with uppersemicontinuous sample paths such that E[supA∈A(u) XA ] ¡ ∞ and let V ={Vs ; s ∈ [0; 1]} be a bounded nonnegative right-continuous process with nondecreasing sample paths (A is an indexing collection). 0003 Main Theorem 1. For each 0001 ∈ 0002; set R(0001) = E( [0;1] X0016t dVt ). Then there exists an optional increasing path 0001∗ ∈ 0002 s.t. R(0001∗ ) = sup0001∈0002 R(0001); i.e.; 0001∗ is an optimal o.i.p. This theorem will be proved in the last section. 2. Fuzzy stopping sets De0016nition 3. Let B be the Borel sets of [0; 1]. A map 001f : 0014 × [0; 1] → A(u) will be called a fuzzy set if it is F ⊗ B-measurable and (i) nondecreasing in the second variable: s 6 t implies 001f(· ; s) ⊆ 001f(· ; t); (ii) inner continuous in the second variable: if tn → t; tn 6 t; then 0004 001f(·; tn ) = 001f(·; t); n

0002 (iii) outer continuous at 0 : 001f(· ; 0) = t¿0 001f(· ; t); and will be called a fuzzy stopping set if it is a fuzzy set and {(!; r): A ⊆ 001f(!; r)} ∈ FA ⊗ B for any A ∈ A. Also, any function on 0014 will be considered de9ned on 0014 ×[0; 1] in the obvious way. This implies that a stopping set may be seen as a fuzzy stopping set (where 0016(!; v) = (!)). Let 0016 : 0014×[0; 1] → A be nondecreasing, inner continuous and outer continuous at 0. We denote for every v ∈ [0; 1] 0016v : 0014 → A(u);

0016v (!) = 0016(!; v):

Proposition 1. Let 0016 : 0014 × [0; 1] → A(u) be nondecreasing; inner continuous and outer continuous at 0. 0016 is a fuzzy stopping set i9 0016v is a generalized stopping set for each v ∈ [0; 1]. In particular; taking FA = F; 0016 is a fuzzy set i9 0016v is F-measurable for each v ∈ [0; 1]. Proof. If A * 0016(!; r); then there exists 0010 ¿ 0 s.t. A * 0016(!; r + 0010) by inner continuity. Hence we have that 0004 {(!; r): A * 0016(!; r)} = ({!: A * 0016(!; v)} × [0; v]) v∈Q∩[0;1]

=

0004

({!: A * 0016v (!)} × [0; v]):

v∈Q∩[0;1]

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

Given a fuzzy set 0016, de9ne the “probability” P0016 (!; ·) on A(u) by 0005 ◦ ◦ inf {v ∈ [0; 1]: A ⊆ (0016(!; v)) } if A ⊆ (0016(!; 1)) ; P0016 (!; A) = ◦ 1 if A * (0016(!; 1)) :

131

(1)

Remark 6. By inner continuity; when t ¿ 0 we have that ◦

B ⊆ (0016(!; t))

⇔ t ¿ P0016 (!; B);

B ∈ A(u)

(2)

and hence

0004 {A ∈ A: P0016 (!; A) ¡ t} if t ¿ 0; 0016(!; t) = 0004 {A ∈ A: P0016 (!; A) = 0} if t = 0

(3)

by De9nitions 1(1) and 3(iii). Proposition 2. P0016 satis4es the following properties: • takes values in [0; 1]: P0016 (!; ∅) = 0; P0016 (!; T ) = 1; • is nondecreasing: If A ⊆ B; 0002 then P0016 (!; A) 6 P0016 (!; B); ◦ • is outer continuous: If A = n An ; then P0016 (!; An ) → P0016 (!; A). (In fact; if A ⊆ B ; ◦ then there exists k0 s.t. Ak ⊆ B for any k ¿ k0 .) Denote by B (resp. B0003 ) the set of the all nondecreasing, outer continuous processes as {P(·; A); A ∈ A} taking values in [0; 1] which are measurable (resp. adapted). Proposition 2 states that P0016 ∈ B (resp. P0016 ∈ B0003 ) when 0016 is a fuzzy (stopping) set. The following proposition states the converse: Proposition 3. Let P ∈ B0003 (resp. P ∈ B0003 ). Then the random set if t ¿ 0; Lev!; t

0016(!; t) = Lev!; s if t = 0;

(4)

s

where Lev!; t =

0004

{A ∈ A: P(!; A) ¡ t}

is a fuzzy (stopping) set and P[P0016 (·; A) = P(·; A); any A] = 1. Proof. It is a consequence of (2). Corollary 4. P ∈ B0003 corresponds to a stopping set i9 P(·; A) ∈ {0; 1}. The conditions that make a family of stopping sets be an optional increasing path may be transported on [0; 1] B0003 to fuzzy optional increasing paths in the following way: De0016nition 4. A fuzzy optional increasing path is a family P = {P t ; t ∈ [0; 1]} ∈ 0003 [0; 1] B s.t.

132

(1) (2) (3) (4) (5) We

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

P t ∈ B0003 ∀t ∈ [0; 1]; P 0 (!; A) = 1; for any A ∈ A; P 1 (!; A) = 0; for any A ∈ A; A 0004= T ; P s (!; ·) ¿ P t (!; ·) if s 6 t; P t (!; gn2 (A)) ¿ P s (!; A) if s 6 t ¡ s + 2−0019(n) . denote by P0003 the set of all the fuzzy optional increasing paths.

Lemma 5. {P t ; t ∈ [0; 1]} ∈ P0003 corresponds to an optional increasing path i9 P t (· ; A) ∈ {0; 1} for any t ∈ [0; 1]. Proof. It is a consequence of Corollary 4. Remark 7. We only underline that; if s 6 t ¡ s + 2−0019(n) ; we have P t (!; A) 6 P s (!; A) 6 P t (!; gn2 (A)):

(5)

3. Integration on A(u) The set-indexed bandit problem is expressed here as the maximization of a function $X de9ned on the set of the optional increasing paths by 000e (0016t )t∈[0; 1] 0013→ E X0016t dVt ; R+

where {XA ; A ∈ A(u)} is an (suNcient regular) integrable set-indexed stochastic process and {Vt ; t ∈ [0; 1]} is a bounded process with nondecreasing sample paths. We note that 000e 000f 000e 0010 E X0016t dVt = E X0016t (·;v) dv dVt ; R+

R+

[0;1]

since the fuzzy set obtained by a stopping set is constant. We give a de9nition of integration on A(u) s.t.

f(A)P0016 (·; dA) = f(0016(·; v)) dv; [0;1]

so that $X : 0002 → R will be extended to an aNne function &X : P0003 → R by setting: 000e 000f 0010 t t (P )t∈[0; 1] 0013→ E XA P (·; dA) dVt : R+

A

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

133

Let f be any bounded Borel function on A and 0016 be a fuzzy set. We denote

ˆ max(f[0016(!; v)]; 0) dv; f (0016)(!) = [0;1]

f P(0016)(!) =

[0;1]

max(−f[0016(!; v)]; 0) dv:

De0016nition 5. We say that a function f : A → R is integrable (and we denote it by f ∈ L1B [A]) if; for any fuzzy set 0016; f ˆ(0016)(!) ¡ + ∞ and fP(0016)(!) ¡ + ∞; and we de9ne f(0016)(!) := f ˆ(0016)(!) − f P(0016)(!): Let A; B ∈ A(u). We de9ne 0005 ◦ 0 if B ⊆ (A) ; 'B (A) = 1 otherwise;

(6) 0005

1A (B) =

so that, for any B ∈ A 0005 ◦ 0 if B ⊆ (0016(!; v)) ; 'B (0016(!; v)) = 1 otherwise;

1

if B ⊆ A;

0

otherwise 0005

1(0016(!; v)) (B) = ◦

◦

1

if B ⊆ (0016(!; v)) ;

0

otherwise:

Following this de9nition and (2), we have that

(1 − 1(0016(!; v))◦ (B)) dv: P(!; B) = 'B (0016(!; v)) dv = [0;1]

[0;1]

Remark 8. Let I be an interval of R+ of the form [0; s]. It is natural to denote 0005 0005 0 if I ⊆ [0; t); 1 if [0; t] ⊆ I; 'I (t) = 1I (t) = 1 otherwise; 0 otherwise and this fact explains our choice. Let f : A → R+ ∪ {+∞} be a nonnegative extended real function on A. Let if : R → A(u), 0004 if (t) := {A ∈ A: f(A) ¡ t}: We have if (s) ⊆ if (t) when s 6 t. De0016nition 6. We say that a bounded nonnegative real function f : A(u) → R is regular iA f(A) = limn fn (A); for any A ∈ A(u); where fn (A) =

n n2 −1 0011

i=0

i2−n ['if ([i+1]2−n ) (A) − 'if (i2−n ) (A)]:

134

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

We denote by L[A] the monotone class generated by the linear combinations of regular functions which are integrable. Proposition 6. C(A(u))∩L1B [A] ⊆ L[A] (C(A(u)) is the set of continuous function on A(u)). Proof. It is suNcient to prove that; given a set B ∈ A(u); the function 1B (A) belongs to L[A] (in fact; the monotone class generated by linear combinations of 1B ; B ∈ A(u) contains both C(A(u)) and L1B [A]). For any n ∈ N, we de9ne fnB (A) =

min

A∗ ∈An (u) A∗ *(gn (B))

=1−

'A∗ (gn (A))

max [1 − 'A∗ (gn (A))]

A∗ ∈An (u) A∗ *gn (B)

= 1 − fn0003B (A): We note that, if A ⊆ B, then A∗ * gn (A), for any A∗ * gn (B), and hence 'A∗ (gn (A))=1 and fnB (A) = 1, for any n ∈ N. If A * B, there will be an n ∈ N s.t. gn (A) * gn (B). Then fnB (A) = 0 and so 1B = inf fnB = 1 − supfn0003B . Since An ⊆ An+1 , then {fnB ; n ∈ N} is a monotone sequence of functions on A and then we have only to prove that fn0003B ∈ L[A], for each n ∈ N. Since 'A∗ is a regular function, then fn0003B ∈ L[A]. Proposition 7. The space L[A] is the space of the integrable functions on A(u). Proof. The proof follows by Proposition 6 and the fact that 'B (A) =

sup

f∈C(A(u)) 06f61

f(A)

f(A) = 0 when B ⊆ A

◦

since L1B [A] is a monotone class. • Let f be a bounded positive regular function on A and 0016 be a fuzzy set. We de9ne

f(A)P0016 (!; dA) := lim n

n n2 −1 0011

i2−n [P0016 (!; if ([i + 1]2−n )) − P0016 (!; if (i2−n ))]:

i=0

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

We have

f(0016)(!) =

0012

n

=

n n2 −1 0011

i2

−n

[0;1]

i=0

= lim n

0013 lim fn (0016(!; v)) dv n

[0;1]

= lim

135

['if ([i+1]2−n ) (0016(!; v)) − 'if (i2−n ) (0016(!; v))] dv

n n2 −1 0011

i2−n [P0016 (!; if ([i + 1]2−n )) − P0016 (!; if (i2−n ))]

i=0

f(A)P0016 (!; dA):

(7)

• It is not diNcult to show that the extension (via linear combinations and monotone class, as usual) of the integral operator to L[A] gives coherent de9nitions and all those 0003 de9nitions are well 0003posed. We only underline that, for any f ∈ L[A]; f(0016)(!) = f(A)P0016 (!; dA) and f(A)P0016 (!; dA) is a linear function on B0003 . • If 0016 does not depend on the second variable for some !0 (0016(!0 ; v) = A, for any v ∈ [0; 1]), we have

f(0016)(!0 ) = f(0016(!0 ; v)) dv = f(A): [0;1]

Then &X : P0003 → R, where t &X ((P )t∈[0; 1] ) = E

000f

R+

A

t

0010

000e

X (A) P (·; dA) dVt

is an aNne function on P0003 that extends $X : 0002 → R.

4. Compactness of fuzzy stopping sets and fuzzy o.i.p. We wish to study the convergence of generalized stopping sets and of the associated stopping variables, as in Baxter and Chacon (1977). Let G be a 9xed -algebra contained in F. De0016nition 7. Let {0016n ; n ∈ N} and 0016 be fuzzy sets. 0016n will be said to converge weakly G to 0016 on G (0016n ⇒ 0016) if the distribution of 0016n (!; v) on G × [0; 1] converges weakly to that of 0016(!; v) on G × [0; 1] for any G ∈ G. That is; if we de9ne f(0016n ) and f(0016) as in (6); G

a:s:

0016n ⇒ 0016 ⇔ E(f(0016n ) G) → E(f(0016) G)

when n → ∞

for each f ∈ C(A(u)) ∩ L[A]; where C(A(u)) is the set of continuous functions on A(u).

136

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

Let + = +({FA }) be the set of all fuzzy stopping sets. For any Y ∈ L1 (0014; G; P) and any f ∈ C(A(u)), let -(Y; f) : + → R be de9ned by -(Y; f)(0016) = E[Yf(0016)]. Let I the collection of all such - and T = T(G) be the topology on + generated by all - in I . Proposition 8. T is generated by -('G ; f); obtained as G runs over an L1 -dense subset of G and f runs over a sup-norm-dense subset of C(A(u)) ∩ L[A]. G

T

Corollary 9. 0016n ⇒ 0016 if and only if 0016n →0016. For any Y ∈ L1 (0014; F; P) and f ∈ L[A], let .0016 (Y; f) := -(Y; f)(0016) = E[Yf(0016)] .0016 will be called the distribution map for 0016. By (7), we have .0016 (Y; f) = E[Yf(0016)] 000f =E Y

[0;1]

0010000e f(0016v ) dv

000f 0010000e =E Y f(A)P0016 (·; dA) : For H ∈ F write .0016 ('H ; f) as .0016 (H; f) and similarly for K ∈ A(u) let .0016 (Y; 'K ) = .0016 (Y; K). Proposition 10. Let f ∈ L[A] such that f(A) 0004= 0 only if A ⊆ B0003 (we will also write that f ≡ 0 on (B; T ]). If 0016 is a fuzzy 0003 stopping set; then f(A)P0016 (·; dA) is FB -measurable. Conversely; if P ∈ B and f(A)P(·; dA) is FB -measurable for every function f ∈ L[A] ∩ C(A(u)) with support on [0; B]; then P ∈ B0003 . Proof. It is a consequence of Proposition 1 and the fact that

∗ P0016 (·; B ) = 'B∗ (0016(·; v)) dv: [0;1]

Remark 9. For any fuzzy set 0016; let us temporally restrict the distribution map .0016 to L1 (0014; F; P) × {L[A] ∩ C(A(u))}. Then .0016 has the following properties: (i) .0016 is a bilinear function on L1 (0014; F; P) × {L[A] ∩ C(A(u))}. (ii) • Y ¿ 0; f ¿ 0 imply .0016 (Y; f) ¿ 0. • .0016 (1; 1) = 1. • .0016 (Y; f) 6 0017Y 00171 0017f0017∞ for all Y; f. (iii) .0016 (Y; f) = .0016 (E[Y FB ; f) for any Y ∈ L1 (0014; F; P) and any function f ∈ L[A] ∩ C(A(u)) with support on [0; B]. Lemma 11. Let . be a map satisfying (i) – (iii) in Remark 9. Then there exists a unique (P × 0[0; 1] ) fuzzy stopping set 0016 s.t. .0016 = .. (Note: 0[0; 1] denotes the Lebesgue measure on [0; 1].)

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

137

Proof. For any Y ∈ L1 (0014; F; P) with 0 6 Y 6 1; 0017Y 00171 + 00171 − Y 00171 = 1 = .(1; 1) = .(Y; 1) + .(1 − Y; 1) and 0017Y 00171 ¿ .(Y; 1); 00171 − Y 00171 ¿ .(1 − Y; 1). Hence .(Y; 1) = 0017Y 00171 . By continuity; .(Y; 1) = E[Y ] for any Y ∈ L1 (0014; F; P). For any Y ∈ L1 (0014; F; P), the map .(Y; ·) is linear on L[A] ∩ C(A(u)) and hence 1(B) = .(Y; 1B ) de9nes a bounded Borel measure on BT . 1(T ) = E[Y ], and if Y ¿ 0 then 1(·) ¿ 0. One may0003 extend . to all Y ∈ L1 (0014; F; P), and all functions f ∈ L[A] by de9ning .(Y; f) = T f(A) .(Y; dA). Clearly . is bilinear, Y ¿ 0, f ¿ 0 imply .(Y; f) ¿ 0, .(Y; 1) = E[Y ] and .(Y; f) 6 0017Y 00171 0017f0017∞ . Using the outer continuity of {FA } and the fact that .(Y; ·) is continuous under bounded pointwise limits, it is easy to see that (iii) in Remark 9 holds for all Y ∈ L1 (0014; F; P) and any bounded Borel function f s.t. f = 0 on (B; T ]. For B in a countable base of A(u), let c(B) be a bounded FB -measurable function such that .(Y; B)=E[Yc(B)] for any Y ∈ L1 (0014; F; P). We may choose c(B) s.t. c(T )=1, c(B) ¿ 0. Clearly, c(B) 6 c(B∗ ) whenever B ⊆ B∗ (P-a.s.), so we may assume that c(B) 6 c(B∗ ) everywhere, by replacing c(B∗ ) by sup{c(B): B ⊆ B∗ }. Let P(!; ·) be the probability on A(u) such that P(!; B) = inf {c(B∗ ; !): B ⊂ B∗ } for each B ∈ A(u) (P(!; T ) = 1, P(!; ∅) = 0). By outer continuity, P(·; B) is FB measurable for any B ∈ A and hence P ∈ B0003 . By Proposition 3, there exists 0016 s.t. P0016 (!; B) = P(!; B). For any Y ∈ L1 (0014; F; P) and B ∈ A(u) .(Y; B) = =

inf

.(Y; B∗ )

inf

{E[Yc(B∗ )]}

B⊂B∗ ;B∗ ∈An (u)

B⊂B∗ ; B∗ ∈An (u)

=E Y

inf

∗

000e

{c(B )}

B⊂B∗ ; B∗ ∈An (u)

= E[YP0016 (·; B)] = .0016 (Y; B): Hence . = .0016 . 0016 is unique by Lemma 12, so the lemma is proved. Let + = +({FA }) be the set of fuzzy stopping sets, and let 3 = 3({FA }) be the set of maps . satisfying (i) – (iii) in Remark 9. There exists a natural map 4 : + → 3 which takes each member of + to its distribution map 4(0016) = .:

(8)

Lemma 11 says that if {FA ; A ∈ A(u)} is outer continuous then 4 is an onto map, and 4 is one-to-one (P × 0[0; 1] -a.s.).

138

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

0003 It is easy to check that 0016(!; v) is the intersection of the largest sets B such that f(A) P0016 (!; dA) ¡ v+0010 for some nonincreasing f in C(A(u))∩L[A] with 0 6 f 6 1 and f = 0 on [B; T ]. Let 5 be another fuzzy set. Clearly the following statements are equivalent: • 0016(!; ·) ⊆ 5(!; ·). • 0003P0016 (!; ·) ¿ P5 (!; ·). 0003 • f(A) P0016 (!; dA) ¿ f(A) P5 (!; dA), for all nonincreasing functions f ∈ {C(A(u)) ∩ L[A]}. Lemma 12. Let 0016 and 5 be fuzzy sets. Suppose .0016 (Y; f) ¿ .5 (Y; f) for every Y ¿ 0 in L1 (0014; F; P) and every nonincreasing f in {C(A(u)) ∩ L[A]}. Then 0016 ⊆ 5 (P × 0[0; 1] -a.s.). Proof. Choose a countable dense set D of nonincreasing functions in C(A(u))∩L[A]. For any f ∈ D; 000e 000e

Y f(A) P0016 (!; dA) dP ¿ Y f(A) P5 (!; dA) dP for all Y ¿ 0 in L1 (0014; F; P). Hence

f(A) P0016 (·; dA) ¿ f(A) P5 (·; dA);

P-a:s:

Let 00141 ∈ F with P[0014 00141 ] = 0 s.t.

f(A) P0016 (!; dA) ¿ f(A) P5 (!; dA) for all f ∈ D; ! ∈ 00141 . Then the same inequality holds on 00141 for all nonincreasing f ∈ {C(A(u)) ∩ L[A]}. Then; as stated above; 0016 ⊆ 5 on 00141 ; so the lemma is proved. Lemma 13. Let 0016 and 5 be fuzzy sets. Let G be a sub--algebra of F. The following conditions are equivalent: (i) .0016 (Y; f) = .5 (Y; f); for all Y ∈ L1 (0014; G; P); f ∈ {C(A(u)) ∩ L[A]}. (ii) E(f(0016) G) = E(f(5) G); for any f ∈ C(A(u)) ∩ L[A]. The proof is immediate. Lemma 14. Let 0016 be a fuzzy set. Let G be a sub--algebra of F. Then there exists a unique (P × 0[0; 1] -a.s.) G-fuzzy set 5 for which (ii) in Lemma 13 holds. Proof. Restrict .0016 to L1 (0014; G; P)×C(T ). Apply Lemma 11 with F=FA =G to obtain 5. Apply Lemma 13 to conclude that (ii) holds. Uniqueness follows also from Lemma 11 with F = FA = G. It is easy to check that if 0016 happens to be a fuzzy stopping set then 5 can be chosen to be a {FA ∩G}-fuzzy stopping set provided that {FA ; A ∈ A(u)} is outer continuous

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

139

and E[E[ · G] FA ] = E[ · GA ∩ G]

for all A ∈ A(u):

Theorem 15. If {FA ; A ∈ A(u)} is outer continuous then (+; T) is compact. Proof. Let 4 be the map de9ned in (8). For each Y ∈ L1 (0014; F; P) and f ∈ C(T ); let : 3 → R be de9ned by (Y; f)(.) = .(Y; f). Let 8 be the set of all such . Let C be the topology on 3 generated by all in 8. It is easy to see that T = 4−1 (C). C is compact; by the same argument used to prove that unit ball in the dual of a normed linear space is compact. Since 4 is onto by Lemma 11; T is also compact. Theorem 16. The set B (resp. B0003 ) has the following properties: (i) B (resp. B0003 ) is convex. (ii) The set of the extremal elements in B0003 is the set of those which correspond to the set of the generalized stopping set. (iii) B (resp. B0003 ) is compact in the topology induced by (+; T). Proof. (i) The convex combination of two (adapted) increasing outer continuous processes with values in [0; 1] is an (adapted) increasing outer continuous process with values in [0; 1]. (ii) Suppose that there exists A s.t. P[{!: 0 ¡ P(!; A) ¡ 1}] ¿ 0. Then we may choose a convenient 0 such that if P 0003 (!; B) =

P(!; B) ∧ 0 0

P 00030003 (!; B) =

(P(!; B) − 0) ∨ 0 1−0

and

for any B ∈ A; then P 0003 and P 00030003 are distinct. We have P = 0P 0003 + (1 − 0)P 00030003 . Moreover; P 0003 and P 00030003 are nondecreasing; compatible and outer continuous; since P is. By Corollary 4; if P does not correspond to a stopping set; it cannot be one of the extremal elements of B0003 . (iii) It is a consequence of Theorem 15. Proposition 17. The set P0003 has the following properties: (i) P0003 is convex. (ii) The set of the extremal elements in P0003 is the set of those which correspond to the set of the optional increasing path. (iii) P0003 is compact for the product topology. Proof. (i) It is a consequence of Theorem 16 and the fact that a convex combination is a linear function.

140

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

(ii) If P={P t ; t ∈ [0; 1]} ∈ P0003 ; we can de9ne two elements 1 P and 2 P by the formulas 1 t

P (!; A) = min(2P t (!; A); 1);

2 t

P (!; A) = max(2P t (!; A) − 1; 0):

It is easy to check that 1 P; 2 P ∈ P0003 and 2P = 1 P + 1 P and so P can be an extremal element in P0003 only if P= 1 P= 2 P. Then P t (!; A) ∈ {0; 1} and the proof is 9nished via Lemma 5. (iii) It is suNcient to note that P0003 is a closed subset of [0; 1] B0003 and thus is compact (as in Dalang; 1990; this set is closed since it is de9ned by (1) – (5) of De9nition 4). 5. Proof of the Main Theorem Let M denotes the deterministic elements of P0003 , i.e., 0005 = {P t ; t ∈ [0; 1]} ∈ M provided each 9t : A(u) → [0; 1] is a nondecreasing outer continuous function such that 9t (T ) = 1 and • 9s (·) ¿ 9t (·) if s 6 t, • 9t (gn2 (A)) ¿ 9s (A) if s 6 t ¡ s + 2−0019(n) . As in (5), we may aNrm that if s 6 t ¡ s + 2−0019(n) , 9t (A) 6 9s (A) 6 9t (gn2 (A)):

(9)

Let x be an integrable function on A(u), and let 0005(x) : [0; 1] → R be de9ned by x(A) 9t (dA) when t ∈ [0; 1); 0005(x)(t) = T x(T ) when t = 1: Lemma 18. If x : A(u) → R is a continuous function on A(u); then {0005(x); 0005 ∈ M} is an equicontinuous set of functions on [0; 1]; i.e.; for all 0010 ¿ 0; there exists ; ¿ 0 such that if t − tQ ¡ ; then 0005(x)(t) − 0005(x)(tQ ) ¡ 0010

(10)

for any 0005 ∈ M. Proof. Since a continuous function on a compact set is uniformly continuous; then (10) has to be checked for all 9xed t ∈ [0; 1]. The case t = 1 follows immediately from the continuity of x at 1; so we assume t ∈ [0; 1). Now 0014 0014 0014 0014 0005(x)(t) − 0005(x)(tQ) = 00140014 x(A)[9t (dA) − 9tQ(dA)]00140014 A

0014 0014 = 00140014

[0;1]

0014 0014 [x(0016 (v)) − x(0016 (v))] dv00140014 : t

tQ

(11)

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

141

We must prove that for any n ∈ N; there exists k ∈ N s.t. 0014 0014 0014 0014 −k t tQ 0014 Q t − t ¡ 2 ; 0005 ∈ M ⇒ 0014 x(A)[9 (dA) − 9 (dA)]00140014 ¡ 2−n : T

Since x is uniformly continuous on a compact set by Remark 3; then d(A; B) ¡ ;0010 implies x(A) − x(B) ¡ 0010 and hence; by (11); we can prove that t − tQ ¡ 2−k implies d(0016t (v); 0016tQ(v)) ¡ ; for any v ∈ [0; 1]. First, let us choose N ∈ N s.t. supA d(A; gN2 (A)) ¡ ;. By (9) and (4), if k = 0019(N ), t − tQ ¡ 2−k implies d(0016t (v); 0016tQ(v)) ¡ ; for any v ∈ [0; 1]. The proof of the following result will follow that of Dalang (1990). We will write it for completeness. Lemma 19. Suppose E[supA∈A(u) XA ] ¡ ∞. Then &X is continuous on P0003 . Proof. Let V k denote the increasing process de9ned by k

Vtk

=

2 0011

SVjk I{j2−k 6t}

where SVjk = Vj2−k − V(j−1)2−k :

j=1

Since E[supA∈A(u) XA ] ¡ ∞; it is not diNcult to see using Lemma 18 that 0014 0014

0014 0014 sup 00140014 9(X )(t) dVt − 9(X )(t) dVtk 00140014 → 0 P-a:s: k→∞ 9∈=A

[0;1]

[0;1]

Fix 0010 ¿ 0. Again since E[supA∈A(u) XA ] ¡ ∞; it follows that we may choose k ∈ N s.t. 0014 0014000e

0014 0014 0010 k0014 0014 E sup 0014 9(X )(t) dVt − 9(X )(t) dVt 0014 ¡ : (12) 3 9∈=A [0;1] [0;1] Fix P ∈ P0003 ; and de9ne an open set O of P0003 by 0015 0016 ˜ )(j2−k ) − P(X )(j2−k ))SVjk ] ¡ 0010 2−k ; j = 1; : : : ; 2k : O = P˜ ∈ P0003 : E[(P(X 3 Using (12); we see that for P˜ ∈ O; 0014 000e 000e0014 0014 0014 0014E ˜ P(X )(t) dVt 00140014 P(X )(t) dVt − E 0014 [0;1] [0;1] 0014 000e 000e0014 0014 0010 00140014 k k 0014 ˜ ¡ 2 + 0014E P(X )(t) dVt 0014 ¡ 0010 P(X )(t) dVt − E 3 [0;1] [0;1] by the de9nitions of O and V k . This completes the proof. Proof of the Main Theorem. This proof is now similar to that of Dalang (1990); Mazziotto and Millet (1987). Note that (A(u); d) is a metric space s.t. its topology has a countable space (and hence, by Bourbaki (1966, IX, Section 2.8 Proposition 12), it is homeomorphic to a subspace of I N , where I is the interval [0; 1] in R).

142

G. Aletti, E. Merzbach / Stochastic Processes and their Applications 101 (2002) 127 – 142

Then, by the proof of Dalang (1989, Proposition 7.1), there is a nonincreasing sequence of processes (XAn )n∈N (where E[supA∈A(u) XAn ] ¡ ∞) s.t. XA (!) = lim ↓ XAn (!); n→∞

∀A ∈ A(u); ∀! ∈ 0014:

Since dVt is a nonnegative measure, we obtain lim ↓ &X n (P) = &X (P);

n→∞

∀P ∈ P0003 :

By Lemma 19, this shows that & is upper semicontinuous on P0003 . Hence & attains its maximum on P0003 and since & is aNne, this maximum is attained at an extremal element of P0003 (see Bourbaki, 1981, II.58, Proposition 1). Proposition 17 completes the proof. References Aletti, G., 2001. On diAerent topologies for set-indexing collections. Statist. Probab. Lett. 54 (1), 67–73. Baxter, J.R., Chacon, R.V., 1977. Compactness of stopping times. Z. Wahrsch. Verw. Geb. 40 (3), 169–181. Bourbaki, N., 1966. Elements of Mathematics. General Topology. Parts 1 and 2. Hermann, Paris. X ements de mathXematique (Elements of Bourbaki, N., 1981. Espaces vectoriels topologiques, new Edition. ElX mathematics), Masson, Paris, (Chapitres 1 aY 5). Dalang, R.C., 1989. Optimal stopping of two-parameter processes on nonstandard probability spaces. Trans. Amer. Math. Soc. 313 (2), 697–719. Dalang, R.C., 1990. Randomization in the two-armed bandit problem. Ann. Probab. 18 (1), 218–225. Gittins, J.C., 1989. Multi-armed Bandit Allocation Indices. Wiley, Chichester (with a foreword by Peter Whittle). HMurzeler, H.E., 1985. The optional sampling theorem for processes indexed by a partially ordered set. Ann. Probab. 13 (4), 1224–1235. IvanoA, G., Merzbach, E., 2000. Set-Indexed Martingales. Chapman & Hall=CRC Press, London=Boca Raton, FL. IvanoA, G., Merzbach, E., 2002. Random censoring in set-indexed survival analysis. Ann. Appl. Probab., in preparation. Kaspi, H., Mandelbaum, A., 1998. Multi-armed bandits in discrete and continuous time. Ann. Appl. Probab. 8 (4), 1270–1290. Kurtz, T.G., 1980. The optional sampling theorem for martingales indexed by directed sets. Ann. Probab. 8 (4), 675–681. Mandelbaum, A., 1987. Continuous multi-armed bandits and multiparameter processes. Ann. Probab. 15 (4), 1527–1556. Mandelbaum, A., 1988. Navigating and stopping multiparameter bandit processes. In: Fleming, W., Lions, P.L. (Eds.), Stochastic DiAerential Systems, Stochastic Control Theory and Applications. Springer, New York, pp. 339 –372. Mazziotto, G., Millet, A., 1987. Stochastic control of two-parameter processes application: the two-armed bandit problem. Stochastics 22 (3– 4), 251–288.