Beyond Scalar Rewards: An Axiomatic Framework for Lexicographic MDPs

We thank the reviewer for the constructive criticism and thoughtful questions. We reply to the questions below.

Q: What specific types of problems can this framework model compared to existing ones, like CMDPs?

A: There are CMDP problems that cannot be modeled as LMDPs. For example, any CMDP problem that leads to non-uniform optimal policy or stochastic optimal policy (and these do exist).

In general, an LMDP cannot be modeled as a CMDP. However, if we fix the starting state distribution and, given K priority levels, we know the optimal value of all but the lowest priority level – i.e., we know $V^\star_1, …, V^\star_{K-1}$ – then it is possible to turn the LMDP problem into a CMDP, by constraining these $K-1$ values with the known optimal values and optimizing the lowest-priority value – that is,

Basically, the first $K-1$ optimization problems are turned into constraints similar to turning $\max_x f(x)$ into $\max_x 0 \text{ subject to } f(x) ≥ f^\star$. We believe this to be a rather unnatural way of specifying the problem.

When we have a single unsafe outcome, CMDP is constraining the probability of this outcome, assuming access to optimal achievable probability threshold (i.e., $V^\star_1$) rather than optimizing it. We contend that this assumption (of access to optimal values) is a limitation of CMDP framework that LMDPs naturally address.

Q1: In line 124, what are the "other methods" being referred to?

A: We claim that vNM reward systems have advantages compared to “other”s. Another way of specifying rewards is to assign a reward of 1 to optimal actions and 0 to all other actions. It is not practical but is still a valid reward system. More generally, there are many reward functions that can lead to the same optimal policy. A simple case: there are 3 actions $a, b, c$. We prefer $a \succ b \succ c$ but we use a reward function that satisfies $r(a) > r(c) > r(b)$ – notice that $b$ and $c$ are swapped. The optimal action is the same but the reward function has some undesirable properties. Suppose the initial policy selects action $b$ and then we optimize it (w.r.t. rewards) to $c$ but, due to “bad” reward function, the policy actually gets worse. On the other hand, with vNM rewards, increasing expected reward is guaranteed to result in a more preferred policy. Ad-hoc reward shaping methods can also be considered to be part of the "other" we mentioned.

The advantage of vNM reward systems being insensitive to environment mechanics is also nicely demonstrated in the example in the response to first Q of reviewer AHWB where we want rewards that work regardless of the shape of the maze and hazard probabilities.

Q2: line 36?

A: They are not connected. The writing should be changed to "... the time that it takes. Lexicographic objectives are also reminiscent of Asimov’s Three Laws of Robotics..."

Q3: What does the Q* in Theorem 7 refer to?

A: The definition of Q* is the same as in scalar-reward MDP with the difference that maximization is w.r.t. lexicographic ordering of vectors. We will revise the text to clarify this.

Q4: Do you conjecture that the proposed LMDP framework satisfies a Bellman-type equation?

A: A Bellman equation does indeed exist and it is the same as the one for scalar-reward MDPs: $Q(s, a) = \mathbb{E}[R(s, a) + \gamma \max_{a’} Q(s’, a’)]$ with the distinction that Q-values are vectors and maximization is w.r.t. lexicographic ordering of vectors. However, in the lexicographic case, the Bellman operator is no longer a contraction mapping, so iterating it does not give us an algorithm with convergence guarantees.

Q: Significance of LMDPs and comparison to MDP and CMDP?

A: Let us provide an example. Consider the classic problem of a robot in a maze trying to escape. To incentivize the robot to escape as fast as possible we either assign a reward of -1 for each step or we use a discount factor < 1 and assign a positive reward for escaping. Now consider a maze with hazards that can possibly destroy the robot. We are first and foremost interested in maximizing the probability of a safe escape out of the maze. Our second priority is to do so as fast as possible. Now suppose we have to design a reward function for this task without having seen the maze, e.g., we don’t know how likely the hazards are to destroy the robot or how large the maze is. The previous approaches break down in this setup. For a scalar reward function we can always design a maze such that the robot takes a more hazardous path by making safe paths longer and making hazard probabilities smaller. To quote Rich Sutton: “Approximate the solution, not the problem.” Using discount factors or negative rewards would be an approximation of the problem in this case. The true problem is lexicographic in nature. The reward for a hazardous event is (-1, 0), the reward for a safe step is (0, -1), and the reward for escaping the maze is (0, 0). Moreover, to be able to use CMDPs for this problem, we need to know what the optimal hazard probability is in order to set a constraint on it. Additionally, changing the starting state to a point in the maze that has a different optimal hazard probability necessitates respecifying the CMDP. Working on a better approximation of the solution to LMDPs is an interesting direction that we leave for future work.

Q1: Do standard MDP algorithms work with LMDPs? What changes have to be made?

Q2: Have the authors tested methods for solving LMDPs? Are there any challenges not found in the standard MDP setting?

A: Value iteration is not guaranteed to converge since the Bellman operator is not a contraction mapping in the lexicographic setting. Intuitively, we first need to find the set of optimal actions w.r.t. Q_1, then construct an MDP restricted to these actions, and then optimize w.r.t. Q_2. Since value iteration for Q_1 isn’t guaranteed to converge in any finite number of steps we might never get to the second stage. What is sometimes done is to have a tolerance threshold τ such that Q-values that differ less than τ are considered equal. τ can go to 0 during training. However, this is a somewhat ad-hoc approach and can be difficult to tune. A method of encouraging Q-values for different actions to be equal via some kind of regularization could be an interesting direction for future work. Similar issues appear in policy-based algorithms as well. This new open problem that we also briefly discuss in future works is also the reason we cannot have an empirical evaluation.

Q3: Can we state more formally what classes of problems are solved by LMDPs but not CMDPs?

A: Please see answer to first Q of reviewer ii8W.

Certainly. We will add discussion and analysis of approximate Q-learning for LMDPs:

$\tau$-Approximate Q-learning for LMDP

Input: LMDP with $d$-dimensional reward; threshold $\tau \in \mathbb{R}^d_+$

1. $Q(s, a) \leftarrow 0$ for all $s \in \mathcal{S}, a \in \mathcal{A}$
2. $\alpha \leftarrow 0.1$ # learning step-size
3. $\epsilon \leftarrow 0.1$ # $\epsilon$-greedy policy
4. Sample initial state $s \sim P_0$
5. Repeat:
6. $\quad$ Let $\mathcal{A}^\star_0(s) = \mathcal{A}$
7. $\quad$ Let $\mathcal{A}^\star_i(s) = \set{ a \ |\ Q_i(s, a) \geq \max_{a \in \mathcal{A}_{i-1}^\star} Q_i(s, a) - \tau_i }$ for all $i \in [d]$
8. $\quad$ Sample action $a \sim \epsilon\ \text{uniform}(\mathcal{A}) + (1-\epsilon)\ \text{uniform}(\mathcal{A}^\star_d(s))$
9. $\quad$ Take action $a$ and transition into state $s'$ and obtain reward vector $R \in \mathbb{R}^d$
10. $\quad$ $Q_i(s, a) \leftarrow (1-\alpha)Q_i(s, a) + \alpha (R_i + \gamma \max_{a' \in \mathcal{A}_{i-1}^\star(s')} Q_i(s', a'))$
11. Return $\pi(s) = a \in \mathcal{A}^\star_d(s)$

We thank the reviewer for their positive evaluation of our work. Please see the other responses for some arguments in favor of the significance of our work.

Hi reviewer gQjL,

Have you reads the other reviews (and the author responses)? Has your opinion on the significance of the work changed?

Thanks,

area chair

We thank the reviewer for the detailed feedback and thoughtful questions. We will address the minor issues (abstract, define lex max). We respond to questions below.

Q: Is there a [problem] where one should use this formalism as opposed to [CMDP]?

A: We argue for an axiomatic approach to using objectives. If one accepts the independence axiom of von Neumann & Morgenstern as a natural axiom of rationality (which we the authors do), then one should use LMDPs (or MDPs if continuity is also accepted). For more comparison see also the response to first Q of reviewers ii8W and AHWB.

Q: Comparison to (Shakerinava & Ravanbakhsh, 2022) and (Bowling et al. 2023)?

A: This work is a natural next step for those papers. Is there a more general setup than vNM’s four axioms and what does that more general utility structure look like for MDPs? If one accepts the very natural Completeness, Transitivity, and Independence axioms then Hausner tells us that lexicographic rewards are the most general setting there is. We extend this result to MDPs and see that, similar to the scalar reward setting, lexicographic rewards take a simple recursive form.

Q: Theorem 4.2 of (Shakerinava & Ravanbakhsh, 2022) vs. Theorem 3?

A: The final recursive reward decomposition equation for both theorems look similar. The distinction is that in Theorem 3 rewards are vectors instead of scalars, and the factor Γ is a lower triangular matrix with positive diagonal instead of a positive scalar. A similar explanation goes for Theorem 4.1 of (Bowling et al., 2023) vs. Theorem 4. However, our Theorems 5, 6, 7 don’t have similar counterparts in these previous works.

Q: What specific novel insights does your work provide that these earlier papers did not establish?

A: Apart from Hausner’s work in 1954, before Bellman’s introduction of MDPs in 1957, recent prior works have largely ignored the lexicographic setting. It is only mentioned in passing in (Bowling et al. 2023). We provide a long overdue connection of Hausner’s work to MDPs and show that LMDPs (with a specific structure on the Γ matrix) provide the most general reward setting. Colloquially, the “correct” way to go beyond scalar-reward MDPs is to go to the LMDP setting (not, e.g., CMDPs).

Q: AI Safety problem where this is useful?

A: In AI safety, LMDPs can be appropriate when we introduce a highest-priority objective such as “do no harm.” In this setting, the agent must first minimize the probability of harm before optimizing any secondary performance criteria. This cannot be faithfully captured by scalar rewards. Also, the optimal harm threshold likely depends on the context so CMDPs cannot be used either. LMDPs offer a principled way to express such strict prioritization.

Hi reviewer 7CHw,

Have you read the rebuttal? What are your thoughts?

Thanks,

area chair