Bellman Equations are basic tools to characterize MDPs and MRPs. Here we aim to lay theoritcal foundations for general MDPs. While sometimes it's necessary and convenience to impose certain constraints, e.g. polish space or discrete space, to ensure regularity.

Bellman Equations

Bellman Equations are a family of equations that describe recursive relationships for value functions and Q-functions. There are many related terms, which we'll introduce below. In general, we distinguish main types
1. Bellman Expectation Equations, which are expectation recursions with a fixed policy .
2. Bellman Optimality Equations, which are recursions that characterize the optimal value functions and Q-functions.
The overall picture is shown below

Bellman Expectation Equations

Let's start with the standard MDP

For Q-function with a fixed policy , by definition We expand the probability By the Markov property of MDP This gives the Bellman Expectation Equation for Q-function
Now consider the MRP where the dynamics model and reward model are marginalized by It is trivial that we can derive a BEE for value functions using the exact technique as for Q-functions. The result is shown below

Bellman Expectation Operators and Backups

Based on the form of BEEs, we can perform recursive updates for value functions and Q-functions. It is interesting that the formulation of BEEs and recursive updates are rather simple dynamic programming objects, but they are given specific names, probably for their unique importance in the foundation of RL. Concretely, for policy , we define the bellman expectation operator for Q-functions as This basically means using policy to choose the first action and then follow Q-function . There might not be any stable policy that induces , but is useful in many algorithmic aspects. It is clear that has fixed point , below we'll prove that such fixed point is unique under MDP setting.
Proof: Let's consider the bounded measurable function space , we have For any $𝓁$ , we have This means is a contraction over $𝓁$ . Note that is complete under the norm , hence is a Banach space. By Banach Fixed Point Theorem, we determine that
1. has the unique fixed point .
2. Starting from any $𝓁$ , iteration converges to with speed
On the other hand, we call the operation of applying to a given Q-function a Bellman expectation backup.
The Bellman operator for value functions is defined analogously. Here we only give its form Hence under the MRP induced by we write Note that the reward and transition functions are all conditional on the given policy . People may ask should there be a "policy" behind ? The answer is no, because can be some function that is not induced by any policy, e.g. a random initialization.

Bellman Optimality Equations

BOEs characterize the property of optimal value functions and Q-functions. More specifically, they imply that any optimal value functions can be achieved by some deterministic policies, which are rather surprising. Consider the standard MDP First we define the optimal Q-function pointwise. Let denote the set containing all valid policies, we have Note that is uniformly bounded, hence the supremum must exist. Here the definition applies to any measurable state and action spaces. The supremum operator raises the issue that may not be measurable and hence not integrable, while is always measurable with measurable policy . If we stick to general measurable spaces, such measurability issues will continue to arise. Since the point here is not measure theory, we restrict state and action spaces to discrete spaces. In this case, the MDP simplifies to

BOE and Characterizations of and

Now we give the form of the BOE for The BOE has a beautiful connection with the optimal policy . In order to show it, we first define the Bellman Optimality Operator We still the call the operation to apply a Bellman Optimality Backup. Now we introduce the main theorem
- 【Theorem 1. BOE and 】For discrete state and action spaces and , the BOE satisfies if and only if is the optimal Q-function defined by .
Proof: Step 1. Still consider the bounded function space $𝓁$ Which is a Banach Space. By identical arguments as used in the proof in 2.1.1 , is a contranction mapping on $𝓁$ . This implies that has unique fixed point in $𝓁$ , denote as . Now consider any valid policy , it is clear that The here is defined pointwise. It is clear that is monotonic, in the sense that $𝓁$ This gives As this holds for any and any , we have .

Step 2. For any , we can select an action , such that As is discrete, is a valid policy, denote as . We calculate Let be the Q-function induced by . We want to control This further gives As is fixed, and can be made arbitrarily close to , we conclude . Together these give
Identical results hold for value functions. Here we only give the statements. Let's first define the optimal value function pointwise The BOE for follows Hence the Bellman Optimality Operator is defined as Finally the theorem holds
- 【Theorem 2. BOE and 】For discrete state and action spaces and , the BOE satisfies if and only if is the optimal value function defined by .

The achievability of and

Another issue is that the pointwise definition doesn't guarantee the existance of a policy that achieves or naturally. However by Theorem 1. and 2. , it is easy to see such a sufficient condition
- If the supremum over can be attained for any , then the induced deterministic policy satisfies
Indeed, we can further proof that such condition is also necessary for .
- 【Theorem 3. Achievability for 】 can be achieved by certain policy if and only if the supremum in can be attained for any .
  
  Proof: The sufficiency is obvious. Let's consider the necessity. Assume exist a state such that And the supremum can't be achieved by any , that is We want to show that for any policy This is a classic result in measure theory. Below we'll give a standard proof to it. Define Consider event It is clear that In this way Hence when supremum is not attained, there's no policy can achieve .
A subtle difference is that the supremum condition is not necessary for . The problem is that, if we observe , the supremum is weighted by a probability measure . Therefore, the supremum on a measure-zero set is irrelevant. A simple example is shown below
- 【Example 4. A two state counter example】Consider an MDP such that with being the absorbing state, action space , reward function , , and transition kernel , . The transition graph is shown as below
  
  For any policy , we have These are independent of any policy. Hence holds for any . But can't be attained by any , hence This means no policy can achieve .
Intuitively, this implies that by excluding the measure-zero set, we can have a necessary and sufficient condition for . Indeed, under the discrete setting, this is correct.
- 【Theorem 5. Achievability for 】For discrete state and action spaces, denote Then can be achieved by certain policy if and only if for holds for any .
At last, the above arguments together yield an important message that, if the optimal and are achievable, they must can be achieved by deterministic policies. This is the reason why a wide range of optimization methods only consider deterministic policies.