A Note on Memoryless Rules for Controlling Sequential Control Processes

We are concerned with a dynamic system which at times t = 0, 1, ⋯ is observed to be in one of a finite number of states. We shall denote the space of possible states by I. After each observation the system is "controlled" by making one of a finite number of possible decisions. We shall denote by Kᵢ the set of possible decisions when the system is in state i, i ε I. Let ₜ\, t = 0, 1, ⋯, denote the sequence of observed states and \Δₜ\, t = 0, 1, ⋯, the sequence of observed decisions. The fundamental assumption regarding ₜ, Δₜ\, t = 0, 1, ⋯, is {equation*}{A}P(Yₜ₊₁ = j Y_0, Δ0, ⋯,tY_t = i, Δ_t = k) = qᵢⱼ(k), t = 0, 1, ⋯; j ε I; k ε K_i{equation*} where the qᵢⱼ(k)'s are non-negative numbers satisfying ∑ⱼ qᵢⱼ(k) = 1, k ε Kᵢ; i ε I. A rule for making successive decisions can be summarized in the form of a collection of non-negative functions Dₖ(Y₀, Δ₀, ⋯, Δₜ₋₁, Yₜ), t = 0, 1, ⋯; k ε KYₜ, where in every case ∑ₖ Dₖ(·) = 1. We set P(Δₜ = k Y₀, Δ₀, ⋯, Δₜ₋₁, Yₜ) = Dₖ(Y₀, D₀, ⋯, Δₜ₋₁, Yₜ) for t = 0, 1, ⋯. Thus, given Y₀ = i and any rule R for making successive decisions, the sequence ₜ, Δₜ\, t = 0, 1, ⋯, is a stochastic process with its probability measure dependent upon the rule R. We refer to such a process as a sequential control process. Let C denote the class of all possible rules; $C'$ denote the class of all rules such that Dₖ(Y₀, Δ₀, ⋯, Δₜ₋₁, Yₜ = i) = Dᵢₖ, t = 0, 1, ⋯; k ε Kᵢ; i ε I. That is, $C'$ is the class of all rules such that the mechanism for making a decision at any time t is dependent only on the state of the system at time t. A rule R ε C' has a stationary Markovian character and, indeed, when R ε C' is used, the resulting process ₜ\, t = 0, 1, ⋯, is a Markov chain with stationary transition probabilities. We let $C''$ denote the subclass of $C'$ where the Dᵢₖ's are zero or one. Rules in $C'$ allow for randomization; the rules in $C''$ are non-randomized. For a given R ε C and initial state Y₀ = i, let XT,j,k,R(i) = (T + 1)⁻¹∑Tₜ₌₀ PR(Yₜ = j, Δₜ = k Y₀ = i) and let XT,R(i) denote the vector of components XT,j,k,R(i) for all k ε Kⱼ and j ε I. Denote by HR(i) the set of limit points of XT,R(i) as T → ∞. Let H(i) = Rε C HR(i), H'(i) = Rε C' HR(i), H''(i) = Rε C'' HR(i); and let H̄'(i) and H̄''(i) denote the convex hulls of $H'(i)$ and $H''(i)$, respectively. In [5] was proved Theorem 1. (a) H'(i) = H''(i) ⊃ H(i). (b) If the Markov chain corresponding to R is irreducible for every R ε C'', then H''(i) = H'(i) = H(i) = iε I H(i). Examples were given in [4] and [5] showing that $H(i)$ can be larger than $H'(i)$. In (b) the irreducibility assumption can be weakened to the condition that for each R ε C'' the corresponding Markov chain has, at most, one ergodic class. Blackwell [1], [2], and Maitra [6] have considered memoryless rules. By a memoryless rule we mean a rule R such that Dₜ(Y₀, Δ₀, ⋯, Δₜ₋₁, Yₜ = i) = D⁽ᵗ⁾ᵢₖ t = 0, 1, ⋯, k ε Kᵢ, i ε I. That is, with a memoryless rule the mechanism for making a decision is a function of the time t and the state i at time t. The memoryless rules of Blackwell and Maitra are non-randomized; i.e., D⁽ᵗ⁾ᵢₖ = 0 or 1. We shall let CM denote the class of memoryless rules (both randomized and non-randomized). Thus C ⊃ CM ⊃ C' ⊃ C''. If R ε CM - C', then ₜ\, t = 0, 1, ⋯, is a finite state Markov chain with non-stationary transition probabilities. We remark that it is the memoryless rules (non-randomized) that are considered the rules of interest in the usual finite horizon dynamic programming problems. See Blackwell [2] for interesting remarks along these lines. We are concerned with optimization problems where the criterion to be optimized are functions of the points in $H(i)$. In [5] it was shown that one can construct problems where the optimal rule is in $C - C'$. This can occur, e.g., if the criterion to be optimized is a linear functional over the points in $H(i)$ but where a solution must also satisfy one or more linear constraints in $H(i)$. It is for the purpose of treating optimization problems of this kind that we are interested in the limit points of XT,R(i) for rules belonging to the various important sub-classes of C. Let HM(i) = Rε CM HR(i). The result of this note (which is similar to Theorem 4.1 of [7]) is Theorem 2. H(i) = HM(i). In fact, for any R ε C there exists an R₀ ε CM such that XtR₀(i) = XtR(i) for all t. Proof. Define R₀ by Dⱼₖ(t) = PR₀(Δₜ = k Yₜ = j) = PR(Δₜ = k Yₜ = j, Y₀ = i). It is enough to show that for all t, k ε Kⱼ and j ε I, {equation*} {*} PR_0(Y_t = j, Δ_t = k \ Y_0 = i) = P_R(Y_t = j, Δ_t = k Y_0 = i).{equation*} The relation () holds for $t = 0$, since PR(Y₀ = j, Δ₀ = k Y₀ = i) = 0 = PR₀(Y₀ = j, Δ₀ Y₀ = i) if j ≠ i and {align*}P_R(Y_0 = i, Δ_0 = k Y_0 = i) &= P_R(Δ_0 = k Y_0 = i) \\ &= PR_0 (Δ_0 = k Y_0 = i){align*} by definition. Now assume () holds for t = 0, ⋯, T - 1. Then PR(YT = j,ΔT = k Y₀ = i) = PR(YT = j Y₀ = i)PR(ΔT = k YT = j, Y₀ = i) but PR(ΔT = k YT = j, Y₀ = i) = Dⱼₖ(t) by definition, and {align*}P_R(Y_T = j Y_0 = i &= ∑lε I ∑kε K_l P_R(YT-1 = l, ΔT-1 = k Y_0 = i) qₗⱼ(k) \\ &= ∑lε I ∑kε K_l PR_0(YT-1 = l, ΔT-1 = k Y_0 = i) qₗⱼ(k) \\ &= PR_0(Y_T = j Y_0 = i){align*} by the introduction hypothesis. Thus {align*}P_R(Y_T = j, Δ_T = k Y_0 = i) &= PR_0(Y_T = j Y_0 = i)Dⱼₖ(t) \\ &= PR_0(Y_T = j, Δ_T = k Y_0 = i).{align*} This completes the proof.