Short answers, pulled from the story.
A Markov decision process (MDP) is a mathematical model for sequential decision making when outcomes are uncertain. It originated from operations research in the 1950s and is used in ecology, economics, healthcare, telecommunications, and reinforcement learning.
The MDP is named after the Russian mathematician Andrey Markov, whose work on Markov chains forms the structural backbone of the model. The decision process extends Markov chains by adding a decision maker who can influence state transitions.
A Markov decision process is defined as a 4-tuple consisting of a state space, an action space, a transition probability function, and a reward function. The reward is in general a random variable received after an action moves the system from one state to another.
Value iteration, also called backward induction, avoids storing a policy and repeatedly updates value estimates until convergence, guaranteed by the Banach fixed-point theorem. Policy iteration, invented by Howard to optimize Sears catalogue mailing, interleaves a linear system solve with a policy improvement step and stops as soon as two consecutive steps produce the same policy.
A partially observable Markov decision process, or POMDP, arises when the decision maker cannot observe the full current state before choosing an action. In this case the standard policy calculation cannot be applied directly.
Reinforcement learning solves MDPs without explicit transition probabilities or rewards, learning instead from agent-environment interaction. The Q-learning algorithm maintains a state-action array updated directly from experience, while learning automata, first surveyed by Narendra and Thathachar in 1974, update action probabilities directly with a rigorous proof of convergence.