-1
$\begingroup$

In the context of Decision Making and Game Theory, "Bellman's Equations and Bellman's Conditions of Optimality" are said to be some of the most important mathematical principles in this field.

Reading the corresponding Wikipedia page, I am trying to understand what is considered so "groundbreaking" about the Bellman's Condition of Optimality.

As far as I understand, Bellman's Principle of Optimality is saying that - for a policy to be considered as optimal, the policy must be optimal at each time point where the policy is being considered. If I have understood this correctly - isn't this kind of obvious?

To me, this sounds like a tautology - for something to be blue, the thing must also be blue.

I think I am obviously not understanding the above statements properly.

In short, could someone please explain why Bellman's Equations and Bellman's Conditions of Optimality are considered so "important and groundbreaking"?

$\endgroup$
1
  • 1
    $\begingroup$ Can you please quote the statement that you're confused about, rather than providing a possible misinterpretation of it? For example, you say "for a policy to be considered as optimal, the policy must be optimal at each time point where the policy is being considered", that doesn't look very accurate. I would prefer to see the original statement. $\endgroup$
    – nbro
    Commented May 9, 2022 at 15:23

1 Answer 1

2
$\begingroup$

In the context of decision theory (and reinforcement learning, which is the trendier name for this field of research nowadays), the Bellman equations are the most important equations because all algorithms used in reinforcement learning are derived from them. Even though they might not seem groundbreaking they are the foundations on which the whole field rests.

Let's take as an example the policy iteration algorithm. It consists of alternating a policy evaluation and a policy improvement step until convergence.

If we take the Bellman equation for the value function, we have $$V^\pi(s) = \mathbb{E}_{a_t \sim \pi(s), s_{t+1} \sim P(.|s, a_t)}[R(s, a_t) + \gamma V^\pi(s_{t+1}) | s_t = s]$$ where $\pi$ is the policy, $P$ the transition probabilities and $R$ the reward function.

You can calculate this exactly in the discrete case, if $P$ and $\pi$ are known, because it's a system of $|S|$ (the dimension of the state space) equations with $|S|$ unknowns (the $V^\pi(s)$).

Once you've evaluated your policy, you perform a policy improvement step which consists in setting (pay attention to where $\pi'$ and $\pi$ are used) $$V^{\pi'}(s) = \text{argmax}_a Q_\pi(s, a) = \text{argmax}_a \mathbb{E}_{s' \sim P(.|s,a)}[R(s, a) + \gamma V^\pi(s') | S_t=s, A_t=a]$$ The fact that the new greedy policy $\pi'$ is a strict improvement over $\pi$ can be derived from the Bellman equations (you can refer to the Sutton&Barto book section 4.2 for the full proof). It's called greedy because we've assumed that by changing $\pi$ by only looking at what's better one step ahead we've improved $\pi$ for all following steps.

The final piece of the puzzle is that we've designed a sequence of monotically improving policies. We know it converges towards the optimal policy in a finite number of steps because there's only a finite number of policies in the discrete case.

Hopefully this gives you an idea of why the Bellman equations are so important.

$\endgroup$
6
  • $\begingroup$ This is correct, but, although the OP mentions the "decision theory" and "game theory" contexts, I would also say that 1. dynamic programming is a general approach to solving problems, as long as they satisfy 2 conditions (optimal substructure and overlapping subproblems - refer to the CLRS book), 2. why that is the case in the case of RL, 3. mention the "Bellman optimality principle" and how it relates to what you just said. $\endgroup$
    – nbro
    Commented May 9, 2022 at 20:41
  • 1
    $\begingroup$ Just to double check before I amend my answer: 2. Is it because we are in an MDP setting where P(S_t|S_{t-1}, A_{t-1},S_{t-2},...) = P(S_t|S_{t-1},A_{t-1})? 3. The principal of optimality is what is used to derive the Bellman equations (e.g. the one I gave for the state value function), is that what you want me to mention? $\endgroup$ Commented May 10, 2022 at 20:18
  • $\begingroup$ I think the Bellman optimality equation (BOE) (a recurrence relation, which is a term used in CS in the context of DP) itself describes that an MDP has optimal substructure, i.e. the solution to $v(s)$ is a function of $v(s')$ (a subproblem) - if you know $v(s')$, you also know $v(s)$. Regarding the overlapping subproblems, $v(s')$ could be used to define both $v(s_1)$ and $v(s_2)$, so we can reuse $v(s')$ to compute $v(s_1)$ and $v(s_2)$, so they have overlapping subproblems. Note that this is how I've just tried to connect the 2 worlds - CS and RL - so I don't know if this is accurate. $\endgroup$
    – nbro
    Commented May 10, 2022 at 22:19
  • $\begingroup$ So, I am not sure if the Markov property is relevant here. I know we can use it to derive the BE from the definition of the value function (see here), so maybe the Markov property is somehow related. Regarding the principle of optimality, as stated e.g. in Wikipedia Principle of Optimality: 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, I think that's just the BOE. $\endgroup$
    – nbro
    Commented May 10, 2022 at 22:20
  • $\begingroup$ It all makes sense. I'm wondering if from this you have precise suggestions to make my answer better for OP. These are all valid points, but I'm not sure they explain why the Bellman equations are important. $\endgroup$ Commented May 11, 2022 at 19:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .