THE STRONG LAW OF LARGE NUMBERS FOR SEQUENTIAL DECISIONS UNDER UNCERTAINTY

We combine optimization and ergodic theory to characterize the optimum long-run average performance that can be asymptotically attained by n onanticipating sequential decisions. Let {X(t)} be a stationary ergodi c process, and suppose an action b(t) must be selected in a space B wi th knowledge of the t-past (X0,...,X(t-1)) at the beginning of every p eriod t greater-than-or-equal-to 0. Action b(t) will incur a loss l(b( t), X(t)) at the end of period t when the random variable X(t) is reve aled. We prove under mild integrability conditions that the optimum st rategy is to select actions that minimize the conditional expected los s given the currently available information at each step. The minimum long-run average loss per decision can be approached arbitrarily close ly by strategies that are finite-order Markov, and under certain conti nuity conditions, it is equal to the minimum expected loss given the i nfinite past. If the loss l(b, x) is bounded and continuous and if the space B is compact, then the minimum can be asymptotically attained, even if the distribution of the process {X(t)} is unknown a priori and must be learned from experience.