Learning incomplete models using dominant markets

post by Vanessa Kosoy (vanessa-kosoy) · 2017-04-28T09:57:16.000Z · LW · GW · None comments

% operators that are separated from the operand by a space

% operators that require brackets

% operators that require parentheses

% Paper specific

This post is formal treatment of the idea outlined here.

Given a countable set of incomplete models, we define a forecasting function that converges in the Kantorovich-Rubinstein metric with probability 1 to every one of the models which is satisfied by the true environment. This is analogous to Blackwell-Dubins merging of opinions for complete models, except that Kantorovich-Rubinstein convergence is weaker than convergence in total variation. The forecasting function is a dominant stochastic market for a suitably constructed set of traders.

Appendix A contains the proofs. Appendix B restates the theorems about dominant stochastic markets for ease of reference. Appendix C states a variant of the Michael selection theorem due to Yannelis and Prabhakar which is used in Appendix A.


Given a metric space, and , .

Given a topological space:

Given and measurable spaces, is a Markov kernel from to . For any , we have . Given , is the semidirect product of and and is the pushforward of by .

Given , Polish spaces, Borel measurable and , we denote the set of Markov kernels s.t. is supported on the graph of and . By the disintegration theorem, is always non-empty and any two kernels in coincide -almost everywhere.


Consider any compact Polish metric space and its metric. We denote the Banach space of Lipschitz continuous functions with the norm

(as before, with the weak topology) can be regarded as a compact subset of (with the strong topology), yielding a metrization of which we will call the Kantorovich-Rubinstein metric :

In fact, the above differs from the standard definition of the Kantorovich-Rubinstein metric (a.k.a. 1st Wasserstein metric, a.k.a. earth mover's metric), but this abuse of terminology is mild since the two are strongly equivalent.

Now consider convex. We will describe a class of trading strategies that are designed to exploit any .

#Definition 1

Let . is said to be an -representative of when for all , we have

#Lemma 1

Consider another compact Polish space and closed. For any , define by

Assume that for any , is convex. Then, for any , there exists measurable w.r.t. and s.t. for all , is an -representative of .

For each , let be a compact subset of ( is arbitrary). Denote

is a compact subset of . We will regard it as equipped with the Euclidean metric. Denote

is a compact Polish space. For each we denote the projection mapping. Given and , we have and .

The following definition provides a notion of updating an incomplete model by observations:

#Definition 2

Consider . For any and , we define by

Note that the limit in the definition above need not exist for every .

Denote the convex hull of and define by

Finally, we define to be the closure of . Given , we define by

Note that the above definition uses the Euclidean metric on . This is the only place through which the assumption that is a compact subset of (rather than an arbitrary compact Polish space) enters. This is used the in the proof of Lemma 2 below, via the Lebesgue differentiation theorem.

Fix a family of metrizations of : . The reason we need a family rather than a single metric is that convergence in is trivial unless we renormalize the metric for each . On the other hand, completely arbitrary renormalization is allowed. For example, assuming the diameters of are uniformly bounded, we can take

Here, are required to satisfy . To get a non-trivial result, we need the to fall slower with as increases. The stronger we make this trend, the stronger conclusion we get (although it always remains weaker than convergence in total variation).

#Lemma 2

Consider and . Let be a metastrategy s.t. for each and , is an -representative of (relatively to ). Then, is profitable for any .

Combining Theorem B.2 and Lemma 2, it is easy to get the following:

#Corollary 1

Consider , and a metastrategy s.t. for each and , is an -representative of . Let be a market which dominates . For every , denote the Kantorovich-Rubinstein metric associated with . Then, for any and -almost any :

Thus, if we construct a set of traders as in Corollary 1 where corresponds to , then a market dominating all of these traders would have to converge to with -probability 1. Putting this together with Lemma 1 (so that as above actually exists) and Theorem B.1 we finally get

#Theorem 1

Consider any countable. Then, there exists a market s.t. for any , and -almost any :

This leaves an interesting open question, namely whether the counterpart of Theorem 1 with replaced by total variation distance is true.

##Appendix A

#Proposition A.1

Let be a compact Polish space, and . Then, there exists s.t. and for all , .

#Proof of Proposition A.1

Without loss of generality, assume that (if the theorem is trivial, otherwise we can rescale everything by a scalar). Using the compactness of , choose a finite set s.t.

Using the Goldstine theorem, choose s.t. and for any

Consider any . Choose s.t. . We get

#Proposition A.2

Let be a compact Polish space and convex. Consider any and s.t. . Then, there exists s.t.

#Proof of Proposition A.2

Define by

By the Hahn-Banach separation theorem, there is s.t. for all , . Multiplying by a scalar, we can make sure that . For any , we can choose s.t. and . For any , and therefore

Taking to 0 we get . Applying Proposition A.1 for , we get s.t.

#Proposition A.3

Let be a compact Polish space, convex and . Let (an open set) be defined by

Then, there exists continuous s.t. for all

#Proof of Proposition A.3

Define by

By Proposition A.2, for any , . Clearly, is convex. Fix and consider . Consider any , and take s.t.

Define . Obviously is open and , hence is open. Applying Theorem C, we get the desired result.

#Proposition A.4

Let be a compact Polish space, convex and . Then, there exists an -representative of .

#Proof of Proposition A.4

Let be defined by

Use Proposition A.3 to obtain . Define by

Obviously is continuous in . Consider any and s.t. . We have and hence . Therefore, is continuous everywhere.

#Proof of Lemma 1

Define by

Define . It is easy to see that are closed and therefore also. Define by

is closed since it is the projection of and is compact. The are compact, therefore for some , and hence if and only if the following two conditions hold:

Define by

is locally closed and in particular . Define by

is the projection of and is compact, therefore is . Let be the complement of . is and in particular Borel. As easy to see, if and only if is an -representative of .

For any , is closed since

Moreover, is non-empty by Proposition A.4.

Consider any open. Then, is Borel and therefore its image under the projection to is analytic and in particular universally measurable. Applying the Kuratorwsi-Ryll-Nardzewski measurable selection theorem, we get the desired result.

#Proposition A.5

Consider a compact Polish space, , a compact subset of , continuous, and . Then, for -almost any

#Proof of Proposition A.5

Let be dense in . For any and we denote the characteristic function of and the characteristic function of . For any and we have and

In particular, the above holds for -almost any . Applying the Lebesgue differentiation theorem, we conclude that for -almost any

Now consider any . For any , there is s.t. and therefore


Taking to 0, we conclude that

#Proof of Lemma 2

Fix any and . By Proposition A.5, for -almost any

Therefore, . Since is an -representative of , for any

When , , hence for any , . We get

#Proof of Corollary 1

By Lemma 2, is profitable for . By Theorem B.2, for -almost any

By Proposition A.5, and therefore

We get

#Proof of Theorem 1

Consider any and a positive integer . By Lemma 1, for any , there exists measurable s.t. for all , is a -representative of . We fix such a for each and . It is easy to see that the -diameter of is at most 2, therefore and is a trading metastrategy. By Theorem B.1, there is a stochastic market that dominates for all and . By Corollary 1, for any , , positive integer and -almost any

It follows that

##Appendix B

The following are the theorems about dominant stochastic markets proven before.

#Theorem B.1

Given any countable set of traders , there is a market s.t. dominates all .

#Theorem B.2

Consider , , a trading metastrategy profitable for and a market. Assume dominates . Then, for -almost any :

##Appendix C

The following variant of the Michael selection theorem appears in Yannelis and Prabhakar (1983) as Theorem 3.1.

#Theorem C

Consider a paracompact Hausdorff topological space and a topological vector space. Suppose is s.t.

(i) For each , .

(ii) For each , is convex.

(iii) For each , is open.

Then, there exists continuous s.t. for all , .

None comments

Comments sorted by top scores.