① DDS (deterministic system): x_t+1 := f_t(x_t, u_t, w_t) = f_t(x_t, u_t). y_t := h_t(x_t, v_t) = h_t(x_t). Case where at any time t, both the state variable x_t and the output variable y_t are known.

② SDS (stochastic dynamical model): x_t+1 := f_t(x_t, u_t, w_t), y_t+1 := h_t(x_t, v_t), w_t, v_t ≢ 0.

⑶ Classification by control input

① Open loop control: u_t := g_t(y_0:t, u_0:t-1) = g_t(u_0:t-1).

② Feedback control: Cases where past outputs y_0:t influence the control action u.

③ Centralized stochastic control: (1) Stochastic dynamical system + (2) One controller + (3) Controller with perfect recall

④ Multi-controller problem: team problem, competitive game, etc.

⑷ Classification by policy

① Decision process: a general framework that deals with decision-making problems where state, action, and reward follow through a process.

② Markov process: (regardless of whether it is a decision process) the future depends only on the current state

○ Markov chain: among Markov processes, it refers to those with a finite or countably infinite state space.

○ Controlled Markov chain: Markov chain + Decision process

③ MDP (Markov decision process): among decision processes, it refers to cases where the future depends only on the current state.

○ Dynamic programming: recurrence relation (break the time dependence). If MDP refers to the system framework, dynamic programming refers to the methodology.

○ POMDP (partially observed Markov decision process): an MDP system where only partial information rather than full state information can be used.

○ Constrained MDP, Constrained POMDP also exist.

○ Related algorithms

④ Gaussian process: the state process {X_t} is such that any finite subset follows a joint Gaussian distribution.

⑤ Gaussian-Markov process

○ Condition 1. {X_t} is a Gaussian process.

○ Condition 2. Markov property: P(X_n+1 ∈ A ㅣ X₀, ···, X_n) = P(X_n+1 ∈ A ㅣ X_n)

3. Laws of Stochastic Control Theory

⑴ Lemma 1. In open-loop control, x_t is a function of x₀, u_0:t-1, w_0:t-1, and y_t is a function of x₀, u_0:t-1, w_0:t-1, v_t.

⑵ Lemma 2. Open-loop system vs. Feedback system

① Open loop control: u_t := g_t(y_0:t, u_0:t-1) = g_t(u_0:t-1).

② Feedback control: Cases where past outputs y_0:t influence the control action u.

③ Under DDS, open-loop and feedback systems are equivalent.

○ Proof for open-loop → feedback: Given an open-loop control input sequence u, define a feedback control that ignores the state (i.e., a map returning the predetermined u_t at each time t). Then, from the initial state x₀, it produces the same trajectory and cost. Thus, regardless of DDS/SDS, for any open-loop there exists a feedback policy that is equivalent at that initial state. That is, open-loop ⊂ feedback holds always.

○ Proof for feedback → open-loop: In a DDS, all control inputs are uniquely determined (determinism). Therefore, if you pre-specify the same input sequence u as an open-loop policy, the resulting state evolution is identical and so is the cost.

④ Under SDS, open-loop and feedback systems are not equivalent.

○ Counterexample 1.

○ In the above counterexample, the feedback system outperforms the open-loop system (i.e., it generates the lower cost).

⑶ Lemma 3. Policy independence: If W_t is independent of X_0:t-1, U_0:t-1, then ℙ(x_t+1^g ∈ A ㅣ x_0:t, u_0:t) = ℙ(x_t+1^g ∈ A ㅣ x_t, u_t) = ℙ(f_t(x_t, u_t, w_t) ∈ A ㅣ x_t, u_t) (Markov property), so dependence on policy g disappears.

① In DDS, if you know the current state, you can know the next state immediately, but in SDS, past states matter, so conditional probabilities on the history are important.

② That is, when w_t is independent, system evolution follows natural laws + pure noise, so the policy is irrelevant; but if w_t depends on the policy, the policy changes the noise distribution, so the future state distribution depends on the policy.

③ Philosophy: Philosophically, “policy independence” implies that diversified judgments based on individual value assessments are impossible, and that choices become constrained by factual determinations.

⑷ Lemma 4. Gaussian process (GP)

① Definition: the state process {X_t} is such that any finite subset of it follows a joint Gaussian distribution.

② 4-1. Even if each X_i is Gaussian, it does not imply {X_i}_i∈ℕ is a GP.

○ Example: X₂ = X₁ I{ㅣX₁ㅣ ≤ k} + (-X₁) I{ㅣX₁ㅣ > k}, Y = (X₁ + X₂) / 2 is not a GP.

③ 4-2. For X_t+1 = AX_t + BU_t + GW_t, X₀ ~ 𝒩(0, ∑₀), W_t ~ 𝒩(0, Q), {X_t} is a GP.

④ 4-3. Under a feedback policy, {X_t} is generally not a GP.

○ Example: If U_t := g_t(Y_t) = g_t(X_t) = X_t², then X₁ = AX₀ + BX₀² + GW₀, which is not Gaussian.

○ On the other hand, in a linear Gaussian SDS, for a general open-loop policy, the state process {X_t} is always Gaussian.

⑤ (Note) MMSE (minimum mean-square estimator)

⑥ (Note) Orthogonality principle

⑦ (Note) LMMSE (linear minimum mean-square estimator)

⑧ If X and Y are jointly Gaussian, then LMMSE = MMSE holds.

⑸ Lemma 5. Multi-step prediction

① In general, ℙ(x_t+2^g ∈ A ㅣ x_t, u_t, u_t+1) ≠ ℙ(x_t+2^g ∈ A ㅣ x_0:t, u_0:t+1)

○ Proof: Let’s think of x_t → y_t → u_t → x_t+1 → y_t+1 → u_t+1 → x_t+2. Since u_t+1 = g_t(y_0:t+1, u_0:t) that is not independent of u_0:t-1 implies information about w_t via xt+1 = f(xt, ut, wt), conditioning on u_t+1 breaks the past-independence of w_t: here “past” means x_0:t-1, u_0:t-1.

○ Counterexample 1. In open-loop control, u_t+1 = g_t(u_0:t) holds, so it cannot imply information about w_t, hence equality holds.

○ Counterexample 2. When w_t is a constant

○ Counterexample 3. When u_t is defined to have the Markov property and memoryless feedback, e.g., u_t = μ_t(x_t): the following is the case y_t = x_t = u_t

② Multi-step prediction with open-loop control

③ Chapman-Kolmogorov decomposition

⑹ Lemma 6. Linear Gaussian state-space model

① (Note) Gaussian-Markov process

○ Condition 1. {X_t} is a Gaussian process.

○ Condition 2. Markov property: P(X_n+1 ∈ A ㅣ X₀, ···, X_n) = P(X_n+1 ∈ A ㅣ X_n)

② System definition

○ Markov property: applies even with feedback policy.

○ Multi-step Markov property

○ Mean propagation

○ Cross-covariance Cov(X_t+m, X_t)

○ Covariance propagation

③ DALE (discrete-time algebraic Lyapunov equation)

○ If the absolute values of all eigenvalues (including complex ones) of a square matrix A are less than 1, the matrix is defined as stable: because A^∞ = 0.

○ If A is stable, then ∑_∞ = lim_t→∞ ∑_t = lim_t→∞ 𝔼[(X_t - 𝔼[X_t])(X_t - 𝔼[X_t])ᵀ] exists uniquely.

○ Proof of uniqueness of ∑_∞

○ Remark 1. Stability of A is a sufficient, but not necessary condition.

○ ∑_∞ may still exist uniquely even if A is not stable.

○ A trivial example is given by ∑₀ = 0, Q = 0, in which case ∑_k ≡ 0 independent of A. (No noise in the first place.)

○ Remark 2. ∑_∞ may not be strictly positive definite.

○ A trivial example is A = O, rank(GQG^T) < n. (Noise does not touch all directions in the state.)

○ Remark 3. If the input disturbance w_k affects all the components of the state vector, then the stability of A would be necessary for the convergence of ∑_k, and the limiting covariance ∑_∞ would be positive definite → the concept of recapability is related.

④ Reachability

○ Definition: Related to controllability and observability.

○ Theorem 1. The following are all equivalent: assuming w ∈ ℝ^s

○ In condition 3, the noise sequence w should be interpreted as the control input applied to the system; due to them, the system can be steered from 0 to a given state x over n time steps.

○ Theorem 2. Lyapunov stability test

○ Note that in condition 2, it is PD (positive definite), not PSD (positive semidefinite).

⑺ Lemma 7. Graph Theory

① Strongly connected (= irreducible, communicable): a condition where from any node i in the graph, one can reach any other node j.

Figure 1. Example of “irreducible”

Figure 2. Example of “reducible” (state 3 is a sink)

② Period: the period of a specific node i is the greatest common divisor of the lengths of all paths from i back to i

○ Example: with two nodes A, B connected by two edges A=B, the period of each node is 2.

○ The transition matrix with period m should have the following form when allowing for state rearrangements like Q^TPQ given a proper permutation matrix Q.

Figure 3. Example of a transition matrix with period m

S₁ → S₂ → ··· → S_m → S₁ → ··· has such a cycle.

③ Aperiodic: all nodes have period 1.

○ Aperiodic ⊂ Irreduicible

○ Example: if each node has a walk to itself, it is aperiodic.

④ Stationary state: If Pr(x_n ㅣ x_n-1) is independent of n, the Markov process is stationary (time-invariant).

⑤ Regular

○ Regular ⊂ Irreduicible

○ For some natural number k, every entry of the power M^k of the transition matrix M is positive (i.e., nonzero).

⑥ Transition matrix

⑦ Markov policy: u_t = g_t(x_t)

⑧ One can prove the second law of thermodynamics (law of increasing entropy) using a Markov process.

○ Because one can simulate the law of diffusion: provided a uniform stationary distribution is assumed.

○ Related concept: random walk

⑨ Perron-Frobenius theorem

○ Theorem 1. If a Markov chain with transition matrix P is strongly connected, there exists exactly one stationary distribution q.

○ The stationary distribution satisfies Pq = q.

○ Theorem 2. If a finite Markov chain with transition matrix P is strongly connected and aperiodic, it is called an Ergodic Markov chain and satisfies:

○ P_ij: probability of transition from node j to node i. ∑_i P_ij = 1. Note that P_ij means the probability of transition from node i to node j in other Lemma below.

○ 2-1. The (i,j) entry of P^k, P_ij(k), converges to q_i as k → ∞: note that it converges to the same value for fixed i regardless of j.

○ 2-2. Regardless of the initial state x₀, the k-th state x_k converges to q as k → ∞.

⑻ Lemma 8. Value function following deterministic Markov property

① Expected cost and transition probability

② Recursive and backward iteration: Dynamic programming

○ J_T^g ∈ ℝ^1×1

○ π₀ ∈ ℝ^1×n: initial distribution of the Markov chain

○ V₀^g ∈ ℝ^n×1: vector of state-wise value functions collecting expected cumulative cost at each state under policy g

○ When T = ∞, J^g becomes infinite, being unable to find the optimal policy g; thus, Bellman equation, Cesàro limit concepts are introduced.

③ Bellman equation: The below describes the discounted cost problem primarily.

○ (Note) Time-homogeneous: {x_t^g}_t≥0 and {x_t^g}_{t≥τ,∀τ∈ℤ₊} follow the same distribution. Also means strictly stationary.

○ Condition 1. Time-homogeneous transition: P_t(j ㅣ i, u) = P(j ㅣ i, u) ∀t

○ Condition 2. Time-homogeneous cost: C_t(x, y) = C(x, y) ∀t

○ Condition 3. Stationary policy: g_t = g ∀t

○ If all the above hold, one can obtain the following fixed-point equation.

○ J^g: The present value of the cost; generally used in an economic context.

○ Since P^g is stable, all eigenvalues have absolute value less than 1, so det(I - βP^g) = β det((1/β)I - P^g) ≠ 0

○ V^g ∈ ℝ^n×1: vector of state-wise value functions collecting expected discounted cumulative cost at each state under policy g

○ P^g ∈ ℝ^n×n: transition matrix; the (i,j) entry is the probability of transition from i to j.

④ Cesàro limit: related to the long-term average cost problem.

⑤ Poisson equation: related to average cost.

○ J^g is unique.

○ L^g: relative value function. L^g is not unique (∵ L^g + α1 ∀α ∈ ℝ is also a solution to the Poisson equation)

○ Existence of solutions

⑼ Lemma 9. When not irreducible

① If P^g is not irreducible, the state space S splits into the transient states T and one or more recurrent communicating classes C₁, ···

② Transient state: visited only finitely many times. Eventually the process leaves the transient states and enters a recurrent state.

○ Theorem: The stationary distribution π^g of a finite-state Markov chain assigns probability 0 to all transient states.

○ (i) Proof: Pigeonhole principle. The finiteness is critical (and needs to be used).

○ Suppose that a certain transient state i satisfies Q_i=0. Since a recurrent communicating class is a closed set, no communication occurs with outside nodes once the process enters the recurrent class. Thus, the assumption implies that the transient state i moves to only transient states for all K transitions. Thus, by Pigeonhole Principle, at least one transient state is visited twice among K+1 pigeonholes (counting the start), which yields a directed cycle entirely contained in the transient set. This cycle is closed (no edge leaves it to the recurrent class within these K steps), so it forms a closed communicating class disjoint from the given recurrent class. In a finite Markov chain, every closed communicating class is recurrent; thus, we have produced a second recurrent class, contradicting the assumption of uniqueness. Therefore, the assumption Q_i is false, and hence Q_i>0 for every transient state i.

○ (ii) Proof

③ Recurrent state: since a recurrent communicating class is a closed set, no communication occurs with outside nodes.

○ i → j: means there exists a path with positive probability from i to j.

○ i ↔︎ j: means i → j and j → i; i and j communicate.

○ Positive recurrent: the mean return time to that state is finite.

○ A chain starting in a positive recurrent state has a unique stationary distribution.

○ Null recurrent: the mean return time to that state is infinite. No stationary distribution exists.

○ Example: X_n+1 = X_n + ξ_n, X₀ = 0, ℙ(ξ_n = +1) = ℙ(ξ_n = −1) = 0.5 → The probability of going back to the origin is 1 but the expected time is ∞.

○ Absorbing state: a state that, once entered, you remain in forever

④ Example 1. Stationary state set F

⑤ Example 2. Finite state space

Let S = {0, 1, ···, I}. Since V^g(0) = 0 and C(0, g(0)) = 0, we can focus only on Ś = S \ {0} = {1, ···, I}, the non-absorbing states. Let Ṽ^g be the value vector for states in Ś, and let R^g be the submatrix of P^g for transitions among states inside Ś. (i.e., the matrix that describes how the chain moves only among the non-absorbing states before hitting 0.) Then the system of equations for these states is Ṽ^g = c̃ + R^gṼ^g. To show uniqueness of Ṽ^g, suppose there are two solutions Ṽ₁^g, Ṽ₂^g. Let their difference be U^g = Ṽ₁^g - Ṽ₂^g; subtracting the two equations yields U^g = R^gU^g = ⋯ = (R^g)ⁿU^g = ⋯ = 0 (∵ lim_n→∞ (R^g)ⁿ = 0, method of infinite descent) ⇔ Ṽ₁^g = Ṽ₂^g. Thus, in a finite state space where state 0 is absorbing and all other states can reach 0, the first-passage-time cost equation has a unique nonnegative solution.

⑥ Example 3. Countably infinite state space

Figure 4. Countably infinite state space diagram

Uniqueness is not trivial. Assuming the solution is bounded often allows one to show uniqueness. Consider the equation for the difference of two solutions U^g = R^gU^g. Connecting this to the diagram yields U^g(ℓ+1) - U^g(ℓ) = (λ - 1)(U^g(ℓ) - U^g(ℓ-1)). The consecutive differences Δ(ℓ) = U^g(ℓ+1) - U^g(ℓ) form a geometric sequence with ratio (λ - 1). If |λ - 1| < 1, these differences converge to 0, suggesting a bounded solution. If |λ - 1| ≥ 1, the differences may diverge, implying that uniqueness may fail.

⑽ Lemma 10. Martingale

① Doob’s theorem

○ σ(X₁, X₂, ···, X_n): the smallest σ-algebra that makes X₁, X₂, ···, X_n measurable.

○ Doob’s theorem: σ(X₁, X₂, ···, X_n) is equivalent to the collection of all functions of the form g(X₁, X₂, ···, X_n).

○ The larger the σ-algebra, the more functions are measurable with respect to it; i.e., the more information it contains.

② Filtration

○ A collection of σ-algebras ordered increasingly by inclusion.

○ Ordered by ⊆; if ℱ₁ ⊆ ℱ₂, then ℱ₂ is afterwards relative to ℱ₁.

○ For convenience, let time index t = 0, 1, 2, ⋯; then the filtration is {ℱ_t}_t∈ℤ₊ and satisfies ℱ_s ⊆ ℱ_t for all s ≤ t.

○ Intuition: represents situations where information increases as observations accumulate over time.

③ Martingale

○ Property of conditional expectation

○ For any random variable Y, 𝔼[Y ㅣ X₁, ···, X_n] = 𝔼[Y ㅣ σ(X₁, ···, X_n)] holds.

○ Reason: because σ(X₁, ···, X_n) is equivalent to the set of all functions generated by X₁, ···, X_n.

○ Additionally, when σ(Y) ⊂ σ(Z), 𝔼[𝔼[X ㅣ Z] ㅣ Y] = 𝔼[𝔼[X ㅣ Y] ㅣ Z] = 𝔼[X ㅣ Y] is established.

○ Martingale: a stochastic process {X_t}_t∈ℤ₊ adapted to a filtration {ℱ_t}_t∈ℤ₊ that satisfies all of the following

○ Condition 1. X_t is ℱ_t-measurable for all t ∈ ℤ⁺.

○ If s ≤ t ≤ s′ and ℱ_s ⊆ ℱ_t ⊆ ℱ_s′, then X_t ∈ ℱ_t is not ℱ_s-measurable (due to insufficient information) but is ℱ_s′-measurable.

○ Condition 2. 𝔼[ㅣX_tㅣ] is finite for all t ∈ ℤ₊.

○ Condition 3. 𝔼[X_t ㅣ ℱ_s] = X_s, almost surely for all s ≤ t and all t ∈ ℤ₊

○ Interpretation: Given only the information up to time s (ℱ_s), the optimal prediction of X_t equals X_s (i.e., the prediction is constrained to X_s; 𝔼[X_t ㅣ ℱ_s] is an orthogonal projection of X_t into the ℱ_s-measurable random variable space (‘best prediction’)).

○ Remark: The martingale property is needed only when predicting the future from the past. In particular, for s > t we have 𝔼[X_t ㅣ ℱ_s] = X_t regardless of whether X_t is a martingale (assuming integrability).

○ For s < t, 𝔼[X_s ㅣ ℱ_t] = X_s also holds, because X_s is ℱ_s-measurable, but has insufficient information due to ℱ_s ⊆ ℱ_t.

○ Note: an i.i.d. process is generally not a martingale (except for the constant process).

○ Application: 𝔼[U^g(X_t^g) ㅣ X_t-1^g] = U^g(X_t-1^g)

④ Martingale and stochastic control theory

⑾ Lemma 11. (Fully observed) ― Optimal Policy

① Problem definition: cost-to-go function under perfect observation. Since control input {U_t, …, U₁} is measurable by {X_t, …, X₀}, the following holds:

② When following Markov property, Bellman equation is established. Here, J_t^g, V_t^{g^M}(X_t) is a cost-to-go from t to future.

③ Markovization theorem (Markov policy sufficiency, reduction to Markov policy)

○ Theorem: In a finite-horizon MDP, for any general (possibly history-dependent and randomized) policy g, there exists a behavioral Markov policy g^M such that, under the same initial distribution μ, the joint distributions of (X_t, U_t) for all t = 0, …, T−1 and of X_T are identical. Consequently, the performance (cost) J^g = 𝔼^g[∑_{t=0 to T−1} C_t(X_t, U_t) + C_T(X_T)] equals J^{g^M}. Hence, without loss of optimality, one may restrict attention to randomized Markov policies.

○ Proof

④ Comparison principle

○ Theorem: By working backward from the objective and ensuring the Bellman inequality holds at each step, the initial value V₀ serves as a lower bound for the performance of all possible policies. The set of actions that achieve equality at each stage collectively constitute the optimal policy. Thus, the optimality can be verified or constructed by combining locally optimal (stage-wise) choices.

○ Proof: Using mathematical induction on backward

○ Case 1. t = T: Since J_T^g = 𝔼^g[C_T(X_T^g) ㅣ X_T^g, …, X₁^g, X₀] = C_T(X_T^g) ≥ V_T(X_T^g) (∵ (V1)) holds, the induction assumptions are still established.

○ Case 2. If the induction assumptions are established on ℓ = t+1, …, T, the fact that the assumptions still hold for ℓ = t can be verified as follows:

○ Corollary

⑤ Hamiltonian-Jacobi-Bellman (HJB) equation

○ Theorem: HJB is applicable to fiinite / countably infinite, state / action space. Continuous time version of Bellman equation.

○ Proof of theorem 1 is shown at the comparison principle already, so the following explanations are only relevant to theorem 2.

○ p: A certain Markov policy g^M = {g_t} is optimal.

○ q: Given ∀x, t, g_t(x) ∈ arg inf_u∈𝒰 {c_t(x, u) + 𝔼_{W_t}[V_t+1(f_t(x, u, W_t))]} (i.e., stepwise Bellman minimization is achieved)

○ Proof of sufficiency on theorem 2 (q ⇒ p): When x_t is given for each stage, any policies satisfying the infimum is optimal (∵ corollary). Then, u_t should be a measurable function on the current state x_t, the optimal policy should be Markov policy.

○ Proof of necessity on theorem 2 (p ⇒ q): If a policy is optimal Markov policy, it should achieve infimum for each stage (w.p.1); otherwise, we can construct a better policy g’ with a positive probability set, implying J(g’) < J(g).

○ Corollary

○ Application 1. If an optimal path of 1 → 6 is 1 → 2 → 3 → 6, the optimal path of 2 → 6 should 2 → 3 → 6 by HJB equation.

○ Application 2. Policy evaluation: discussed below.

○ Application 3. V_t(x) obtained from HJB equation is called value function. It effectively decreases the size of search space.

○ Application 4. Q-value (state-action value function) : Q_t(x, u) = C_t(x, u) + 𝔼_{W_t}[V_t+1(f_t(x, u, W_t))], V_t(x) = inf_u∈𝒰 Q_t(x, u)

○ Application 5. For given finite state / action space, inf = min, and the optimal policy is deterministic Markov policy.

○ Application 6. Value function at randomized Markov policy: For u ~ μ_t(u ㅣ i),

⑥ (Note) Blackwell’s Principle of Irrelevant Information

○ If Y is independent of the state and does not appear directly in the reward, then Y is irrelevant for decision-making: a decision rule that ignores y is always at least as good. In other words, having more information is not always better.

○ Example: Suppose a doctor has to decide on a treatment for a patient. Every morning, the doctor can observe the patient’s health status X, and in addition also knows what day of the week it is, Y. The available actions are “treat” and “do not treat.” If the day of the week is unrelated to both the expected reward (survival probability) and the health status, then making decisions based only on X yields the same expected survival probability as using both X and Y.

○ However, depending on technical assumptions such as the action space and measurability, the statement may need to be formulated in terms of ε-optimal policies, and when countability/non-countability and measurability traps are involved (e.g., the projection of a Borel set can be non-Borel), there are counterexamples in which global approximate dominance fails.

○ Conclusion: In dynamic programming problems, one can mathematically prove that memoryless strategies are sufficient to optimize the expected reward.

○ Application: In finite-horizon Markov decision problems, one can easily prove that Markov policies are optimal. (ref)

⑿ Lemma 12. (Partially observed) ― Information state

① {z_t}_{t={0,···,T}} satisfying the following given partial observation context

○ Background: The history H_t := {y₀, …, y_t, u₀, …, u_t-1} increases in time and the domain of it increases exponentially. (Curse of dimensionality)

○ Condition 1. Compression: z_t = ℓ_t(H_t) ∀t

○ Condition 2. Policy / Strategy Independent : z_t+1 = 𝒯_t(z_t, y_t+1, u_t) (■ current state, ■ new information) That is, z_t can be updated recursively using current state and new information without direct reference to the entire past history.

○ Condition 3. Independence relative to g_0:t-1: ∀t = 0, …, T-1

② Condidate 1. z_t = H_t := {y₀, …, y_t, u₀, …, u_t-1}

○ π₀(i) is as follows:

③ Candidate 2. Belief state: z_t = π_t s.t. π_t(i) := ℙ(X_t = i ㅣ H_t) = ℙ(X_t = i ㅣ y_0:t, u_0:t-1) ∀i ∈ S

○ Condition 1 is satisfied: z_t = ℓ_t(H_t) in time (compression)

○ Condition 2 is satisfied: we can obtain 𝒯_t satisfiying π_t+1 = 𝒯_t(π_t, y_t+1, u_t) directly using Bayes’ rule. This is the update equation for the belief state, often called a nonlinear filter.

○ Condition 3 is satisfied: using backward mathematical induction.

○ Case 1. t = T-1: All terms do not depend on g_0:T-1.

○ Case 2. The backward induction can be established as follows:

○ Bellman equation of belief-MDP: The key message of this theorem is that, although the overall policy space 𝒢 of an MDP consists of all mappings from histories to actions and is therefore extremely large, the belief Π_t is sufficient, so we lose no optimality by restricting attention to separated policies of the form “belief → action.”

○ Proof

○ Application 1. (One-way) Separation theorem

○ Application 2. Cost function in belief space

○ Application 3. The following is strategy-dependent unlike belief state because it dependes on g_t-1.

○ Application 4. The following is strategy-dependent unlike belief state: because if not including u_t as a condition π_t+1 = 𝔼_{u_t ~ p(· ㅣ Y_0:t) [𝒯_t(π_t, y_t+1, u_t)] is established so the information state transition is affected by the policy.}

○ Application 5. Generally, P^g(X_t+1 ∈ A ㅣ H_t, u_t) ≠ P^g(X_t+1 ∈ A ㅣ y_t, u_t), H_t = (Y_0:t, U_0:t-1)

○ Proof: Let’s suppose t = 1. Let’s think of x₀ → y₀ → u₀ → x₁ → y₁ → u₁ → x₂ → ⋯. Given H₁ = (y_0:1, u₀), we can determine the distribution of x₀ via y₀ → x₀. Thus, we can more accurately determine the distribution of x₁ via y₁ → x₁ and (x₀, u₀) → x₁. Afterward, we can determine the distribution of x₂ via x₁, u₁, w₁. However, in the right-hand side, we can only use y₁ → x₁ and the limited information for u₁ to determine the distribution of x₁, leading to less accurate distribution of x₂. Thus, both sides differ.

○ Application 6. P^g(X_t+1 ∈ A ㅣ H_t, u_t) = P^g(X_t+1 ∈ A ㅣ y_0:t, u_t)

○ Proof: Let’s think of x₀ → y₀ → u₀ → x₁ → y₁ → u₁ → x₂ → ⋯. Given policy g, in the right-hand side, we can determine the distribution of u₀ and x₀ via y₀ → u₀ and y₀ → x₀, respectively. Thus, we can determine the distribution of x₁ via (x₀, u₀) → x₁. Now by utilizing u_t = g_t(y0:t, u_0:t-1) and x_t+1 = f_t(x_t, u_t, w_t), we can determine the distribution of all the variables, thus leading to the distribution of x_t+1 thoroughly. It is identical that from the left-hand side.

○ Conclusion: The information state Z_t^g := (Y_0:t^g, U_0:t-1^g) is a function of Y_0:t^g.

○ Application 7. P(X_t+1 ∈ A ㅣ H_t, u_t) ≠ P(X_t+1 ∈ A ㅣ y_0:t, u_t)

○ Proof: Let’s think of x₀ → y₀ → u₀ → x₁ → y₁ → u₁ → x₂ → ⋯. In the right-hand side, we can determine the distribution of x₀ via y₀ → x₀ but can only determine the distribution of u₀ via y0 → u0 on the probability over policy set. However, u₀ is exactly given in the left-hand side. Therefore, both sides differ. We can conclude that P^g(X_t+1 ∈ A ㅣ H_t, u_t) is policy-independent, while P^g(X_t+1 ∈ A ㅣ y_0:t, u_t) is policy-dependent.

⒀ Lemma 13. Dynamic Program

① If V_t(i) = max{r(i), a + b∑_j∈S ℙ(j ㅣ i) V_t+1(j)} = max{r(i), a + b𝔼[V_t+1(j) ㅣ i]}, V_t(i) ≥ V_t+1(i) is established.

② If V_t(x) = max{-c + p(x)(1 + V_t+1(x-1)) + (1 - p(x))V_t+1(x), V_t+1(x)}, V_N+1(x) = 0, the following is established:

○ Monotonicity on time: V_t(x) ≥ V_t+1(x) (Proof)

○ Monotonicity on x: V_t(x) ≥ V_t(x-1) (Proof)

○ Supremum of marginal value: 1 ≥ V_t(x) - V_t(x-1) (Proof)

○ Concavity on x is not established: V_t(x) - V_t(x-1) ≤ V_t(x-1) - V_t(x-2) (Counterexamples exist)

○ Relationship between marginal value and time: V_t(x) - V_t(x-1) ≥ V_t+1(x) - V_t+1(x-1) (Proof)

○ Existence of threshold: G_t(x) = p(x)(1 - Δ_t+1(x)) is nondecreasing on x (Proof)

③ Convex

○ Lemma 1. Given two convex functions f₁ and f₂, max{f₁, f₂} is also convex.

Figure 5. Maximum of two convex functions is convex.

○ Lemma 2. Sum of two convex functions is convex.

○ Lemma 3. If V(x) is a non-decreasing convex function, V(max{x, a}), ∀a is also a convex convex: it can be easily understood geometrically.

○ Lemma 4. If L(π) is a convex function, L(π) = sup_i∈I {α_i π + β_i}, α_i, β_i ∈ ℝ is established.

○ The above comes from the inequality f(x) ≥ f(x₀) + f’(x₀)(x - x₀); it is not a claim that the formula holds for arbitrary choices of α_i and β_i.

○ Example: If L(π) = π², then π² = sup_x₀∈ℝ {2x₀π - x₀²}.

○ Practical point: Using transformation that preserve convexity in the linear (affine) representation, one can show that applying the same transformation to the original convex function also preserves convexity. Example is as follows.

⒁ Lemma 14. (Stochastic policy) DCOE(discounted cost optimality equation, infinite-horizon discounted cost Bellman equation)

① Banach fixed point theorem

○ Theorem

○ Let F be a Banach space. Here, Banach space refers to a complete normed space, and a set being “complete” means every Cauchy sequence in the set converges to a certain element in the set. Let T: F → F be a transformation satisfying the following: ㅣㅣTx - Tyㅣㅣ ≤ βㅣㅣx - yㅣㅣ, ∃β ∈ (0,1), ∀x, y ∈ F. Then, the following is established:

○ There is a unique fixed point w ∈ F satisfying Tw = w.

○ For any x ∈ X, lim_n→∞ Tⁿx = w.

○ This essentially implies the following:

○ The transformation satisfying the above is called contraction. Strictly speaking, it requires that sup β(x, y) < 1.

○ T is continuous, and specifically is Lipschitz continuous.

○ Proof

○ Let x ∈ F, α = ㅣㅣx - Txㅣㅣ. Then, we have ㅣㅣTⁿx - Tⁿ⁺¹xㅣㅣ ≤ βⁿα. If we set the Cauchy sequence of {x, Tx, T²x, ···}, we can obtain the following: ∀ϵ > 0, ∃N_ϵ s.t. ∀n, m ≥ N_ϵ, ㅣㅣTⁿx - T^mxㅣㅣ < ϵ. Without loss of generality, we can set n > m. Then, we have

○ Thus, we have N suject to αβ^N / (1 - β) < ϵ. As F is a Banach space, we have w subject to lim_n→∞ Tⁿx = w. Since T(lim_n→∞ Tⁿx) = Tx = lim_n→∞ Tⁿ⁺¹x = w, so w is a fixed point. IF we set w₁, w₂ as T’s fixed points, we have ㅣㅣw₁ - w₂ㅣㅣ = ㅣㅣTw₁ - Tw₂ㅣㅣ = ⋯ = ㅣㅣTⁿw₁ - Tnw₂ㅣㅣ = ⋯ = 0, so w₁ and w₂ are same.

○ Intuition

② Bellman operator and contraction theorem

○ Theorem

○ Let F be a set of functions such tat F = {z: S → ℝ}. Here, S = {1, 2, ···, I} and z := (z(1), ···, z(I))^T. Let’s define the following norm: ㅣㅣzㅣㅣ = max_i ㅣz(i)ㅣ (i.e., ㅣㅣ·ㅣㅣ_∞) Let’s define the operator T: F → F for each component. Then, for all i ∈ S, we have Tz(i) = min_u∈𝒰 [C(i, u) + β∑_j∈S ℙ(j ㅣ i, u) z(j)]. Then, T is a contraction mapping.

○ Proof

○ Let ℝ^I be a Banach space with a norm of ㅣㅣ·ㅣㅣ_∞. If z, y ∈ F, then we can prove the theorem as follows:

○ Even if we replace it with a peculiar definition that maximizes the cost, the contraction theorem still holds with the same proof structure.

③ Corollary

○ ∀i ∈ S, W_∞(i) = min_u∈𝒰 C(i, u) + β∑_j∈S ℙ(j ㅣ i, u) W_∞(i) has a unique solution of w_∞.

○ Relationship between DCOE and geometric distribution

○ W_∞(i) = inf_g∈𝒢 J^g(i) = inf_g∈𝒢 𝔼^g[∑_{t=0 to ∞} β^tc(x_t, u_t) ㅣ X₀ = i], ∀i ∈ S

○ Definition of J^g(i) and bound

○ Definition of W_∞: By the property of contraction mapping, the decreasing sequence {W_n} converges to W_∞.

○ J^g(i) ≥ W_∞ (lower bound)

○ W_∞(i) ≥ inf_g J^g(i) (upper bound): it can be represented as J(X₀, π*) ≤ ∑_{τ=0 to t-1} β^τ C_τ(X_τ, π_τ*) + β^t𝔼[V_t(X_t, π_t)].

○ Conclusion: W_∞(i) = inf_g J^g(i)

○ The optimal stationary Markov policy g*(i) ∈ argmin_u∈𝒢 c(i, u) + β∑_j∈S ℙ(j ㅣ i, u)V_∞(j)

○ ⇔ W_∞ = c^g* + βP^g*w_∞

○ ⇔ W_∞ = (I - βP^g*)^-1 c^g*

○ Optimal operator T is defined as follows:

○ By definition, TZ ≤ T^gZ

○ T^g and T are both contraction mapping on ℓ_∞ norm.

○ T^g and T both satisfy the monotonicity: if z ≤ y, T^gz ≤ T^gy and Tz ≤ Ty

○ Proof 1

○ Proof 2

○ If h, g ∈ 𝒢_SMP, and T_hW_∞^g ≤ W_∞^g, W_∞^h ≤ W_∞^g is established: we can obtain T_hⁿW_∞^g ≤ ⋯ ≤ T_hW_∞^g ≤ W_∞^g; then, we can make n to infinite to obtain the conclusion.

④ Algorithm 1. Value iteration

○ A method that updates the value function by repeatedly applying the Bellman optimality operator T as V_k+1 = TV_k.

○ Because of the contraction mapping property, if β < 1 then V_k → V^* converges to the unique fixed point, and the greedy policy with respect to V^* is optimal.

○ A typical stopping criterion is ㅣㅣV_k+1 - V_kㅣㅣ_∞ < ε , etc.

○ Characteristic: It has the advantage of simple computation, but the disadvantage of requiring many iterations.

⑤ Algorithm 2. Policy iteration

○ Step 1. Choose any stationary Markov policy g_n ∈ 𝒢_SMP.

○ Step 2. Policy evaluation: compute W_∞^g_n = (I - βP^g_n)^-1C^g_n.

○ Step 3. Stopping criterion: if TW_∞^g_n = W_∞^g_n, stop and take g_n as the optimal policy; otherwise go to Step 4.

○ Step 4. Policy improvement: define g_n+1 as follows.

○ Theorem: The sequence ({g₀, g₁, g₂, ···}) reaches an optimal policy after finitely many iterations.

○ Proof: When the stopping condition W_∞^g_n = TW_∞^g_n holds, g_n is already an optimal policy. Otherwise, in Step 4 we have T_{g_n+1} W_∞^g_n ≤ W_∞^g_n, and there is at least one state where the inequality is strict. Since the number of possible policies is finite (ㅣUㅣ^ㅣSㅣ) and at each step the cost is strictly improved (in at least one state), the same policy cannot be revisited. Therefore, the algorithm reaches the stopping condition in finitely many steps and yields an optimal policy.

○ Characteristic: It has the advantage of needing far fewer iterations, but at each iteration it must alternate between two operators (policy evaluation (more expensive due to inverse matrix calculation) and policy improvement).

⑥ Algorithm 3. Linear programming

○ Theorem

○ Proof

○ Implementation: Lagrange multiplier method, dual optimal variables.

⒂ Lemma 15. (Stochastic policy) ACOE (average cost optimality equation, infinite-horizon average cost Bellman equation)

① Overview

○ For a finite state space, finite action space, and bounded cost function, define J^g as follows:

○ In an irreducible Markov chain, consider the Poisson equation J^g1 + W^g = C^g + P^gW^g.

○ If W^g is a solution, then W^g + α1 is also a solution for any constant α, but W^g is uniquely determined up to this additivity constant.

○ Derivation of the ACOE: the relative value function W_N(i) - W_N(j) converges, as N → ∞, corresponding to W(i) - W(j).

○ Significance 1. J* is the optimal cost.

○ Significance 2. The optimal SMP g* must satisfy the ACOE.

○ Suppose the optimal policy g* is given as follows, and assume that the equality does not hold for some state i.

○ Then a contradiction arises because g* loses optimality, and hence the optimal g* must satisfy the ACOE.

○ Significance 3. We can use policy iteration.

② Algorithm 1. Policy iteration algorithm

○ Step 1. Choose an arbitrary policy g₀ ∈ 𝒢_SMP.

○ Step 2. Policy evaluation: Given g_n, solve the following Poisson equation to obtain (J^g_n, W^g_n). Since we have I equations but (I+1) unknowns (J^g_n, W^g_n(1), ···, W^g_n(I)), we fix one component, e.g. set W^g_n(I) = 0), to uniquely determine the solution of J^gn1 + W^g_n = C^g_n + P^g_nW^g_n

○ Step 3. Stopping criterion: If g_n satisfies the ACOE, then g_n is an optimal SMP. Otherwise, go to Step 4. ACOE: J^g_n + W^g_n(i) = min_u∈𝒰 {C(i, u) + ∑_j∈S P(j ㅣ i, u)W^g_n(j)}, ∀i

○ Step 4. Policy improvement: Define a new policy g_n+1 by g_n+1 ∈ arg min_u∈𝒰 {C(i, u) + ∑_j∈S P(j ㅣ i, u)W^g_n(j)} and return to Step 2.

○ If g_n does not satisfy the stopping criterion, then J^g_n+1 < J^g_n holds.

③ Algorithm 2. ACOE and relative value iteration

○ Assumption: For every g ∈ 𝒢_SMP, the transition matrix P^g is irreducible and aperiodic.

○ Step 1. Choose an arbitrary h₀ ∈ ℝ^I.

○ Step 2. For any k ≥ 1,

○ ∀i ∈ S, λ^k(i) = min_{u∈𝒰_{{C(i, u) + ∑_j∈S P(j ㅣ i, u)h^k-1(j)}}}

○ μ^k = λ^k(I) for some fixed reference state I

○ ∀i ∈ S, h^k(i) = λ^k(i) - μ^k

○ Step 3. Check convergence; if it does not converge, return to Step 2.

○ Then μ^k converges to J*, and h^k converges to W (the relative value function).

④ Other algorithms

○ Linear programming: If there is no max condition, J* can go down to −∞ due to the ≤ inequality (which is a stronger condition than taking the minimum).

○ Successive approximation

○ Bertsekas’ algorithm

○ Puterman’s algorithm

⑤ MDS (Martingale difference sequence)

○ Overview: For concrete sample paths (random variables), we want to prove that lim inf_N→∞ Ĵ_N^g(ω) almost surely (a.s.) is as follows for every g, and that lim_N→∞ Ĵ_N^g*(ω) = J* a.s. (assuming g* is optimal)

○ Theorem 1. Let {X_k}_k∈ℕ be adapted to a filtration {ℱ_k}_k∈ℕ and satisfy 𝔼[X_k+1 ㅣ ℱ_k] = 0 almost surely. Then X_k and Y_k = ∑_{j=1 to k} X_j are ℱ_k-measurable.

○ Theorem 2. Martingale stability theorem (LLN)

○ Theorem 3. For any g ∈ 𝒢, lim_N→∞ inf (1/N) ∑_{t=0 to N-1} C(X_t^g, U_t^g) ≥ J* a.s. is established, and if equality holds, then g* satisfies the ACOE.

○ Let (J*, W) be a solution of the ACOE. Define Z_k+1 = C(X_k, U_k) - J* + W(X_k+1) - W(X_k) - h(X_k, U_k) and h(i, u) = C(i, u) + ∑_j∈S P(j ㅣ i, u)W(j) - J* - W(i) ≥ 0. Let ℱ_k = σ(X₀, X₁^g, ···, X_k^g). Then, given U_k^g = g_k(X₀, X₁^g, ···, X_k^g), we obtain 𝔼[Z_k+1 ㅣ ℱ_k] = 0 as follows:

○ Hence {Z_k}_k∈ℕ is an MDS, and each term of Z_k+1 is bounded, so Z_k+1 is bounded with respect to M̃. Therefore,

○ holds, and by the LLN we have lim_N→∞ (1/N)∑_{k=1 to N} Z_k = 0 a.s. But

○ holds and h(·, ·) ≥ 0, so we have lim_N→∞ inf (1/N) ∑_{t=0 to N-1} C(X_t^g, U_t^g) ≥ J* a.s.

⑥ Theorem: The DCOE problem becomes equivalent to the ACOE problem as β → 1.

○ Reason why ㅣW_β(i) - W_β(j)ㅣ < ∞ in the above proof.

○ Theorem

○ Upper bound

○ Lower bound

○ General proof

○ Significance 1. It is not necessarily true that the optimal policy g_β* converges to the optimal ACOE policy g*.

○ Significance 2. Blackwell optimality: If the same policy g_β* is optimal for all β with β̂ < β < 1, then g_β* is also optimal for the ACOE. Then, J_β* = ACOE optimal J* also holds.

○ Proof 1.

○ Proof 2. In the classical Blackwell argument, you compare two stationary policies π and ν by looking at their value difference as a function of the discount factor, f_π,ν(γ) = V_γ^π − V_γ^ν. In a standard finite MDP this difference is a rational function of γ, and a nonzero rational function can have only finitely many zeros. That means there are only finitely many discount factors γ at which the two policies tie; beyond those points, their ranking cannot keep flipping infinitely often as γ → 1. Hence, for all γ sufficiently close to 1, the same policy remains optimal, and this policy is also optimal for the average-reward criterion; this is the Blackwell-optimal policy.

⒃ Lemma 16. Kalman filter

① Overview

○ Case 1. Pure prediction problem (U_t ≡ 0): Kalman filter. Given Y₀, ···, Y_t, the problem is to predict X₀, ···, X_t.

○ Case 2. Pure control problem (Y_t = X_t): LQR (linear quadratic regulator)

○ Case 3. Partial observation with quadratic cost: LQG (linear quadratic Gaussian).

② Review: linear Gaussian process

③ Case 1. u_t ≡ 0 or B_t = 0

○ Step 1. Prediction

○ Step 2. Observation prediction

○ Step 3. Data update

○ Significance: From the form of L_t, we see that the filter is deterministic and nonlinear.

○ Application: Asymptotic behavior of the Kalman filter

○ Definition: In the time-invariant case A_t ≡ A, G_t ≡ G, C_t ≡ C, H_t ≡ H.

○ Background theory: The reason observability appears when discussing the asymptotic behavior of the Kalman filter is that, in order to construct a long-term stable observer, the system must be at least observable or, more generally, satisfy observability. If an unobservable mode exists, the state component in that direction cannot be corrected using measurements. In particular, if such a mode is unstable (i.e., its eigenvalue lies outside the unit circle), then its contribution cannot be inferred from the outputs, and the estimation error in that direction grows without bound over time. Consequently, the error covariance P_k also diverges along that direction, so the Riccati recursion does not converge to a finite limit P_∞, and the observer error cannot be stabilized. Therefore, to guarantee good asymptotic behavior of the Kalman filter—such as convergence of the error covariance, a constant steady-state Kalman gain, and stable estimation—it is essential that all unstable modes be observable, that is, that the pair (A,C) be observability.

○ “Observable”, “detectabile” and “reachable” have the same meaning.

○ ARE(algebraic Riccati equation)

○ If (A,S) is reachable, then the following are equivalent: A is stable. ⇔ The equation ∑ = A∑A* + SS* has a positive definite solution ∑. ⇔ Corollary

④ Case 2. Arbitrary u_t = g_t(H_t) = g_t(y_0:t, u_0:t-1), and arbitrary C_t(x_t, u_t)

○ Result 1. (y_0:t^g, u_0:t-1^g) and y_0:t are the same σ-algebra: each is the function of each other

○ (y_0:t^g, u_0:t-1^g) → y_0:t proof: u₀^g = g₀(y₀^g) = g₀(y₀ + ȳ₀^g) and y₀ = y₀^g - c₀x̄₀^g = y₀^g - C₀𝔼[x₀]. x̄₁^g = A₀x̄₀^g + B₀u₀^g, so ȳ₁^g = C₁x̄₁^g, leading to y₁ = y₁^g - ȳ₁^g. So, we can construct y_0:t in this way.

○ y_0:t → (y_0:t^g, u_0:t-1^g) proof: Let’s think of x₀ → y₀ → u₀ → x₁ → y₁ → u₁ → x₂ → ⋯. ȳ₀^g = c₀x̄₀^g is known. y₀^g = y₀ + ȳ₀^g is known, and u₀^g = g₀(y₀^g) is also known. Then, x̄₁^g = A₀x̄₀^g + B₀u₀^g is known, and also we know ȳ₁^g = c₁x̄₁^g and y₁^g = y₁ + ȳ₁^g. Thereforw, u₁^g = g₁(y_0:1^g, y₀^g) is known. Thus, the proposition can be proved in this way.

○ This is related to the former proposition: P^g(X_t+1 ∈ A ㅣ H_t, u_t) = P^g(X_t+1 ∈ A ㅣ y_0:t, u_t).

○ Result 2. π_t = ℙ(x_t^g ㅣ y_0:t^g, u_0:t-1^g) = ℙ(x_t^g ㅣ y_0:t)

○ Result 3. ℙ(x_t ㅣ y_0:t) (= Kalman filter) is enought to understand the system.

○ Remark 1. Control only affects x̄_t^g (mean), but not for ∑_tㅣt (variance).

○ Remark 2. It does not require learning(active exploration) to decrease the variance, unlike general POMDP.

○ Remark 3. Separation principle: Kalman filter and control can be divided.

⑤ Dynamic programming

⑥ Quadratic cost

○ Assumption: C_t(x_t, u_t) = x_t*P_tx_t + u_t*T_tu_t, C_T(x_T) = x_T*P_Tx_T

○ Let X ~ 𝒩(X̄, ∑) and S be a symmetric matrix, then we have 𝔼[X*SX] = X̄*SX̄ + Tr(S∑).

○ Solution for LQG problem

○ Proof

○ Remark 1. Certainty equivalent control: Noise terms {w_t} and {v_t} don’t apprear in the optimal control policy.

○ Remark 2. Separation principle: Forward estimation through Kalman filter, and backward computation for control action by solving LQR problem.

○ Remark 3. If ∑_tㅣt ≡ 0, s_t ≡ 0.

⑦ Quadratic cost and ACOE

⒄ Lemma 17. MAB(multi-armed bandit)

① Formula

○ N stochastic processes (X_kⁿ)_{k=0,1,···; n=1,2,···}

○ Each stochastic process has a value in S = {1, 2, ···, I} or countably infinite set.

○ For each time k, u_k ∈ {1, 2, ···, N}

○ If u_k = m, X_k+1^m = X_k^m ∀m ∈ {1, 2, ···, N} - {n}

○ ℙ(X_k+1ⁿ = j) = P(j ㅣ X_kⁿ)

○ We observe (X_k¹, X_k², ···, X_kⁿ).

○ We want an optimal policy such that sup_g∈𝒢 𝔼^g[∑_{k=0 to ∞} β^kR(x_k^u_k)].

○ Dynamic programming: W(x¹, x², ···, x^N), xⁱ ∈ S(s^N) = max_{u∈{1, 2, ···, N}} R(x^u) + β∑_{j=1 to I} P(j ㅣ x^u)W(x¹, x², ···, x^u-1, j, x^u+1, ···, x^N)

② Example: Suppose there are N slot machines, denoted by M₁, …, M_N. The success probability of each slot machine M_i is θ_i, and the failure probability is 1 − θ_i. When we play once, we receive a reward of 1 on success and 0 on failure. The success probabilities θ₁, …, θ_N are mutually independent random variables taking values in [0, 1], and their prior distributions are denoted by P₁(dθ₁), …, P_N(dθ_N) (we assume these distributions admit densities). At each time step, we can choose and play only one of the N slot machines. Find an optimal policy that maximizes E^g[∑_{t=0 to ∞} β^t r_t].

③ Example: We consider a small network with J queues (nodes). At each node j ∈ {1, …, J}, there are initially n_j jobs (customers) waiting in line. The time required to serve a single customer at node j is random, and its distribution has cumulative distribution function (CDF) F_j. When a customer completes service at node j, one of two things happens. With probability q_jℓ, the customer moves to another node ℓ and joins the queue there; with the remaining probability 1 − ∑_{ℓ=1 to J} q_jℓ, the customer leaves the system entirely. We assume that whenever a customer completes service at node j, we obtain a reward r_j > 0 (for example, r_j can be interpreted as the revenue the company earns from completing one job at node j). There is only one server (worker) in the system. Thus, at each moment we must decide “which node’s queue should we serve next?” We assume that no new customers arrive from outside, and our goal is to maximize the total discounted reward (total discounted revenue) over time. Viewing this situation as a multi-armed bandit (MAB) problem, each node j corresponds to an arm. At each time step we choose one action from the set {1, 2, …, J} and serve one customer from the corresponding node’s queue. Where the customer goes next is determined by the probabilities q_jℓ for that node, and as a result the overall queueing state (how many customers remain at each node, etc.) evolves to the next state. The joint state of all nodes is the “system state” in the bandit problem. To make the system look more like a standard bandit model, we can add a fictitious (J+1)-th node that represents the destination of customers who leave the system, thereby making the network “closed.” No actual server is assigned to this fictitious node, so it is never chosen as an action; it is just a device to represent the flow of customers leaving the system. In this way, a structure in which a single server chooses among several queues where to spend time, receives a reward whenever a service is completed, and sees the queueing state change accordingly is a canonical example of an MAB. If there are no arrivals at all, each queue shrinks only when we choose to serve it, so the problem is a relatively simple “rested” bandit (cf. the Gittins policy is optimal). However, if customers keep arriving from outside, then the queues change state even when they are not chosen, and the problem becomes an example of a “restless bandit” (cf. the Gittins index policy is no longer optimal, and one must resort to concepts such as the Whittle index).

Input: 2025.08.26 23:34

895

Chapter 9. Stochastic Control Theory

1. Sigma-algebra

2. Terminology of Stochastic Control Theory

3. Laws of Stochastic Control Theory

results matching ""

No results matching ""