Lexicon
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^*
$$