The two-armed-bandit problem with time-invariant finite memory

This paper solves the classical two-armed-bandit problem under the finite-memory constraint described below. Given are probability densitiesp_0andp_1, and two experimentsAandB. It is not known which density is associated with which experiment. Thus the experimental outcomeYof experimentAis as likely to be distributed according top_0as it is to be distributed according top_1. It is desired to sequentially choose an experiment to be performed on the basis of past observations according to the algorithmT_n = f(Tₙ₋₁, e_n, Y_n), e_n = e(Tₙ₋₁), whereT_n ∈ \{1, 2, ⋯, m\}is the state of memory at timen, e_n ∈ \{A, B\}is the choice of experiment, andY_n, is the random variable observation. The goal is to maximize the asymptotic proportionrof uses of the experiment associated with densityp_0. Letl(y) = p_0 (y) / p_1 (y), and letl̄and{l̄}denote the almost everywhere greatest lower bound and least upper bound onl(y). Let1 = max {{l̄}, 1/l̄}. Then the optimal value ofr, over allm-state algorithms(f, e), will be shown to belᵐ⁻¹ / (lᵐ⁻¹ + 1). Ane-optimal family ofm-state algorithms will be demonstrated. In general, optimal algorithms do not exist, ande-optimal algorithms require artificial randomization.