Corrupt Reward MDPs

Context

Everitt2019 - Towards Safe Artificial General Intelligence uses corrupt reward MDPs to separate true reward from observed reward. The point is to model cases where the learner receives high feedback in states that are bad according to the designer’s intended objective.

Formal Statement

A corrupt reward MDP is:

$$\mu =⟨S,A,R,T,\dot{R},C^r⟩,$$

where S is a finite state set, A a finite action set, R a finite reward set in [0,1], T(s' | s,a) the transition kernel, R_dot:S -> R the true reward function, and C^r:S x R_dot -> R_tilde a reward-corruption function. The state-specific corruption function is written:

$$C_s^r(\dot{r}):=C^r(s,\dot{r}).$$

The observed reward is:

$$\tilde{R}(s)=C_s^r(\dot{R}(s)).$$

The agent observes histories built from states, actions, and observed rewards, while performance is evaluated against true reward.

Derivation / Construction

• If the hypothesis classes contain all true reward functions and all corruption functions, the same observed reward process can be explained by incompatible true reward/corruption pairs.
• Everitt’s CRMDP no-free-lunch theorem states that, under such unconstrained hypotheses, no policy can get a strong worst-case regret guarantee; true reward is effectively unlearnable without assumptions on corruption.
• Decoupled reward data extend the model so an agent in state s may observe reward information about another state s'. This changes the observation graph from self-only reward observations to cross-state evidence.
• If every state’s reward is observable from a safe state or from more than 2q states when at most q states are corrupt, then an exploration policy can learn the true reward function in finite expected time.
• Once the true reward is learned under those conditions, a true-reward Bayesian agent can obtain sublinear regret by combining reward-identification exploration with a standard MDP-learning algorithm.
• Quantilization gives a different robustness route: sample from the top quantile of actions or policies instead of fully maximizing a potentially corrupted objective.

Implications

• Reward corruption is not just stochastic reward noise; the hard case is biased feedback that the agent can seek out.
• Ordinary RL’s self-observation pattern is especially weak because each state’s reward is usually observed only from that same state.
• Oversight methods become safer when reward evidence is decoupled from the current state, comes from multiple contexts, or can be checked from known-safe contexts.
• CRMDPs make clear why reward-channel integrity belongs in Goal Alignment and Safe Reinforcement Learning, not only in robustness or exploration.

Links

• Reward Tampering
• Goal Alignment
• Everitt2019 - Towards Safe Artificial General Intelligence
• Safe Reinforcement Learning
• Causal Decision Making