The strong law of large numbers for sequential decisions under uncertainty

Combines optimization and ergodic theory to characterize the optimum long-run average performance that can be asymptotically attained by nonanticipating sequential decisions. Let {X_t} be a stationary ergodic process, and suppose an action b_t must be selected in a space ℬ with knowledge of the t-past (X₀, ···, X_t-1) at the beginning of every period t⩾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 revealed. The author proves under mild integrability conditions that the optimum strategy is to select actions that minimize the conditional expected loss given the currently available information at each step. The minimum long-run average loss per decision can be approached arbitrarily closely by strategies that are finite-order Markov, and under certain continuity conditions, it is equal to the minimum expected loss given the infinite past. If the loss l(b, x) is bounded and continuous and if the space ℬ 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