Author: Volodya

Many decision problems can be represented in the form
FOR n=1,2,…:
— Reality chooses a datum x_n.
— Decision Maker chooses his decision d_n.
— Reality chooses an observation y_n.
— Decision Maker suffers loss L(y_n,d_n).
END FOR.
The observation y_n can be, for example, tomorrow’s stock price and the decision d_n the number of shares Decision Maker chooses to buy. The datum x_n ideally contains all information that might be relevant in making this decision. We do not want to assume anything about the way Reality generates the observations and data.

Suppose there is a good and not too complex decision rule D mapping each datum x to a decision D(x). Can we perform as well, or almost as well, as D, without knowing it? This is essentially a special case of the problem of on-line learning.

This is a simple result of this kind. Suppose the data x_n are taken from [0,1] and L(y,d)=|y–d|. A norm ||h|| of a function h on [0,1] is defined by

||h||² = (Integral₀¹ h(t) dt)² + Integral₀¹ (h'(t))² dt. Decision Maker has a strategy that guarantees, for all N and all D with finite ||D||, Sum_n=1^N L(y_n,d_n) is at most Sum_n=1^N L(y_n,D(x_n)) + (||2D–1|| + 1) N^1/2. Therefore, Decision Maker is competitive with D provided the “mean slope” (Integral₀¹ (D'(t))²dt)^1/2 of D is significantly less than N^1/2. This can be extended to general reproducing kernel Hilbert spaces of decision rules and to many other loss functions.

It is interesting that the only known way of proving this result uses a non-standard (although very old) notion of probability. The standard definition (“Kolmogorov’s axiomatic“) is that probability is a normalized measure. The alternative is to define probability in terms of games rather than measure (this was started by von Mises and greatly advanced by Ville, who in 1939 replaced von Mises’s awkward gambling strategies with what he called martingales). This game-theoretic probability allows one to state the most important laws of probability as continuous strategies for gambling against the forecaster: the gambler becomes rich if the forecasts violate the law. In 2004 Akimichi Takemura noticed that for every such strategy the forecaster can play in such a way as not to lose a penny. Takemura’s procedure is simple and constructive: for any continuous law of probability we have an explicit forecasting strategy that satisfies that law perfectly. We call this procedure defensive forecasting. Takemura’s version was about binary observations, but it has been greatly extended since.

Now let us see how we can achieve the goal Sum_n=1 ^N L(y_n,d_n) < Sum_n=1^N L(y_n,D(x_n)) + (something small). This would be easy if we knew the true probabilities for the observations. At each step we would choose the decision with the smallest expected loss and the law of large numbers would allow us to prove that our goal would be achieved. Alas, we do not know the true probabilities (if they exist at all). But with defensive forecasting at our disposal we do not need them: the fake probabilities produced by defensive forecasting are ideal as far as the law of large numbers is concerned. The rest of the proof is technical details.