You are here

Glossary of Terms

This page contains a glossary of terms used in the articles published on this site. This is a living lexicon that will be updated with new terms periodically. If you notice omissions in the articles, or inaccuracies in the lexicon, contact me to request additions or modifications.

Cayley Graph

A vertex-transitive graph which encodes the abstract structure of an algebraic group.

Combinatorial Group

An algebraic group which is defined by all the possible expressions (e.g. words or terms) that can be built from a generator set. All terms will be considered distinct unless their equality follows from the group axioms (closure, associativity, identity, invertibility). See Combinatorial Group Theory.

Dynamic Programming

Dynamic Programming (DP) refers to a collection of algorithms which, given a perfect model of an environment, can compute optimal policies for a Markov Decision Process. The classical DP algorithms are of limited use due to their assumption of a perfect model.

Markov Property

The Markov Property is a property which describes a state, s, that models enough information to be able to determine the next state, s′, given only an action. In other words, a system will satisfy the Markov Property if it can determine precisely it's current state without knowing what states were visited, or what actions were taken prior to reaching that state.

Policy Iteration

Policy iteration is the process of iteratively improving a policy, $\pi_t$, using approximations of a state-value function $V^{\pi_t}$. At each iteration $t$, the approximation from the previous step is used to improve ($\overset{I}{\rightarrow}$) the policy, which in turn is used to update ($\overset{E}{\rightarrow}$) the state-value approximation for the next iteration, $V^{\pi_{t+1}}$. Policy iteration ends when the policy becomes stable ($\pi^*$). This is illustrated as follows:
$$
V^{\pi_0} \overset{I}{\rightarrow} \pi_1 \overset{E}{\rightarrow} V^{\pi_1} \overset{I}{\rightarrow} \pi_2 \overset{E}{\rightarrow}... \overset{I}{\rightarrow} \pi^*
$$