Reinforcement Learning (RL) agents often struggle with "non-Markovian" tasks—scenarios where what you should do next depends on what you’ve already done. While Reward Machines (RMs) provide a elegant way to encode these temporal dependencies as finite-state automata, they have historically required human experts to manually design the machine and write "labelling functions" to detect sub-goals.
RM-VLM changes the game by automating this entire pipeline. It uses Large Language Models (LLMs) to design the reward structure and Vision-Language Models (VLMs) to "see" progress, allowing agents to learn complex, multi-stage tasks directly from pixels and natural language.
TL;DR
RM-VLM automates the creation of Reward Machines by using an LLM to translate natural-language tasks into temporal logic automata and a VLM to ground those sub-goals in visual observations. By maintaining a probabilistic "belief" over the task state, it remains robust to noisy visual detections, significantly outperforming standard VLM-based reward methods.
What Problem Does This Paper Address?
Standard RL assumes the current observation tells you everything you need to know to get a reward. But real-world tasks are often sequential: "Unlock the drawer, then pick up the cube, but only if the light is green." These are non-Markovian tasks.
Reward Machines solve this by tracking task history through states in an automaton. However, they suffer from two major "manual engineering" bottlenecks:
- Specification: Someone has to define the states and transitions of the RM.
- Grounding: The system needs a "labelling function"—an oracle that can look at the environment and say, "Yes, the drawer is now unlocked."
In image-based environments, building these oracles usually requires access to the simulator's internal variables, which isn't possible in the real world.
Methods
The RM-VLM framework (illustrated in Figure 1) consists of four key components:
- Automated RM Generation: Given a task description (e.g., "Reach the red triangle, then the green..."), an LLM (Gemma-4-31B) generates the RM's states, transitions, and the atomic propositions (sub-goals) needed to track progress.
- VLM as a Labelling Function: A VLM acts as the "eyes" of the system. At each timestep, it evaluates the current image to predict which atomic propositions are true.
- RM State Belief: Because VLMs are imperfect and can produce "noisy" labels (false positives/negatives), RM-VLM doesn't just assume the VLM is right. Instead, it maintains a probability distribution (belief) over the possible states in the RM. This prevents a single flickering VLM detection from permanently derailing the agent's progress.
- Dense Reward Shaping: To help the agent learn faster, the authors supplement the sparse rewards of the RM transitions with Generative Value Learning (GVL). This provides a "warmer/colder" signal as the agent moves toward the next sub-goal.
Datasets
The authors evaluated RM-VLM across three distinct domains:
- GeoGrid: A 2D grid world used to test complex logic (e.g., "visit all objects in a specific order") and safety constraints ("avoid triangles").
- OGBench-Scene: A continuous-control robotic manipulation task involving drawers, windows, and buttons. This domain tests robustness against harder visual grounding and long-horizon control.
- MiniWorld-Pickup: A 3D first-person environment where the agent must collect objects. This tests the system under partial observability.
Key Insights and Ideas
- Division of Labor: The core "aha moment" is that VLMs shouldn't be asked to judge a whole complex task at once. Instead, the RM handles the temporal logic (memory), while the VLM handles the instantaneous perception. This modularity makes the system much more reliable.
- Robustness through Probability: By treating VLM labels as noisy "emissions" (similar to a Hidden Markov Model), the system can "filter" out visual errors. If the VLM briefly misidentifies a closed drawer as open, the belief mechanism ensures the agent doesn't prematurely think the task is done.
- LLMs as Task Architects: The paper shows that high-quality LLMs are remarkably capable of generating correct RM structures when provided with a description of the environment's physical constraints.
Key Results
RM-VLM consistently outperformed baselines that use VLMs directly for rewards (like GVL alone or VLM Success Detection).
- Success Rates: In GeoGrid, RM-VLM achieved near 100% success on tasks where non-RM baselines hovered around 10-30%.
- Noise Handling: In the robotic OGBench-Scene, the "Belief" mechanism was critical. Without it (using "Naive" tracking), success rates on the "Open" task dropped from 98% to 59% due to VLM labeling errors.
- Online Learning: When trained from scratch (online RL), RM-VLM matched the performance of agents that had access to ground-truth "oracle" labels, proving that VLM-distilled rewards are a viable substitute for hand-coded ones.
Limitations and Future Work
- Visual Ambiguity: The method's performance is tied to the VLM's ability to recognize states. If a sub-goal is visually subtle or ambiguous, the reward signal degrades.
- Error Rate Estimation: The belief mechanism requires knowing the VLM's true- and false-positive rates, which currently must be estimated from a small set of labeled trajectories.
- Expressiveness: Reward Machines are limited to "regular languages." They can't easily handle tasks that require counting (e.g., "pick up exactly five apples").
Future Directions: The authors aim to extend this to Hierarchical Reward Machines for even longer-horizon tasks and to develop a single policy that can generalize across many different natural-language task specifications.
Summary updated