Reinforcement Learning - Markov Decision Processes and Dynamic Programming

Vocabulary practice flashcards covering Markov Chains, Markov Reward Processes, Markov Decision Processes, Bellman Equations, Dynamic Programming (Value Iteration and Policy Iteration), and Model-Free RL foundations.

Markov Property

The mathematical condition where the future is independent of the past given the present, formalized as: $\mathbb{P}(S_{t+1} = s' \mid S_t = s) = \mathbb{P}(S_{t+1} = s' \mid S_t = s, S_{t-1} = s_{t-1}, \dots, S_0 = s_0)$.

Partially Observable Markov Decision Process (POMDP)

An environment model in which the current state is only partially observable or the state definition lacks sufficient information to fully determine future transition probabilities without knowledge of history.

Frame Stacking

An engineering technique used in Deep Reinforcement Learning (such as in Atari games) where multiple consecutive frames (e.g., the last 4 frames) are grouped into a single state $(O_{t-3}, O_{t-2}, O_{t-1}, O_t)$ to enable the agent to infer velocity and restore the Markov Property.

Curse of Dimensionality

The computational problem where redefining state space to include the entire history of observations and actions causes the number of possible states to explode, preventing the agent from experiencing identical states twice or generalizing learning.

Belief State

A probability distribution maintained by an agent over what it believes the true underlying state of the world to be given past clues, serving as a compressed, fully Markovian state representation in POMDPs.

Stochastic Process

A mathematical system that evolves over time according to probabilistic rules rather than strict deterministic equations, in which states, actions, and rewards are treated as random variables indexed by time.

Markov Chain

A memoryless sequence of random states defined by the tuple $(\mathcal{S}, \mathcal{P})$, where $\mathcal{S}$ is a finite set of possible states and $\mathcal{P}$ is the state transition probability matrix, with no actions or rewards.

Markov Reward Process (MRP)

A Markov Chain equipped with rewards and a discount factor, defined by the tuple $(\mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma)$, in which a passive observer accumulates rewards as the system changes states without taking actions.

Markov Decision Process (MDP)

A formal framework for sequential decision making defined by the tuple $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma)$, where an agent selects actions, and transition probabilities and reward distributions depend directly on the chosen action.

Discount Factor ($\gamma$)

A parameter $\gamma \in [0, 1]$ that weights the present value of future rewards, scaling a reward received $k$ steps in the future by $\gamma^k$ to prevent infinite reward loops and prioritize immediate payoffs.

Return ($G_t$)

The total cumulative discounted reward received from time step $t$ onward, defined as $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$.

State-Value Function ($v(s)$)

The expected return an agent will receive starting from state $s$, defined as $v(s) = \mathbb{E}[G_t \mid S_t = s]$.

Principle of Optimality

Bellman's foundational principle asserting that an optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

Bellman Equation for MRPs

The recursive linear equation splitting state value into the immediate reward plus the discounted expected value of the next state: $v(s) = \mathcal{R}_s + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'} v(s')$, or in matrix form $v = (I - \gamma P)^{-1} R$.

Policy ($\pi$)

A mapping or probability distribution defining the probability of taking action $a$ given state $s$, denoted $\pi(a \mid s) = \mathbb{P}(A_t = a \mid S_t = s)$.

Bellman Expectation Equation

A linear system of equations used to evaluate a specific, fixed policy $\pi$ by calculating the state-value function: $v_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) [r + \gamma v_\pi(s')]$.

Action-Value Function ($q(s, a)$)

The expected return of executing action $a$ in state $s$ and thereafter following policy $\pi$, given by $q_\pi(s, a) = \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a v_\pi(s')$.

Bellman Optimality Equation

A non-linear recursive equation calculating the optimal state-value function by maximizing over all actions: $v_*(s) = \max_{a \in \mathcal{A}} \sum_{s', r} p(s', r \mid s, a) [r + \gamma v_*(s')]$.

Dynamic Programming (DP)

A collection of model-based algorithms that compute optimal policies by solving recursive Bellman equations, under the requirement that transition probabilities $p(s', r \mid s, a)$ are completely known.

Value Iteration

A dynamic programming algorithm that applies the Bellman optimality backup iteratively across all states using a 1-step lookahead and a max operation ($V_{k+1}(s) = \max_a [R_s^a + \gamma \sum_{s'} P_{ss'}^a V_k(s')]$) until convergence to $V^*$, extracting the optimal policy at the end.

Policy Iteration

A dynamic programming algorithm that alternates between two distinct phases: Policy Evaluation (fully solving for $v_\pi$ under a fixed policy) and Policy Improvement (greedily updating $\pi'(s) = \arg\max_a q_\pi(s, a)$) until the policy converges to $\pi^*$.

Generalized Policy Iteration (GPI)

The overarching conceptual framework in RL consisting of the interaction between policy evaluation (making the value function consistent with the current policy) and policy improvement (making the policy greedy with respect to the current value function) until reaching optimality.

Model-Free Reinforcement Learning

Reinforcement learning methods used when environmental transition dynamics and probabilities are unknown, requiring the agent to learn action values ($Q(s, a)$) directly through trial-and-error interactions.

Monte Carlo (MC) Methods

A model-free RL approach where the agent plays an episode all the way to completion, tallies the empirical final return, and updates value estimates backward based on actual complete episode outcomes.

Temporal Difference (TD) Learning

A model-free RL approach where the agent updates a state's value after a single step by combining the immediate reward with its current discounted estimate of the successor state's value.

Bootstrapping

The algorithmic mechanism in reinforcement learning of updating an existing value estimate based in part on another previously learned value estimate, rather than waiting for a complete final return.

CartPole Problem

A classic reinforcement learning benchmark introduced by Barto, Sutton, and Anderson where an inverted pendulum on a cart must be kept upright using discrete horizontal push forces (left or right) within designated angular and positional limits.