Epistemic Reinforcement Learning for Belief Manipulation: SAT-Based Reasoning With Reward Machines

In many real-world scenarios, an agent must influence what another agent believes, not just the physical environment. We develop a reinforcement learning framework for situations where an agent must reason about another agent’s beliefs. The agent maintains a factored state of physical labels and explicit belief labels (\Delta); implicit beliefs (\Box) are derived on demand through SAT-based entailment over a shared knowledge base (Common Ground). To capture the temporal structure of belief-manipulation tasks, we use a condition-based Reward Machine whose transitions depend on both physical and epistemic information, and introduce BEQRM (Belief-based Epistemic Q-Learning for Reward Machines), which applies Q-learning to an epistemically augmented MDP with a convergence proof to an optimal policy. Potential-Based Reward Shaping further improves learning speed while preserving optimality. We validate the framework on three domains, the Chop Cup, Three-Card Monte, and a Waymo-style autonomous driving task, where BEQRM achieves robust task success, outperforming hierarchical and neural baselines.