RL 003

Markov Property

• The future is independent of the past given the present state.
• The current state is sufficient to determine the future, without history.

Markov State

$P[S_{t+1} | S_t] = P[S_{t+1} = s' | S_t = s]$

• $t$: Time step
• $S_{t+1}$: Next state
• $S_t$: Current state
• $S_1, \ldots, S_t$: History (All previous states)

State Transition Probability

$P_{ss'} = P[S_{t+1} = s' | S_t = s]$

• Likelihood or probability of moving from one state $s$ to another state $s'$ in the next time step $t+1$.
• $s$: Markov State
• $s'$: Successor State
• $t$: Time step
• State transition matrix $P$ defines the transitions probabilities between all states $s$ to all successor states $s'$.

State Transition Matrix

$$\mathcal{P} = \begin{array}{rl} & \begin{matrix} \textcolor{red}{\boldsymbol{s_1}} & \textcolor{red}{\boldsymbol{\dots}} & \textcolor{red}{\boldsymbol{s_n}} \end{matrix} \quad \leftarrow \text{(to state)} \\ \begin{matrix} \textcolor{red}{\boldsymbol{s_1}} \\ \textcolor{red}{\boldsymbol{\vdots}} \\ \textcolor{red}{\boldsymbol{s_n}} \end{matrix} & \hspace{-10pt} \begin{bmatrix} \mathcal{P}_{11} & \dots & \mathcal{P}_{1n} \\ \vdots & \ddots & \vdots \\ \mathcal{P}_{n1} & \dots & \mathcal{P}_{nn} \end{bmatrix} \\ \begin{matrix} \uparrow \\[-2pt] \mathclap{\text{(from state)}} \end{matrix} & \end{array}$$

• State transition matrix $P$ defines the transition probabilities between all states $s$ to all successor states $s'$.
• Probability of moving from state $s_n$ to $s_1$ is $\mathcal{P}_{n1}$.

Math cal

Reinforcement Learning and Math Major Symbols

• $\mathcal{P}$: Transition Probability Matrix
• $\mathcal{S}$: State Space
• $\mathcal{A}$: Action Space
• $\mathcal{R}$: Reward Function
• $\mathcal{L}$: Loss Function
• $\mathcal{N}(\mu, \sigma^2)$: Normal Distribution
• $\mathcal{D}$: Dataset
• $\mathcal{H}$: Entropy / Hypothesis Space

Markov Process

Markov Chain

• What is going to be happened next?
• it goes through a sequence of states overtime.
• Stochastic Process: The next state $S_{t+1}$ is determined by the current state $S_t$ and the transition probability matrix $P$ that exhibits the Markov Property.
• Current state is independent of the past states.
• Memoryless: History of states leading up to the current state is not necessary to predict the next/future state.
• MP: $\langle\mathcal{S},\mathcal{P}\rangle$, What states comes next?, Observer's Perspective.
• MRP: $\langle\mathcal{S},\mathcal{P},\mathcal{R},\gamma\rangle$, How good/How much reward is this state in the long run?, Evaluator's Perspective.
• MDP: $\langle\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma\rangle$, What action should I take right now to maximize the long-term reward?, Decision Maker's Perspective.

$\mathcal{P}_{ss'} = P[S_{t+1} = s' | S_t = s]$

• $S$: a finite set of states.
• $\mathcal{P}$: a state transition matrix, defines the transitions probabilities from all states $s$ to all successor states $s'$.
• NO REWARD, NO ACTIONS.

Transition Diagram

• Box: where it ends
• Arrow: transitions
• Circle: states
• Number: probability of transitioning to the state

$$\mathcal{P} = \begin{bmatrix} 0 & 0.1 & 0.5 & 0.1 & 0 & 0.3 \\ 0.4 & 0.1 & 0.5 & 0 & 0 & 0 \\ 0 & 0.5 & 0.5 & 0 & 0 & 0 \\ 0.5 & 0 & 0 & 0.2 & 0.3 & 0 \\ 0.7 & 0 & 0 & 0 & 0.3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

• S1: Calibration Site
• S2: Mineral Site
• S3: Water Site
• S4: Drill Site
• S5: Alien Remain Site
• S6: Lander Site

Markov Chain Episode

• A sequence of states from a starting state to a terminal state.
• $S_1, S_3, S_2, S_1, S_6$
• $S_1, S_3, S_3, S_2, S_1, S_4, S_4, S_1, S_6$

Episodic Task vs Continuous Task

Feature	Episodic Tasks	Continuing Tasks
Termination	Has a well-defined terminal state ($T$)	Runs indefinitely without termination ($T = \infty$)
Real-World Examples	• Video games (e.g., Super Mario: level clear or death) • Navigation (reaching destination) • Board games (e.g., Chess: checkmate/draw)	• Smart thermostat (HVAC temperature control) • 24/7 industrial robotic process control • Automated trading & server load management
Execution Flow	Environment resets to a start state once finished	Operates continuously without automatic resets

• Episodic Tasks: Tasks with a defined end/terminal state.
• Continuing Tasks: Tasks without a defined end/terminal state.
• It may require different MDP formulation and solution methods for each type of task.

Markov Reward Process

Markov Chain + Reward

$\langle\mathcal{S},\mathcal{P},\mathcal{R},\gamma\rangle$

• $S$: a finite set of states.
• $\mathcal{P}$: a state transition matrix (Transition Dynamics)
• $\mathcal{R}$: a reward function to compute expected reward from a state.
  • $\mathcal{R}_s = \mathbb{E}[R_{t+1} | S_t = s]$
  • In the state $s$, how much reward can you expect to get in the next time step?
• $\gamma$: a discount factor, to balance the immediate and future rewards.
  • $\gamma \in [0, 1]$

Return

$G_t = R_{t+1} + R_{t+2} + \cdots + R_T$

• $G_t$: Goal Reward
  • The sum of the rewards received from time step $t$.
• $R_{t+1}, R_{t+2}, \ldots, R_T$: the sequence of rewards received after time step $t$
• $T$: terminal state
• $t$: time step

Discount

• The present value of future rewards.
• $\gamma = 0$: Myopic evaluation for maximizing immediate reward.
• $\gamma = 1$: Far-sighted/Long-term evaluation for maximizing future reward.

Discounted Return

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-t-1} R_T = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$

• $G_t$: Discounted Return
• $\gamma = 1$: Undiscounted Markov Reward Process, if all sequences terminate (like games)