Technical Summary: Infra-Bayesian Reinforcement Learning Agents Outperform Classical RL For Worst-Case Robustness

1. Problem Statement

Classical Reinforcement Learning (RL) and Bayesian RL operate under the assumption that an agent interacts with a fixed environment, typically modeled as a Markov Decision Process (MDP) or a Bayesian posterior over such models. This framework assumes realizability: the true environment (or a sufficiently accurate model of it) exists within the agent's hypothesis class.

However, this assumption fails in non-realizable settings, particularly those relevant to AI safety and embedded agency. In these environments:

• Policy Dependence: Other actors (predictors, humans, institutions) anticipate the agent's policy and respond to it, rather than just its realized actions.
• Knightian Uncertainty: The agent faces ambiguity where no grounds exist to construct a precise prior probability distribution over possible worlds.
• Model Misspecification: The real world contains systems of comparable or greater complexity than the agent, making it impossible for any tractable hypothesis class to contain a complete description of the environment.

Under these conditions, Classical Bayesian methods can produce "confidently wrong" posteriors, leading to unreliable decisions and unbounded regret. Standard value-based RL agents may fail to converge to optimal policies in policy-dependent environments (e.g., Newcomb's problem), often converging only to ratifiable policies.

2. Methodology: Infra-Bayesian Reinforcement Learning (IBRL)

The paper presents a proof-of-concept implementation of an Infra-Bayesian Reinforcement Learning (IBRL) architecture designed for finite-outcome, stateless decision problems. Unlike classical agents that maintain a posterior distribution over MDPs, the IB agent maintains a set of imprecise hypotheses represented as infradistributions.

Core Mathematical Objects

• a-measures (Affine Measures): The fundamental building block is an a-measure $a = (\lambda\mu, b)$, where:
  • $\mu$ is a probability measure over observation histories (representing ordinary stochastic uncertainty).
  • $\lambda \ge 0$ is a scale factor.
  • $b \ge 0$ is an offset term.
  • The evaluation of a bounded return function $f$ is given by $a(f) = \lambda E_\mu[f] + b$.
  • The offset $b$ preserves value from branches of the history tree ruled out by observations, ensuring dynamic consistency.
• Infradistributions ($\Psi$): A set of admissible a-measures. The agent evaluates a policy by its lower expectation:
  $$E_\Psi[f] = \inf_{a \in \Psi} a(f)$$
  This represents the value guaranteed against the worst admissible member of the hypothesis class.
• Mixture Types:
  • Classical (Bayesian) Mixture: A weighted combination of infradistributions ($\sum w_i \Psi_i$), representing uncertainty that can be averaged over.
  • Knightian Mixture: A set-union of infradistributions without weights, representing ambiguity where the value is determined by the least favorable component.

Algorithmic Components

1. Representation: The agent stores only the extremal minimal points of the infradistribution (analogous to vertices of a convex polytope), ensuring computational tractability.
2. World Models: The implementation supports specific compressed representations for:
   • Bernoulli Bandits: Histories represented as $(N, R)$ pairs; measures as sets of $(c_i, p_i)$ pairs.
   • Newcomb-like Problems: The world model contains the full reward matrix and predictor accuracy; no learning of internal states occurs as the structure is known.
3. Decision Process:
   • The agent discretizes the policy space $\Pi$.
   • It computes the lower expectation for each policy: $E_{\Psi(\pi)}[f] = \inf_{a \in \Psi(\pi)} a(f)$.
   • It selects the policy $\pi^*$ that maximizes this lower expectation (Maximin strategy).
4. Update Rule: Upon observing an event $L$, the agent performs an IB-style update:
   • Restricts the measure $\mu$ to the observed branch ($\mu_L$).
   • Transfers the expected value of the unobserved branches into the offset term $b$: $(\lambda\mu, b) \to (\lambda\mu_L, b + \lambda\mu((1-L)g))$.
   • Renormalizes the infradistribution.
   • Due to the linearity of the update, no new extremal points are created; only existing ones are updated.

3. Key Contributions

1. First Proof-of-Concept Implementation: The authors formulate and implement a finite-outcome IBRL architecture based on a-measures, infradistributions, and IB-style updates.
2. Recovery of Classical Behavior: The architecture is shown to recover ordinary Bayesian behavior in the degenerate case where each infradistribution has a single minimal point and all uncertainty is classical.
3. Worst-Case Performance: Empirical demonstration that an IB agent achieves lower worst-case regret than a classical Bayesian agent in environments with Knightian uncertainty.
4. Optimal Policy-Dependent Decision Making: Demonstration that the IB agent obtains optimal rewards in Newcomb-like environments, outperforming classical decision theory agents (Causal and Evidential) which fail to capture the correct causal structure or converge to optimal policies.

4. Experimental Results

A. Knightian Uncertainty (Adversarial Bandits)

• Setup: A two-armed Bernoulli bandit where reward probabilities $p_1 \in [0.3, 0.7]$ and $p_2 \in [0.4, 0.8]$ are chosen adversarially or time-dependently. The agent knows only the constraints, not the specific probabilities.
• Classical Agent: Must assume a precise prior (e.g., point masses at corners). Behavior is highly sensitive to this arbitrary prior choice.
• IB Agent: Represents the interval constraints directly as Knightian uncertainty. It identifies the worst-case environment $(p_1=0.3, p_2=0.4)$ and consistently selects Arm 2, guaranteeing an average reward of 0.4.
• Outcome: The IB agent achieves a lower worst-case regret compared to the classical agent. The IB agent correctly refuses to "learn" from potentially adversarial patterns that might look attractive but are not robust.

B. Policy-Dependent Environments (Newcomb's Problem)

• Setup: A variant of Newcomb's problem with an imperfect predictor of accuracy $\alpha$. The agent chooses a policy to one-box with probability $p$.
• Outcome: The IB agent consistently selects the optimal policy based on the predictor's accuracy:
  • For $\alpha > 0.55$, it one-boxes (optimal).
  • For $\alpha < 0.55$, it two-boxes (optimal).
• Comparison: Causal Decision Theory agents two-box regardless of accuracy (missing large rewards), while Evidential Decision Theory agents one-box but for reasons that may fail in other causal structures. The IB agent selects the optimal action for the correct structural reasons.

5. Significance and Claims

The paper claims that this work bridges the gap between the formal promise of Infra-Bayesianism (robust reasoning under non-realizability) and practical agent implementation.

• Robustness by Design: The results suggest that for agents operating in misspecified or policy-dependent environments, optimizing for worst-case guarantees (via lower expectations) provides robustness that average-case optimization (Bayesian RL) lacks.
• Distinction of Uncertainty: The implementation concretely demonstrates that distinguishing between classical probabilistic uncertainty and Knightian uncertainty leads to fundamentally different and safer agent behaviors.
• Foundational Step: While the current implementation is limited to finite outcomes and small hypothesis spaces, it serves as a necessary step toward RL systems that remain robust under model misspecification. The authors note that regret bounds for their IB agent are linear (an improvement over classical RL in these specific non-realizable settings, though still not sublinear), and that scaling to continuous spaces and multi-step processes remains an open challenge for future work.

The paper concludes that IBRL offers a viable path toward agents that can reason effectively when the "grain of truth" assumption of classical Bayesian RL is violated.