Source-linked AI summary
Detecting Spiky Corruption in Markov Decision Processes
Jason Mancuso, Tomasz Kisielewski, David Lindner, Alok Singh
TL;DR
Misspecified rewards can lead RL agents to undesired behavior, while detecting or avoiding them remains an open problem. This paper proposes spiky corruption assumptions and a detection algorithm for CRMDPs; in toy gridworlds, it detects corruption and learns optimal policies despite it.
Problem
Misspecified rewards can lead agents to undesired behavior, and detecting or avoiding such rewards remains an open problem in RL.
Source: §1 · p. 1Method
The paper assumes corruption is spiky relative to state-space distance, detects corrupt states using Lipschitz violations, and defines reward bounds for policy learning.
Source: §1 · p. 1, §3.1 · p. 2, §3.2 · p. 3Results
Spiky CRMDPs need not have finite diameter and can be solved in the usual MDP formalism; in two gridworlds, the algorithm learned optimal policies using about twice the data of an agent with hidden-reward access.
Source: §6 · p. 5, §5.2 · p. 5Takeaways & Limitations
Smooth-reward and spiky-corruption priors can encode useful inductive biases in relevant environments.
Source: §6 · p. 5The approach requires quite a few assumptions, its experimental support is in toy gridworlds, and learning the distance metric from trajectory data remains future work.
Source: §6 · p. 5
Abstract
from arXiv · showhide
Current reinforcement learning methods fail if the reward function is imperfect, i.e. if the agent observes reward different from what it actually receives. We study this problem within the formalism of Corrupt Reward Markov Decision Processes (CRMDPs). We show that if the reward corruption in a CRMDP is sufficiently "spiky", the environment is solvable. We fully characterize the regret bound of a Spiky CRMDP, and introduce an algorithm that is able to detect its corrupt states. We show that this algorithm can be used to learn the optimal policy with any common reinforcement learning algorithm. Finally, we investigate our algorithm in a pair of simple gridworld environments, finding that our algorithm can detect the corrupt states and learn the optimal policy despite the corruption.
1 Introduction
Misspecified rewards can produce undesired behavior, and detecting or avoiding them remains an open RL problem. This work proposes a learnable CRMDP subclass based on corruption that is “spiky” relative to a state-space distance.
1 Introduction
- CRMDPs model agents receiving corrupted reward signals, and prior work showed learnability only under additional assumptions, including a strong set enabling sublinear regret for quantilizing agents [Everitt et al., 2017].Other assumptions may yield distinct subclasses that are useful in practice.Source: §1 · p. 1
1.1 Problem motivation
- CRMDPs can represent varied reward-misspecification settings, including wireheading and reward functions learned from human or expert input.The cited examples include side effects, sensory malfunction, preference learning, and inverse reinforcement learning.Source: §1.1 · p. 1
1.2 Solution motivation
- The approach assumes the true reward is smooth over states while corruption is spiky, extending a supervised-learning analogy from noisy labels to reward signals.In the analogy, actions select labels and an oracle supplies labels that may be fallible [Rolnick et al., 2017].Source: §1.2 · p. 1, §1.3 · p. 2
1.3 Related Work
- Unlike related safe-exploration work that does not address corruption, this approach uses reward Lipschitz conditions and can allow any state-space metric.Automatically learned distance functions are suggested as future work to avoid requiring an explicitly provided metric.Source: §1.3 · p. 2, §1.2 · p. 2
2 Problem statement
The problem is to identify corrupt states and learn an optimal policy using observed rewards, despite the general impossibility result for CRMDPs. Spiky CRMDPs impose distance-based smoothness and Lipschitz-violation conditions to define a learnable subclass.
2 Problem statement
- A CRMDP is a finite-state MDP with an additional corrupt reward function; states where observed and true rewards agree are non-corrupt, and the remaining states are corrupt.The agent observes the corrupt reward, while the learning goal is an optimal policy with respect to the true reward.Source: §2 · p. 2
- A Spiky CRMDP adds a state-space metric and a non-decreasing Lipschitz-violation measure, with the distance and rewards constrained together.The distance is intended to capture smoothness of the true reward; corruption should be less smooth, and scaling rewards also requires scaling the distance.Source: §2 · p. 2
- The violation measure quantifies departures from the Lipschitz condition using observed rewards: NLV counts violating states, while TLV sums violation magnitudes.For finite state spaces, the counting measure is a reasonable choice.Source: §2 · p. 2
3 Theoretical Results
Under the Spiky CRMDP assumptions, the paper gives a procedure that exactly identifies corrupt states and derives reward bounds for learning despite corruption. An optimal policy can be recovered using the lower bound when an underlying optimal policy avoids corrupt states, a strong condition especially in stochastic environments.
3.1 Corruption identification
- Algorithm 1 returns exactly the corrupt-state set by sorting states by Lipschitz violation and stopping when no further violations remain.The result relies on assumptions 2 and 3 of the Spiky CRMDP definition.Source: §3.1 · pp. 2–3
3.2 A posteriori bounds on regret
- Upper and lower Lipschitz bounds estimate rewards from non-corrupt states, and an upper-bound-optimal policy has a regret bound derived from them.The bounds can be computed after identifying corrupt states, using the distance function and rewards in non-corrupt states.Source: §3.2 · p. 3
- The regret bound can be as large as the full range of possible cumulative rewards, limiting its usefulness as a theoretical result.The authors also propose using improvements to the bound to select costly reward queries, but leave this active-learning direction unexplored.Source: §3.2 · p. 3
3.3 Optimality with corruption avoidance
- If an underlying optimal policy avoids corrupt states, a policy optimal under the lower Lipschitz bound is also optimal for the underlying MDP.The paper notes that the avoidance assumption is especially strong in stochastic environments, consistent with the zero-regret guarantee.Source: §3.3 · p. 3
4 Practical considerations
The practical algorithm sorts across the full state space, requiring complete state-space knowledge and computational resources. An online variant requires a stronger assumption, while memory use remains a practical concern.
4 Practical considerations
- Algorithm 1 sorts the entire state space, requiring complete state-space knowledge and computational resources for sorting.Source: §4 · p. 3
4.1 Modification for Online Learning
- Online use requires assumption 3′ to hold over every possible trajectory, a stronger condition that restricts the eligible environments.With this condition, the online variant applies Algorithm 1 to sampled trajectories and updates the policy using the reward lower bound; its bound approximation is pessimistic for corrupt states but converges as the known non-corrupt set grows.Source: §4.1 · p. 4
4.2 Memory complexity
- Memory can become problematic even when storing only encountered states, and the authors describe optimizations that had no effect in their small toy environments.Source: §4.2 · p. 4
5 Experiments
In two toy gridworlds, the algorithm learned the optimal policy without hidden-reward access, using about twice as much data as an agent with that access. The experiments compare PPO baselines with the algorithm and report reward and sample-complexity measures.
5 Experiments
- The experiment compares PPO using corrupt rewards, PPO using hidden rewards, and PPO with Algorithm 2 replacing identified corrupt-state rewards with Lipschitz bounds.Source: §5 · p. 4
5.1 Toy Spiky-CRMDP
- The two gridworlds use Manhattan distance; in OnTheWay the optimal policy encounters corrupt states, but remains optimal after reward substitution with lower bounds.The environments place unusually high corrupted rewards in red cells; Figure 1 marks the start, goal, true rewards, and corrupted rewards.Source: §5.1 · p. 4, Figure 1 · p. 4
5.2 Results
- PPO with corrupt rewards quickly learned the corrupt-optimal policy, while PPO with hidden rewards needed significantly more data to learn the optimal policy.The hidden-reward problem was more complicated and could not be solved with a constant policy.Source: §5.2 · p. 4
- Table 1 reports final corrupted and hidden rewards and sample complexity, defined by episodes until a 0.9-momentum return average reaches its optimum; sample-complexity estimates are noise-sensitive.Source: Table 1 · p. 5
- With hidden-reward access, the algorithm performed comparably to the baseline because it encountered no states it could identify as corrupt.Source: §5.2 · p. 5
- Without hidden-reward access, the algorithm learned the optimal policy in both environments, requiring about twice as much data as the hidden-reward agent.The authors suggest the extra data likely reflects smaller payoff differences between optimal and suboptimal policies, rather than learning reward bounds.Source: §5.2 · p. 5
6 Conclusion
Spiky CRMDPs address limitations of previously learnable CRMDP classes without requiring finite diameter or decoupled RL. The paper also presents Lipschitz rewards and spiky corruption as strong Bayesian RL priors, while noting assumptions and the need to learn the distance metric for practical use.
6 Conclusion
- Spiky CRMDPs need not have finite diameter and can be solved in the usual MDP formalism without decoupled RL.Source: §6 · p. 5
- The solution still requires substantial assumptions, and practical use of the regret bound depends on learning the distance metric from trajectory data.The authors identify online or active reward learning as settings for this future work.Source: §6 · p. 5
- Lipschitz reward functions and spiky corruption are framed as strong Bayesian RL priors, with experiments demonstrating one instance of usefulness in misspecified environments.The authors suggest these priors may apply in a wider variety of practical settings where Bayesian RL has fallen short.Source: §6 · p. 5
A Proofs of theoretical results
The proofs establish that Algorithm 1 identifies the corrupt states by processing them before non-corrupt states and stopping at a state with no remaining Lipschitz violation. They also use reward bounds to relate policies optimal under the bounds to policies optimal under the true reward.
A Proofs of theoretical results
- Algorithm 1 adds only corrupt states and stops at a non-corrupt state, establishing that it returns the corrupt-state set.Corrupt states are processed before non-corrupt states; the proof shows the addition test cannot accept a non-corrupt state and the stopping test cannot select a corrupt state.Source: A Proofs of theoretical results · p. 6
- Because ub(x) is at least R(x), the proof bounds the performance gap for ub-optimal policies against an R-optimal policy.It derives another average-cumulative-reward bound and then takes a supremum over ub-optimal policies to obtain the final bound.Source: A Proofs of theoretical results · pp. 6–7
- Any lb-optimal policy is also R-optimal, since the R-optimal policy remains optimal under lb and other lb-optimal policies earn at least as much under R.Source: A Proofs of theoretical results · p. 7
B Reducing memory consumption
The memory-saving variant retains every known corrupt state but keeps only a small, randomly trimmed set of non-corrupt states to update lower-bound estimates. Its convergence depends on encountering a state that gives the best bound no later than the corrupt state; the toy experiments saw no practical effect from the cache modification.
B Reducing memory consumption
- The algorithm must store all corrupt states, but can reduce memory by retaining only a small set of non-corrupt states and randomly removing states when that set grows too large.The retained non-corrupt states update cached lower bounds for known corrupt states.Source: B Reducing memory consumption · p. 7
- The lower-bound estimate converges correctly if a state giving the best bound is not encountered before the corrupt state.The stronger assumption suggests that best-bound state may occur in the trajectory that identifies the corrupt state; the authors do not expect practical problems from this optimization.Source: B Reducing memory consumption · p. 7
- In the toy environments, the cached set exceeded the state space, so the memory-saving modification had no practical effect.Source: B Reducing memory consumption · p. 7
- Future work could further reduce memory use by representing state-space information differently, such as with neural-network approximations.Source: B Reducing memory consumption · p. 7