① 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 xt 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, 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, 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

① Under DDS, open-loop and feedback systems are equivalent: because uniqueness of u_t in DDS naturally holds,

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

○ Counterexample 1.

⑶ 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.

③ Sometimes written as W_t ⫫ x₀, U_0:t-1, W_0:t-2 instead of W_t ⫫ x₀, U_0:t-1, but the former is a stronger claim.

⑷ Lemma 4. Gaussian process (GP)

① Definition: the state process {X_t} is such that any finite subset 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

⑤ (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)

② 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 observation, 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 wt, 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 ∑_∞

○ stability of A is a sufficient, but not necessary condition: ∑_∞ may still exist uniquely even if A is not stable

④ reachability

○ Definition

○ Theorem 1. The following are all equivalent: assume 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

Figure 3. Example of a 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 Mk 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 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

○ 2-1. The (i, j) entry P_ij(k) of P^k converges to q_i as k → ∞: note 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

① recursive and backward iteration: for example, with present value (discounting future value to present),

○ 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

② Bellman equation: related to the discounted cost problem

○ (Note) time-homogeneous: {x_t^g}_t≥0 and {x_t^g}_{t≥τ,∀τ∈ℤ⁺} follow the same distribution

○ 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

○ 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 Pg 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.

○ The stationary distribution π^g assigns probability 0 to all transient states.

③ 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.

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

④ Example 1. 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 Ś. 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 2. Countably infinite state space

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

○ 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 (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).

○ 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_t ㅣ ℱ_s] = X_t also holds, because X_s is ℱ_s-measurable and ℱ_s ⊆ ℱ_t implies X_s is ℱ_t-measurable.

○ 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)

Input: 2025.08.26 23:34

895

Stochastic Control Theory

1. Sigma-algebra

2. Terminology of Stochastic Control Theory

3. Laws of Stochastic Control Theory

results matching ""

No results matching ""