Korean, Edit

Reinforcement Learning Example [01-10]

Recommended article: 【Control Theory】 Stochastic Control Theory

Q4.

Consider a finite-state ergodic discrete time Markov chain {X_t}_t∈Z+ on state-space 𝒮 = {1, 2, …, I} with transition matrix P and initial distribution μ (for X₀). For (bounded) cost vector C let (L, J) be a (bounded) solution to the Poisson equation for (C, P), i.e., (L, J) satisfy (vector) equation

Then show the following:

(a) The above equation can be written as

where L(X_t) = L(i) (the i^th component of column vector L) if X_t = i.

(b) Then, using the Markov property show that the random process {M_t}_t∈Z+ given by

is a martingale with respect to filtration {ℱ_t}_t∈Z+ where ℱ_t = σ(X₀, X₁, …, X_t). As 𝔼[ㅣM_tㅣ] < +∞ follows from the boundedness of C, L and J, you only need to show properties (2)―adaptedness, i.e., M_t is ℱ_t measurable―, and (3)―𝔼[M_t+1ㅣℱ_t] = M_t w.p. 1. For property (3) you will need to use part (a) of this question.

A4.

(a)

Let’s check the dimensionality of the given Poisson equation

Here, P(i,j) (i-th row, j-th column) means the transition probability ℙ(jㅣi). Thus, the i-th component of the equation is

Equivalently, given X_t = i, it can be represented as

I replaced L(j) with L(X_t+1) in light of the meaning of the transition.

(b)

M₀ = L(X₀sub>) (measurable by X₀)

M₁ = L(X₁) + C(X₀) - J (measurable by X_0:1)

M₂ = L(X₂) + C(X₀) + C(X₁) - 2J (measurable by X_0:2)

Generally speaking, X: Ω → ℝ is measurable when X^-1(A) = {w ∈ Ω : X(w) ∈ A} ∈ ℱ ∀ A ∈ 𝒢 given a pair (Ω, ℱ) and (ℝ, 𝒢). Of note, the measurability can be defined without a measure ℙ, and 𝒢 is generally set to 𝒢 = ℬ(ℝ), where ℬ is Borel σ-algebra. According to the above observations, we can think of the inverse function of X_0:t for M_t especially given a finite-stage and a finite state set and the existence of the range of the inverse function with the same reasons. Thus, M_t is ℱ_t-measurable.

Obviously, ℱ₀ ⊆ ℱ₁ ⊆ ℱ₂ ⊆ ⋯ (∵ σ(X_0:t-1) ⊆ σ(X_0:t)), so we can find the adaptedness property of filtration. So the question is whether 𝔼[M_t+1ㅣℱ_t] = M_t is true or not. This means the best prediction of M_t+1 can be projected on ℱ_t-measurable space, which is beneficial for future prediction given the current condition. Using (a), we obtain

Here, Doob’s theorem states that σ(X₁, …, X_n) is identical to any functions with g(X₁, …, X_n) form. With a filtration nature of {ℱ_t}_t∈ℤ+ and already proved properties (1), (2) and (3), {M_t}_t∈ℤ+ is a martingale.

Q5.

Let (X_t)_t≥0 be a stochastic process with state space S. Let P be a transition operator on functions f : S → ℝ, and let I denote the identity operator. For every bounded function f : S → ℝ, define

M_t^f = f(X_t) - f(X₀) - ∑_{τ = 0 to (t-1)} (P - I)f(X_τ),

and let ℱ_t = σ(X₀, …, X_t) be the natural filtration generated by X. Show that the following two statements are equivalent:

1. (X_t)_t≥0 is a Markov chain with transition operator P.

2. For every bounded function f, the process (M_t^f)_t≥0 is a martingale with respect to the filtration (ℱ_t)_t≥0.

A5.

Proof on 1 → 2

M_t+1^f - M_t^f = f(X_t+1) - f(X_t) - (P-I)f(X_t) = f(X_t+1) - Pf(X_t)

If (X_t) is a Markov chain with transition probability matrix P, 𝔼[f(X_t+1) ㅣ ℱ_t] = Pf(X_t)

∴ 𝔼[M_t+1^f - M_t^f ㅣ ℱ_t] = 𝔼[f(X_t+1) - Pf(X_t) ㅣ ℱ_t] = 0

∴ 𝔼[M_t+1^f ㅣ ℱ_t] = M_t^f, so M_t^f is a Martingale.

Proof on 2 → 1

M_t+1^f - M_t^f = f(X_t+1) - f(X_t) - (P-I)f(X_t) = f(X_t+1) - Pf(X_t)

Since M_t^f is a Martingale, 𝔼[M_t+1^f - M_t^f ㅣ ℱ_t] = 𝔼[f(X_t+1) - Pf(X_t) ㅣ ℱ_t] = 0

That is, 𝔼[f(X_t+1) ㅣ ℱ_t] = Pf(X_t) is established for all bounded f.

It indicates that if the total past history ℱ_t is given, the next distribution is determined by only X_t. → 1-step Markov property.

If it is applied repetitively, 𝔼[g(X_t+k) ㅣ ℱ_t] = P^kg(X_t) is established, implying the total Markov property.

Q8.

An individual is offered 3 to 1 odds in a coin tossing game where she wins whenever a tail occurs. However, she suspects that the coin is biased and has an a priori probability distribution with CDF F(p) and pdf f(p), for the probability p that a head occurs at each toss. A maximum of T coin tosses is allowed. The individual’s objective is to determine a policy of deciding whether to continue or stop participating in the game, given the outcomes of the game so far, so as to maximize her earnings.

(i) Identify an information state for the problem and write down the equation determining its evolution.

(ii) Write down the dynamic program for this problem.

A8.

Information state can be defined as the posterior probability ℙ(outcome ㅣ prior).

Case 1. For general information state,

Case 1. For specific information state,

Q9.

Show that W_∞(i), i=1,…,I is the solution of the linear program: Maximize ∑_{i=1 to I} z(i) subject to z(i) ≤ c(i,u) + β∑_{j=1 to I} P_ij(u) z(j), ∀u,i

A9.

Let β ∈ (0, 1), a probabilistic transition matrix P(u), and the one-step cost c be given. Define the Bellman operator T by

W_∞ is the unique fixed point of this equation: W_∞ = TW_∞. For all i and u, we have

so W_∞(i) also satisfies the given inequality constraint. Since the constraint holds for all u, we have

Here we can see the monotonicity of the operator T:

Therefore, z ≤ Tz ≤ T²z ≤ ··· ≤ lim_n→∞ Tⁿz = W_∞. The uniqueness of W∞ and the fact that any z converges to W_∞ are already guaranteed by the Banach fixed-point theorem and the Bellman contraction mapping. Moreover, any feasible z is bounded as follows:

Hence Σ_i z(i) ≤ Σ_i W_∞(i). In summary, W_∞ is a feasible solution that satisfies the constraints of the given linear program, and since z ≤ W_∞ for all feasible z, the solution that maximizes Σ_i z(i) is z = W_∞, and this W_∞ is unique.

Q10.

Show that the minimum cost is the solution of the linear program: maximize J* subject to J* + w(i) ≤ c(i,u) + ∑_{j=1 to I} P_ij(u)w(j), 1 ≤ i ≤ I, u ∈ U.

A10.

We can define J_opt* as follows: J_opt* + h(i) = min_u∈U {c(i,u) + ∑_j P_ij(u)h(j)}, ∀i. If we set w(i) = h(i), we know J_opt*, which is LP feasible solution, achieves the minimum cost, implying

For any arbitrary i, u, and LP feasible solution L, we have

Let g be an optimal stationary policy whose long-run average cost is J_opt*. Then

Here, I used the sample-path optimality (a stronger statement), which can be derived from the Martingale difference sequence (MDS). Let J* := sup{J ㅣ ∃w s.t. (J, w) is LP feasible} be the optimal value of the LP. Since J_opt* ≥ J for every LP feasible J, we have J_opt* ≥ J*. Therefore, the minimal cost J_opt* from the Bellman optimality equation is identical to J* from: max J* s.t. J* + w(i) ≤ c(i, u) + ∑_j P_ij(u) w(j).

Input: 2025.11.21 01:30