betaFeedback

WorksComputer Science

RM-VLM: From Natural-Language Task Descriptions to Vision-Grounded Reward Machines

Abstract

Reward machines (RMs) have been proposed as a reward formulation in reinforcement learning (RL) to capture non-Markovian tasks where credit assignment depends on history. By representing reward functions as automata, RMs expose the task's temporal structure and allow such rewards to be handled within a Markovian framework. However, they assume a labelling function, a proposition-grounding oracle for observations, which must be manually engineered for each environment, limiting their wider applicability. In this work, we address this limitation by proposing RM-VLM, a novel approach in which a large language model (LLM) generates an RM from a natural-language task description, and a vision-language model (VLM) acts as the labelling function, grounding the RM's propositions over image-based observations during RM-guided policy learning. A VLM-based value function estimator is used to assess the agent's progress towards each RM transition and derive a dense reward signal. We evaluate RM-VLM on three domains covering non-Markovian grid-world navigation, robotic manipulation, and 3D object collection. Our experimental results show that RM-VLM consistently achieves higher task success rates than existing VLM-based reward methods across all tested domains.

Introduction

Many reinforcement learning [RL; 47] tasks require an agent to remember what it has done. An object may be worth collecting only after a prerequisite has been met; an action may be rewarding only at a particular stage of a task. In these settings, reward depends on the history of states and actions, rather than on the current observation alone. Such non-Markovian rewards make credit assignment depend on history, and remain difficult to specify and learn with standard RL methods.

Reward machines [RMs; 48] offer a structured way to address this challenge. An RM represents a task as an automaton whose states compactly summarise task history and whose transitions capture progress through sub-goals. By augmenting the agent’s state with the RM state, an RM makes the history relevant to reward explicit and can provide intermediate rewards as the task unfolds. Applying RMs, however, typically requires two forms of manual engineering: specifying the automaton and constructing a labelling function that maps observations to the atomic propositions governing its transitions. Labelling functions often rely on access to the environment’s internal state, which may be unavailable in image-based or real-world settings.

Existing methods address parts of this problem, but retain significant dependencies. ARM-FM [7] uses foundation models but implements the labelling function from the environment’s source code. Ground-Compose-Reinforce [GCR; 27] learns a labelling function from trajectories, but requires manual labels. Methods such as ISA [13], FORM [3], and Prob-IRM [37] can learn RM structures from executions, yet assume that a labelling function is already available. The challenge is therefore to obtain both the task structure and its grounding in observations without relying on either extensive manual labelling or privileged access to the environment.

Vision-language models (VLMs) provide a potential source of visual reward supervision [4, 30, 31, 43]. Directly using them to score non-Markovian tasks is difficult, however, because the significance of an observation depends on what preceded it. Moreover, VLM predictions over image sequences can be biased by temporal position: an observation may receive a higher score because it appears later in a sequence, rather than because the agent has made meaningful progress [30]. This suggests a complementary division of labour: an RM can track progress through the task, while a VLM can identify what is happening in each image.

We introduce RM-VLM, an approach that combines these capabilities for RM-guided policy learning from image-based observations. Given a natural-language task description, a large language model (LLM) generates an RM together with the atomic propositions that label its transitions. A VLM then grounds these propositions in observations, acting as the labelling function. The RM retains the history needed to interpret each observation, so the VLM can assess individual images without having to infer task progress from an ordered sequence. Visual grounding is imperfect: an incorrect proposition label can cause an incorrect RM transition and degrade policy learning [35]. RM-VLM therefore maintains an RM state belief, a probability distribution over the agent’s possible positions in the automaton, rather than committing to a single RM state. It defines reward through changes in expected accumulated RM reward under this belief. To supplement the rewards associated with RM transitions, we further extend RM-VLM with Generative Value Learning (GVL), which estimates progress towards the next transition and provides a dense learning signal. The resulting reward can be used with standard RL algorithms, both offline, reusing a single image dataset across tasks, and online, via a classifier distilled from the VLM labels.

We evaluate RM-VLM on three domains spanning non-Markovian grid-world navigation, robotic manipulation, and partially observable 3D object collection. Across these domains, RM-VLM consistently achieves higher task success rates than strong VLM-based reward baselines.

This paper makes the following contributions:

  1. Reward machines from natural language. A novel method for deriving RMs from natural-language task descriptions together with the atomic propositions for labelling RM transitions.

  1. VLMs as labelling functions. Support for RM-guided policy learning from images, using a VLM to ground atomic propositions in image observations, both in the offline setting, where a single VLM-labelled image dataset is reused across tasks, and in the online setting, through a classifier distilled from the VLM labels.

  1. Robustness to imperfect grounding. An RM state belief mechanism for arbitrary RM structures that defines a reward function based on changes in expected accumulated rewards over RM states, to limit the impact of incorrect grounding of RM transition labels.

  1. Dense rewards between RM transitions. A GVL-based zero-shot estimate of progress towards the next RM transition, as a dense learning signal that supplements the RM sparse reward and accelerates policy learning without changing final performance.

Preliminaries

This section reviews the key concepts of reinforcement learning and reward machines. We use the following notation throughout the paper: for a set X\mathcal{X}, Δ(X)\Delta(\mathcal{X}) denotes the probability simplex over X\mathcal{X} and 2X2^{\mathcal{X}} its power set.

Reinforcement learning

Typically, a reinforcement learning process is formulated as a Markov Decision Process (MDP) M=⟨S,A,p,r,γ,μ⟩\mathcal{M} = \langle\mathcal{S}, \mathcal{A}, p, r, \gamma, \mu\rangle, where S\mathcal{S} is a set of states, A\mathcal{A} is a set of actions, p:S×A→Δ(S)p : \mathcal{S} \times\mathcal{A} \to\Delta(\mathcal{S}) is a transition probability function, r:S×A×S→Rr : \mathcal{S} \times\mathcal{A} \times\mathcal{S} \to\mathbb{R} is a reward function, γ∈[0,1)\gamma\in[0, 1) is the discount factor, and μ∈Δ(S)\mu\in\Delta(\mathcal{S}) is the initial state distribution. At time tt, the agent in state st∈Ss_t \in\mathcal{S} takes action at∈Aa_t \in\mathcal{A}, moves to st+1∼p(⋅∣st,at)s_{t+1} \sim p(\cdot\mid s_t, a_t) and receives a reward rt=r(st,at,st+1)r_t = r(s_t, a_t, s_{t+1}). The goal of RL is to learn a policy π\pi that maximises the expected discounted return Eπ[∑t=0∞γtrt]\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^t r_t\right]. The value function Vπ(s)=Eπ[∑t=0∞γtrt∣s0=s]V^\pi(s) = \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^t r_t \mid s_0=s\right] is the expected return from state ss under π\pi. In online RL, the policy is learned from interaction with the environment, and in offline RL [25], from a fixed dataset D\mathcal{D} of trajectories, without any interaction. Sparse rewards make it more challenging for RL algorithms to learn a policy. To accelerate the learning, one can supplement the sparse reward with potential-based shaping [34], which adds γΦ(st)−Φ(st−1)\gamma\Phi(s_t)-\Phi(s_{t-1}) to each reward for a potential function Φ:S→R\Phi: \mathcal{S} \to\mathbb{R}, while leaving the optimal policy unchanged.

Reward machines

Reward machines [RM: 48, 49] represent reward functions as finite-state machines that encode expressive, interpretable specifications of temporal task structure and use the RM states as external memory for non-Markovian tasks. RM transitions are labelled by subsets of P\mathcal{P}, a set of atomic propositions abstracting the environment state space S\mathcal{S}. A labelling function L:S→2P\mathcal{L} : \mathcal{S} \to2^{\mathcal{P}} maps each environment state to the set of propositions that hold in it, with ∣2P∣≪∣S∣\lvert2^{\mathcal{P}} \rvert\ll\lvert\mathcal{S} \rvert. An RM is formally defined as follows.

Definition 1 (Reward machine). A Reward Machine (RM) is a tuple RM=⟨U,P,δu,δr,u0,uA,uR⟩\mathcal{RM} = \langle U, \mathcal{P}, \delta_u, \delta_r, u_0, u_A, u_R\rangle, where UU is a finite set of states, P\mathcal{P} is a finite set of atomic propositions, δu:U×2P→U\delta_u : U \times2^{\mathcal{P}} \to U is the state-transition function, δr:U×U→R\delta_r : U \times U \to\mathbb{R} is the reward-transition function such that δr(u,u′)\delta_r(u,u') is the reward for transitioning from state uu to u′u'. u0∈Uu_0 \in U is the initial state, and uA,uR∈Uu_A, u_R \in U are optional accepting and rejecting states.

We write each transition as an edge ⟨u,u′,φ,r⟩\langle u,u',\varphi,r\rangle, where φ\varphi is a propositional formula over P\mathcal{P} and r=δr(u,u′)r = \delta_r(u,u').

During interaction with the environment, the agent tracks its current RM state alongside its environment state. Formally, a label trace λ=⟨L0,…,Ln⟩\lambda= \langle L_0,\ldots,L_n\rangle induces a unique traversal RM(λ)=⟨u0,…,un+1⟩\mathcal{RM}(\lambda) = \langle u_0,\ldots,u_{n+1}\rangle, where ui+1=δu(ui,Li)u_{i+1} = \delta_u(u_i,L_i) and reward δr(ui,ui+1)\delta_r(u_i,u_{i+1}) is received at each step ii, and the episode ends when the traversal reaches uAu_A or uRu_R. RM states summarise task history, which makes rewards that are non-Markovian over S\mathcal{S} Markovian over S×U\mathcal{S} \times U. We can thus learn a policy π(a∣s,u)\pi(a \mid s,u) over pairs of environment and RM states, with rewards given by the RM [49].

Methodology

We now describe RM-VLM, our approach for solving non-Markovian tasks from natural language descriptions and images without access to the environment’s internal state. RM-VLM addresses three challenges: the automated generation of RM automata from natural language task descriptions, with transitions labelled by atomic propositions, the grounding of proposition labels in images, and the induction of a reward mechanism that provides dense feedback and remains robust to imperfect grounding. We first formalise the problem (§ 3.1) and describe how an LLM generates an RM from a natural-language task description and a VLM grounds its transition label propositions in images (§ 3.2). We then explain how to estimate the RM state under label noise (§ 3.3) and complement this estimate with a dense reward signal to guide the RM-based policy learning (§ 3.4).

Problem formulation

We consider the case where an agent does not have access to the RM of a task, its propositions, or the labelling function. We assume a given dataset D={τj}j=1M\mathcal{D} = \{\tau_j\}_{j=1}^{M} of MM trajectories τj=⟨s0,a0,…,sT⟩\tau_j = \langle s_0, a_0, \ldots, s_T\rangle, collected by a behaviour policy in the environment without rewards or labels. Environment states are observed as images, and tasks are given as natural-language descriptions Ti∈TT_i \in\mathcal{T}. Given a natural-language task description TiT_i, an RM-VLM reward machine is a tuple RM\mathcal{RM} whose atomic propositions in P\mathcal{P} are associated with the task description TiT_i. The propositions and the state transition function of RM\mathcal{RM} are generated by an LLM from the task description augmented with a natural-language description of the environment and its physical constraints as described in § 3.2. The agent tracks its current state, by grounding the label propositions of the RM transitions in the image-based environment state, using the (noisy) labelling function L~:I→2P\tilde{\mathcal{L}}:\mathcal{I}\to2^{\mathcal{P}}, where I\mathcal{I} is the space of image observations, which returns the propositions predicted to hold in the image of an environment state. Figure 1 presents an overview of our RM-VLM approach. An LLM first generates a set of propositions P\mathcal{P} from the natural-language task descriptions, then generates an RM\mathcal{RM} for each TT using these propositions. At each step, a VLM acts as a noisy labelling function L~\tilde{\mathcal{L}}, predicting which propositions are true in the image-based environment state. These labels are used to compute the RM’s state belief and the reward, guiding the agent to learn a policy that maximises the expected return.

Figure 1. The reinforcement learning loop considered in this work. An LLM compiles the language command into reward machines over atomic propositions, and a VLM grounds those propositions in image observations to drive RM transitions. The reward obtained from the LLM-generated RM is used to supervise policy learning.

VLM-grounded reward machines from language

RM-VLM uses a large language model (LLM) to generate the components of an RM that provides an automaton representation of a natural-language task description. Specifically, given a set {Ti}i=1N\{T_i\}_{i=1}^{N} of task descriptions, an LLM is prompted to generate the set P\mathcal{P} of propositions shared across all tasks. Then, for each task TiT_i an associated RMi\mathcal{RM}_i is generated over the alphabet P\mathcal{P}. This is done by prompting the LLM to decompose each TiT_i into a set of independent sub-task RMs, which are then combined together into a single RMi\mathcal{RM}_i [33]. We evaluate the reliability of proposition and RM generation in § 4.2. Given that generating RMs requires only a few calls, a high-quality LLM can be used for this step.

To ground the propositions, we query a VLM for each episode in D\mathcal{D} and each proposition p∈Pp\in\mathcal{P} to identify the timesteps at which pp holds, producing a labelled dataset Dprop\mathcal{D}_{\mathrm{prop}}. Since its predictions can be wrong, we treat the VLM as a noisy labelling function L~\tilde{\mathcal{L}} (§ 3.1).

We describe how Dprop\mathcal{D}_{\mathrm{prop}} is used for offline and online policy learning in § 3.4, and include the prompts used for proposition extraction and RM generation in Appendix H.

Reward machine state belief

In RM-based reinforcement learning, the environment state is typically augmented with the current RM state (§ 2.2). When proposition labels are provided by a perfect labelling function, the current RM state can be tracked deterministically (§ 2.2). With VLM-derived (noisy) labels, however, deterministic state tracking can cause significant degradation in policy performance [35]. To make tracking robust, we replace the deterministic state tracking with an RM state belief, a probability distribution over RM states updated online at each timestep [26, 37]. Prior schemes such as Independent Belief Updating (IBU) [26] re-weight transitions by the predicted labels alone. We additionally exploit two sources of structure. First, given the environment’s physical constraints, described in natural language (Listing 11), the generated RMs encode causal preconditions between propositions, even when they are not explicitly required by the task. For instance, if a drawer must be unlocked before it can be opened, a false positive on “drawer open” cannot trigger a premature transition to the accepting state. Second, a state-dependent prior over true proposition labels couples independently predicted propositions by encoding structural co-occurrence constraints between them. For example, if every object has both a colour and a shape, the prior can encode that a shape proposition never holds without a colour proposition, reducing the impact of isolated misdetections. We formalise the belief update below with the help of a transition–emission matrix.

Definition 2 (Transition–emission matrix). Let L~⊆P\tilde{L}\subseteq\mathcal{P} be a label predicted by a noisy labelling function, L⊆PL\subseteq\mathcal{P} be a label that truly holds, and u,u′∈Uu,u'\in\mathcal{U} a pair of RM states. The transition–emission matrix C∈R∣U∣×∣U∣×2∣P∣×2∣P∣C\in\mathbb{R}^{|\mathcal{U}|\times|\mathcal{U}|\times2^{|\mathcal{P}|}\times2^{|\mathcal{P}|}} is defined as the joint probability of transitioning from state uu to u′u' and observing the noisy label L~\tilde{L}:

C[u,u′,L~]=∑L∈2PP(L∣u)⋅1[δu(u,L)=u′]⋅P(L~∣L),(1)C[u,u',\tilde{L}]=\sum_{L\in2^{\mathcal{P}}}P(L\mid u)\cdot\mathbf{1}[\delta_u(u,L)=u']\cdot P(\tilde{L}\mid L), \tag*{(1)}

where P(L∣u)P(L\mid u) is the state-dependent label prior and P(L~∣L)P(\tilde{L}\mid L) is the probability of observing a noisy label given the ground-truth label, which factorises as P(L~∣L)=∏p∈PP(L~p∣Lp)P(\tilde{L}\mid L)=\prod_{p\in\mathcal{P}}P(\tilde{L}_p\mid L_p) with

P(L~p=1∣Lp)=Lp TPRp+(1−Lp) FPRp,(2)P(\tilde{L}_p=1\mid L_p)=L_p\,\mathrm{TPR}_p+(1-L_p)\,\mathrm{FPR}_p, \tag*{(2)}

where L~p\tilde{L}_p (resp. LpL_p) refers to proposition pp in L~\tilde{L} (resp. in LL), P(L~p=0∣Lp)=1−P(L~p=1∣Lp)P(\tilde{L}_p=0\mid L_p)=1-P(\tilde{L}_p=1\mid L_p), and TPRp\mathrm{TPR}_p and FPRp\mathrm{FPR}_p are the true and false positive rates of the noisy labelling function for proposition pp.

In practice, we estimate TPRp\mathrm{TPR}_p and FPRp\mathrm{FPR}_p by comparing the predicted labels with ground-truth labels on a set of trajectories from D\mathcal{D}. We also generate the prior P(L∣u)P(L\mid u) with the LLM from the environment description and the generated RM (see Appendix § 9).

Definition 3 (RM state belief). The RM state belief u~t∈Δ(U)\tilde{\mathbf{u}}_t\in\Delta(\mathcal{U}) is a probability distribution over RM states at timestep tt, defined as:

u^t[u′]={1[u′=u0]if t=0,∑uu~t−1[u]⋅C[u,u′,L~t−1]if t>0,(3)\hat{\mathbf{u}}_t[u']=\begin{cases} \mathbf{1}[u'=u_0] & \text{if }t=0,\\ \sum_u\tilde{\mathbf{u}}_{t-1}[u]\cdot C[u,u',\tilde{L}_{t-1}] & \text{if }t>0, \end{cases} \tag*{(3)}
u~t=u^t∑uu^t[u′],\tilde{\mathbf{u}}_t=\frac{\hat{\mathbf{u}}_t}{\sum_u\hat{\mathbf{u}}_t[u']},

where u0u_0 is the initial RM state, L~t−1\tilde{L}_{t-1} is the noisy label of the image for the environment state st−1s_{t-1}, and CC is the transition–emission matrix.

An illustrative example is given in Appendix § 11.

Reward and policy learning

We present a novel way of computing RM rewards based on the notion of expected accumulated reward. First, let Gt=∑k=1tδr(uk−1,uk)G_t=\sum_{k=1}^{t}\delta_r(u_{k-1},u_k) denote the ground-truth reward the RM has emitted up to time tt. Also, let αt[u]=E[Gt∣ut=u,L~0:t−1]\alpha_t[u]=\mathbb{E}[G_t\mid u_t=u,\tilde{L}_{0:t-1}] be its expectation given the observed label history. We initialise α0=0\alpha_0=0 and recursively compute α\alpha for each RM state u′u' as:

αt[u′]=∑uu~t−1[u]C[u,u′,L~t−1](αt−1[u]+δr(u,u′))∑uu~t−1[u]C[u,u′,L~t−1],(4)\alpha_t[u']=\frac{\sum_u\tilde{u}_{t-1}[u]C[u,u',\tilde{L}_{t-1}]\left(\alpha_{t-1}[u]+\delta_r(u,u')\right)}{\sum_u\tilde{u}_{t-1}[u]C[u,u',\tilde{L}_{t-1}]}, \tag*{(4)}

where CC is the transition-emission matrix of RM. The task reward δr(u~t−1,u~t)\delta_r(\tilde{u}_{t-1},\tilde{u}_t) at time tt is defined as:

δr(u~t−1,u~t)=(u~t)Tαt−(u~t−1)Tαt−1.(5)\delta_r(\tilde{u}_{t-1},\tilde{u}_t)=(\tilde{u}_t)^\mathsf{T}\alpha_t-(\tilde{u}_{t-1})^\mathsf{T}\alpha_{t-1}. \tag*{(5)}

This task reward reduces exactly to the RM reward when the RM state belief is one-hot (Appendix § 10).

We augment the task reward with a dense reward signal term rtdenser_t^{\mathrm{dense}}, which builds upon two existing shaping schemes: rewarding progress across RM transitions [6] and towards them [27]. Both are potential-based shaping terms (§ 2.1) built from a value function over RM states. We first compute the value of each RM state by value iteration over the RM automaton alone:

vRM(u)=max⁡⟨u,u′,φ,r⟩γRM(r+vRM(u′)).(6)v_{\mathrm{RM}}(u)=\max_{\langle u,u',\varphi,r\rangle}\gamma_{\mathrm{RM}}\left(r+v_{\mathrm{RM}}(u')\right). \tag*{(6)}

where the maximum is taken over all outgoing transitions ⟨u,u′,φ,r⟩\langle u,u',\varphi,r\rangle of uu, terminal states are fixed to vRM(u)=0v_{\mathrm{RM}}(u)=0, and γRM\gamma_{\mathrm{RM}} is a discount factor over RM transitions. As the value iteration algorithm considers RM transitions to be the singular actions, it should be run with γRM<γ\gamma_{\mathrm{RM}}<\gamma as it takes many low-level steps to achieve a transition.

We then extend this value function to include also the environment states (V^RM:S×U→R\hat{V}_{\mathrm{RM}}:S\times U\to\mathbb{R}), thus estimating how close the agent is to triggering an RM transition. This estimation is computed as follows. GVL [30] is used to zero-shot estimate the value of reaching each atomic proposition V^p(s)\hat{V}_{p}(s) and its negation V^¬p(s)\hat{V}_{\neg p}(s) (Appendix H.§ 5). These estimates are composed according to the logical structure of φ\varphi, as in Li et al. [27]:

V^φ1∧φ2(s)=min⁡(V^φ1(s),V^φ2(s)),(7)\hat{V}_{\varphi_1\land\varphi_2}(s)=\min\left(\hat{V}_{\varphi_1}(s),\hat{V}_{\varphi_2}(s)\right), \tag*{(7)}
V^φ1∨φ2(s)=max⁡(V^φ1(s),V^φ2(s)).(8)\hat{V}_{\varphi_1\lor\varphi_2}(s)=\max\left(\hat{V}_{\varphi_1}(s),\hat{V}_{\varphi_2}(s)\right). \tag*{(8)}

By design, V^φ(s)∈[0,1]\hat{V}_{\varphi}(s)\in[0,1] for any formula φ\varphi, as it is the value of reaching a state that satisfies φ\varphi under a sparse reward of 1. The full value estimate V^RM(s,u)\hat{V}_{\mathrm{RM}}(s,u), RM-VLM+GVL is given by combining V^φ(s)\hat{V}_{\varphi}(s) with the RM state values vRM(u)v_{\mathrm{RM}}(u) and vRM(u′)v_{\mathrm{RM}}(u') as follows:

V^RM(s,u)=max⁡⟨u,u′,φ,r⟩[(1−V^φ(s))⋅vRM(u)+V^φ(s)⋅(r+γ⋅vRM(u′))].(9)\hat{V}_{\mathrm{RM}}(s,u)=\max_{\langle u,u',\varphi,r\rangle}\left[(1-\hat{V}_{\varphi}(s))\cdot v_{\mathrm{RM}}(u)+\hat{V}_{\varphi}(s)\cdot\left(r+\gamma\cdot v_{\mathrm{RM}}(u')\right)\right]. \tag*{(9)}

Finally, V^RM\hat{V}_{\mathrm{RM}} is applied to the RM state belief by taking the expectation under the belief:

V^RM(s,u~)=∑u∈Uu~[u]V^RM(s,u).(10)\hat{V}_{\mathrm{RM}}(s,\tilde{u})=\sum_{u\in U}\tilde{u}[u]\hat{V}_{\mathrm{RM}}(s,u). \tag*{(10)}

The dense reward signal term is then given by:

rtdense=γV^RM(st,u~t)−V^RM(st−1,u~t−1).(11)r_t^{\mathrm{dense}}=\gamma\hat{V}_{\mathrm{RM}}(s_t,\tilde{u}_t)-\hat{V}_{\mathrm{RM}}(s_{t-1},\tilde{u}_{t-1}). \tag*{(11)}

The total reward used for policy learning is given by the value

rt=δr(u~t−1,u~t)+rtdense.r_t=\delta_r(\tilde{u}_{t-1},\tilde{u}_t)+r_t^{\mathrm{dense}}.

Policy learning. The tasks we consider can have non-Markovian rewards. We therefore augment the environment state with the RM state belief from Definition 3 and use rtr_t as the reward signal.

We consider both offline and online RL settings. In the offline setting, the RM state beliefs and rewards can be computed from labelled offline trajectories without further environment interaction. We use the same dataset to learn policies for different tasks by augmenting it with different self-generated rewards. In the online setting, since querying the VLM at every step is too costly, we distil the VLM labels into a neural network classifier trained to label states, and use it during online RL.

Experiments

To evaluate the effectiveness of our methods, we design experiments around three research questions:

RQ1 — Effectiveness. Can RM-VLM solve non-Markovian tasks without a pre-engineered labelling function and task-specific RM?

RQ2 — Grounding decomposition with RMs. Does decomposing a task into an RM yield better reward and faster learning than using the VLM directly?

RQ3 — Robustness to grounding noise. How do VLM labelling errors impact policy learning?

We describe the experimental setup in § 4.1, evaluate the LLM-based generation of RM in § 4.2, present the offline RL results in § 4.3 and the online RL results in § 4.4, and present an ablation study of our design choices in § 4.5.

Experimental setup

We evaluate RM-VLM on three different domains: GeoGrid [27], OGBench-Scene [38], and MiniWorld-Pickup [9]. GeoGrid is an 8 × 8 grid world where the agent visits specified objects among three triangles and three circles coloured red, green, or blue, moving along four cardinal directions. Its simple visual setting provides a clean setting for evaluating the generated reward. OGBench-Scene is a continuous-control robotic manipulation domain that requires the agent to complete manipulation tasks involving a drawer, a window, two lock buttons, and a cube. Its rendered robot scenes are substantially harder for the VLM to label than GeoGrid’s symbolic grids, so it tests robustness of RM-VLM to inaccurate VLM labels and long-horizon control from images. MiniWorld-Pickup is a goal-oriented 3D environment requiring the agent to collect specified objects among three balls and three boxes coloured red, green, or blue. Its first-person 3D observations test performance under partial observability. Table 1 lists the RM tasks we consider in each of these domains, requiring different reward structures: fixed sequence of sub-goals, repeated objectives, ordering constraints between sub-goals, and safety constraints. For each task, policy learning uses expert-written reference propositions, RMs and label priors. Section 4.2 shows the LLM generation of these from the task descriptions, whereas further details including VLM labelling accuracies, and descriptions of offline datasets are included in Appendix A.

EnvTaskLanguage command
GeoGridSequenceGo to a red triangle, then a green triangle, then a blue triangle.
GeoGridLoopRepeatedly go to a red triangle, then a green triangle, then a blue triangle.
GeoGridLogicGo to all six objects, but always go to red objects before blue objects, and blue objects before green objects.
GeoGridSafetyGo to a red object, then a blue object, then a green object, but always avoid triangles.
OGBench-SceneOpenOpen both the drawer and the window.
OGBench-SceneClose+LockClose the open drawer and window, then re-engage both locks.
OGBench-SceneCube-in-DrawerPlace the cube into the drawer.
OGBench-SceneCube+WindowPlace the cube into the drawer and open the window.
MiniWorld-PickupSequencePick up the red box, then the green box, then the blue box.
MiniWorld-PickupLogicPick up all six objects, but always pick up red objects before blue objects, and blue objects before green objects.
MiniWorld-PickupSafetyPick up the red ball, then the blue ball, then the green ball, but never pick up a box.
MiniWorld-PickupAlternationPick up a ball, then a box, then another ball, in that order.

Table 1. Compositional language tasks evaluated in each environment.

Baselines. For offline RL, we compare RM-VLM against three baselines that do not use reward machines. Behaviour Cloning (BC) [41] imitates the behaviour policy used to collect the dataset. Generative Value Learning (GVL) [30] uses a VLM to estimate task progress from shuffled frames and uses this estimate as a reward. VLM Success Detection (VLM-SD) [4] uses a VLM to judge whether the task has been completed and assigns a sparse success reward. Both VLM baselines receive the full language command from Table 1 as task description (prompts in Appendix H), whereas our methods query the VLM only about individual sub-goals. Since the baselines have no RM state to track sub-goal completion, they use a recurrent policy on GeoGrid and MiniWorld-Pickup, where completed sub-goals are not visible in the observation. In the online RL setting, we compare against Ground-Compose-Reinforce (GCR) [27], which uses reward machines but assumes that Dprop\mathcal{D}_{\mathrm{prop}} is labelled by an oracle, therefore tracking RM state deterministically. GCR-High-level RS provides reward on transitions between RM states, whereas GCR also rewards progress towards the next RM transition, estimated by offline RL learned value functions on Dprop\mathcal{D}_{\mathrm{prop}}.

We use Gemma-3-4B [16] as both LLM and VLM. In the offline setting, we train policies with Implicit Q-Learning [IQL; 21] and, on OGBench-Scene, also with Flow Q-Learning [FQL; 39], specific for continuous action spaces. In the online setting, we use Proximal Policy Optimization [PPO; 44]. RM-VLM trains a feed-forward policy on image observations extended with RM state belief. We report two variants: RM-VLM, which uses the task reward and RM-based shaping, and RM-VLM+GVL, which additionally uses the GVL progress estimate (§ 3.4). Full training details are given in Appendix F.

Evaluating Proposition and RM generation

Errors in the generation of propositions or RMs would affect policy learning (RQ1). We therefore evaluate each step against the reference propositions, RMs and label priors, over 10 runs per task. Firstly, the LLM generates the propositions from all task descriptions of an environment; results show that in every run, the LLM captures all reference propositions the tasks require. The LLM then generates an RM over the generated propositions. Results show that the generated RM is trace-equivalent to the reference RM in 114/120 runs. The remaining failures are malformed RMs. Given the reference propositions instead, it does so in every run (120/120), in line with prior work [7, 27]. Given the reference RMs, the generated label prior matches the reference prior in 119/120 runs, and the remaining error comes from the LLM’s failure to follow the defined structure. We report the full results in Appendix B.

Compositional-task evaluation

Table 2 reports task success of RM-VLM and our baselines with IQL on GeoGrid, OGBench-Scene, and MiniWorld-Pickup. In line with Jackson et al. [20], we select the best performing checkpoint online with a fixed budget and report its performance on separate held-out episodes (Appendix F).

EnvTaskBCGVLVLM-SDRM-VLMRM-VLM+GVL
GeoGridSequence0.22±0.010.22 \pm0.010.31±0.090.31 \pm0.090.14±0.020.14 \pm0.021.00±0.001.00 \pm0.001.00±0.001.00 \pm0.00
Loop†0.34±0.010.34 \pm0.010.21±0.060.21 \pm0.060.09±0.020.09 \pm0.021.00±0.001.00 \pm0.001.00±0.001.00 \pm0.00
Logic0.00±0.000.00 \pm0.000.00±0.010.00 \pm0.010.00±0.000.00 \pm0.000.98±0.010.98 \pm0.010.97±0.010.97 \pm0.01
Safety0.10±0.010.10 \pm0.010.09±0.030.09 \pm0.030.15±0.020.15 \pm0.020.95±0.010.95 \pm0.010.95±0.010.95 \pm0.01
OGBench-SceneOpen0.60±0.050.60 \pm0.050.63±0.150.63 \pm0.150.73±0.150.73 \pm0.150.98±0.020.98 \pm0.020.97±0.030.97 \pm0.03
Close+Lock0.09±0.030.09 \pm0.030.10±0.040.10 \pm0.040.09±0.070.09 \pm0.070.53±0.180.53 \pm0.180.58±0.200.58 \pm0.20
Cube-in-Drawer0.04±0.020.04 \pm0.020.06±0.040.06 \pm0.040.02±0.030.02 \pm0.030.87±0.100.87 \pm0.100.80±0.100.80 \pm0.10
Cube+Window0.01±0.010.01 \pm0.010.02±0.020.02 \pm0.020.00±0.000.00 \pm0.000.73±0.040.73 \pm0.040.65±0.110.65 \pm0.11
MiniWorld-PickupSequence0.15±0.030.15 \pm0.030.21±0.040.21 \pm0.040.20±0.060.20 \pm0.060.74±0.080.74 \pm0.080.67±0.050.67 \pm0.05
Logic0.25±0.050.25 \pm0.050.15±0.030.15 \pm0.030.25±0.020.25 \pm0.020.74±0.070.74 \pm0.070.72±0.060.72 \pm0.06
Safety0.16±0.020.16 \pm0.020.18±0.040.18 \pm0.040.18±0.020.18 \pm0.020.56±0.030.56 \pm0.030.50±0.050.50 \pm0.05
Alternation0.37±0.040.37 \pm0.040.38±0.060.38 \pm0.060.44±0.060.44 \pm0.060.93±0.020.93 \pm0.020.93±0.030.93 \pm0.03

Table 2. Task success rates with IQL [21] (mean ±\pm std over 5 seeds). Values within 95% of the best per row in bold.

Overall, RM-VLM solves the tasks effectively across the three domains (RQ1). It reaches perfect or near-perfect success rate on all GeoGrid tasks, and solves three of four OGBench-Scene tasks with success rate above 0.65. RM-VLM outperforms all non-RM baselines on every task across the three environments (RQ2), suggesting that grounding atomic propositions and composing them with an RM is more effective than asking the VLM to judge task progress or success directly. Finally, incorporating GVL does not have a substantial impact on the final performance of the agent. Repeating

the OGBench-Scene evaluation with FQL (Appendix § 12) shows that the gains are not specific to IQL.

Online RL on GeoGrid

In the online setting, we train PPO [44] from scratch on GeoGrid with RM-VLM and RM-VLM+GVL, and compare them against GCR-High-level RS and GCR. All four methods distil a proposition classifier from the same fixed dataset and use it as the labelling function during policy training. The GCR variants distil it from ground-truth labels, and GCR additionally learns its value functions with offline RL on the same dataset. Our variants distil it from VLM labels, and RM-VLM+GVL additionally distils its progress model from GVL predictions.

Figure 2 shows that RM-VLM matches GCR-High-level RS and RM-VLM+GVL matches GCR on every task, showing that replacing ground-truth labels and learned value functions with VLM outputs incurs no loss in final performance on GeoGrid.

Figure 2. Online RL on GeoGrid. Ground-truth success rate during PPO training (mean ± std over 5 seeds).

Ablations

We present ablation study on RM state tracking, reward signal and label quality, and analyse why RM-based decomposition helps.

RM state belief and labelling errors

To analyse the effect of RM-state tracking under VLM labels, Table 3 compares three variants:

TaskNaiveIBUBeliefOracle
GeoGrid
Sequence1.00±0.011.00 \pm0.011.00±0.001.00 \pm0.001.00±0.001.00 \pm0.001.00±0.001.00 \pm0.00
Loop†1.00±0.001.00 \pm0.000.98±0.010.98 \pm0.011.00±0.001.00 \pm0.001.00±0.001.00 \pm0.00
Logic0.99±0.000.99 \pm0.000.97±0.020.97 \pm0.020.98±0.010.98 \pm0.010.99±0.010.99 \pm0.01
Safety0.95±0.010.95 \pm0.010.95±0.000.95 \pm0.000.95±0.010.95 \pm0.010.95±0.010.95 \pm0.01
OGBench-Scene
Open0.59±0.050.59 \pm0.050.49±0.170.49 \pm0.170.98±0.020.98 \pm0.020.98±0.010.98 \pm0.01
Close+Lock0.16±0.080.16 \pm0.080.13±0.030.13 \pm0.030.53±0.180.53 \pm0.180.97±0.020.97 \pm0.02
Cube-in-Drawer0.84±0.020.84 \pm0.020.84±0.040.84 \pm0.040.87±0.100.87 \pm0.100.86±0.060.86 \pm0.06
Cube+Window0.53±0.120.53 \pm0.120.44±0.060.44 \pm0.060.73±0.040.73 \pm0.040.72±0.080.72 \pm0.08
MiniWorld-Pickup
Sequence0.77±0.060.77 \pm0.060.77±0.040.77 \pm0.040.74±0.080.74 \pm0.080.75±0.030.75 \pm0.03
Logic0.71±0.030.71 \pm0.030.73±0.030.73 \pm0.030.74±0.070.74 \pm0.070.74±0.050.74 \pm0.05
Safety0.55±0.040.55 \pm0.040.53±0.040.53 \pm0.040.56±0.030.56 \pm0.030.58±0.070.58 \pm0.07
Alternation0.93±0.020.93 \pm0.020.93±0.040.93 \pm0.040.93±0.030.93 \pm0.030.93±0.020.93 \pm0.02

Table 3. Belief ablation: mean ±\pm standard deviation of task success over 5 seeds. Impact of labelling errors: RM-VLM with VLM labels vs. ground-truth labels (Oracle). Values within 95% of the best per row in bold.

  • *Naive: update the RM state directly from VLM labels, treating them as correct [26].

  • *Independent Belief Updating (IBU): maintain a belief over RM states using the predicted labels, as in Li et al. [26] and Prob-IRM [37], but without state-dependent structural prior.

  • *Belief: use the full belief update, including the RM structure and structural prior.

As an upper bound, it also reports an Oracle variant of RM-VLM that uses the same RM and reward construction but replaces VLM labels with ground-truth proposition labels, which measures the cost of imperfect VLM grounding.

The three approaches, unsurprisingly, achieve similar success rates in GeoGrid and MiniWorld-Pickup where the labels are reliable. However, in OGBench-Scene, the Belief shows its benefit, outperforming the other two variants in three out of four tasks and matching them on Cube-in-Drawer. Under synthetic label noise on GeoGrid (Appendix § 14), Belief also degrades most gracefully, retaining 0.79 and 0.85 success on Logic and Safety at a 2% flip rate where Naive drops to 0.55 and 0.70. On GeoGrid and MiniWorld-Pickup, VLM labels are accurate enough that Belief matches the Oracle on every task. On OGBench-Scene, it matches the Oracle on every task except Close+Lock (0.53 vs. 0.97), the only task that requires detecting a closed drawer and window, which the VLM labels least reliably (RQ3).

Reward signal

We next ablate the components of the RM-based reward on GeoGrid, where VLM proposition labels are highly accurate. We compare four variants:

  • sparse reward: use only the sparse reward from the RM transition function δr\delta_r.

  • RM-based shaping: adds RM-based shaping obtained by value iteration described in Equation (6).

  • RM+GVL-based shaping: additionally predicts progress towards reaching proposition with GVL, combining its predictions into a value estimate described in Equation (9).

  • RM+GVL(GT)-based shaping: same as above but replacing the GVL-progress prediction with the ground truth one.

Figure 3 shows the resulting convergence curves.

Figure 3. GeoGrid convergence curves for the reward-signal variants (mean ±\pm std over 5 seeds).

RM-based shaping improves convergence over the sparse reward, showing that RM structure can provide useful dense guidance. RM+GVL-based shaping can further accelerate learning at early stages when the progress signal is accurate, but the additional VLM noise it introduces can hurt final performance, as seen on Sequence (RQ3). On Logic and Safety, we do not see the same benefits. The issue arises because the use of min [27 Appendix A.4] overestimates progress towards the next transition, which in turn can occasionally generate a misleading reward signal.

Why does RM-based decomposition help?

GeoGrid, despite being a simple environment, poses significant challenges to GVL (RQ2). Focusing on value function estimation, we examine two capabilities that RMs provide, task decomposition and memory. We design tasks such that only these capabilities are individually evaluated. We compare the value function used by the RM-VLM+GVL densification term (§ 3.4) against the one produced by GVL, measuring Value-Order Correlation (VOC) [30], the rank correlation between the predicted values and the timestep order along an optimal trajectory, for simple GeoGrid tasks.

Task decomposition. A VLM answering a disjunctive query must jointly reason about all alternatives simultaneously, which could degrade progress estimation. We compare GVL with a disjunctive prompt against decomposing the task into atomic sub-goal queries and taking their per-frame maximum, following fuzzy-logic disjunction [59]. For the disjunctive task “reach a red object OR a triangle”, we collect 200 optimal episodes (100 per sub-goal) and compute progress with both approaches. Table 4 reports the results.

Per-atom queries perform on par with the disjunctive prompt, so decomposing the query does not lose accuracy. The RM decomposes tasks into such atomic queries by construction (§ 3.4).

ConditionVOC (mean ± SE)
Decomposition (“reach red OR triangle”)
Disjunctive prompt+0.931 ± 0.010
Per-atom queries (max)+0.944 ± 0.010
Memory (“reach triangle, then circle”)
Standard env+0.541 ± 0.028
Yellow-marker env+0.878 ± 0.006
VLM sub-goal split+0.986 ± 0.002

Table 4. VOC of GVL under conditions that isolate task decomposition and memory. Higher is better; a perfect value estimator achieves +1.0.

Memory. Sequential tasks require tracking sub-goal completion across time, but GVL presents frames in random order, so the VLM must rely solely on the observation to infer this history. We compare GVL against two alternatives on the task “reach a triangle, then reach a circle”. The first applies GVL on a modified environment that renders visited objects in yellow, encoding completion history directly into the observation. The second uses VLM proposition labels to detect the sub-goal boundary and applies GVL independently on each segment. We collect 200 optimal episodes and compute progress with each approach. The yellow-marker environment achieves a 62% relative improvement over GVL via an environment-level memory cue, while the VLM sub-goal split achieves 82% by explicitly tracking sub-goal completion. The yellow-marker fix requires a modified environment unavailable at test time; the RM’s belief filter (§ 3.3) provides this memory without environment modifications.

Related Work

VLM/LLM-based reward specification. VLMs can judge task success zero-shot [12], which has motivated their use as a source of reward for RL. Early work defined rewards from the similarity between vision-language embeddings of the observation and the goal [4, 43, 45], whereas later work defines them from pairwise preferences over image pairs [54], fine-tunes a VLM into a dense reward model [23], supplies memory through test-time adaptation [61], or tracks sub-goal completion with a Bayesian filter [60]. GVL [30] uses a VLM as an in-context value learner that provides dense per-timestep rewards. Venkataraman et al. [52] label a dataset for offline RL with a reward model trained on VLM preferences, whereas we derive rewards from reward machines whose propositions are labelled zero-shot by a pretrained VLM. Rather than using VLM outputs directly, a complementary approach generates reward code with LLMs, as dense reward functions over the environment state [32, 56], as reward machines with executable labelling functions [7], or as sub-goals with executable reward functions [53]. Alternatively, Hung et al. [18], Wang et al. [55] combine LLM-based task decomposition with learned grounding modules. RM-VLM uses an LLM to decompose a task into sub-task reward machines, a VLM to ground their atomic propositions, and RM states to provide memory for reward prediction.

Formal languages for RL. Formal languages such as LTL [40], whose specifications can be compiled into reward machines [6], have been widely adopted in RL for specifying temporally extended, non-Markovian reward functions. A growing body of work trains policies that generalise zero-shot to unseen temporal logic formulas [1, 10, 15, 19, 22, 24, 28, 42, 51, 57], whereas our approach requires offline RL for each new task but does not assume a ground-truth labelling function. The methods above assume a perfect labelling function; a separate line of work relaxes this assumption. Ground-Compose-Reinforce [27] assumes a hand-designed set of propositions and learns the labelling function from manually labelled trajectories, treating its predictions as correct when tracking the RM state. We instead ground LLM-derived propositions with a pre-trained VLM and track a belief over RM states to absorb the resulting label noise. Like RM-VLM, Yang et al. [58] construct an automaton with an LLM and evaluate its propositions from images with an open-vocabulary detector, but use the automaton directly as a controller instead of learning a policy. Li et al. [26] and Parac et al. [37] mitigate the problem of noisy labelling functions by maintaining a belief over RM states, a formulation we directly build upon, but either consider only a simplified δr\delta_r structure [37] or do not specify how reward is assigned under an uncertain RM state [26], while Umili et al. [50] handle noise by representing the RM as a probabilistic finite automaton. Concurrently, Panaccι et al. [36] extend the approach of Umili et al. [50] to arbitrary LTL tasks, achieving zero-shot task composition on simple 2D environments. Like Sun and Wu [46], we combine reward machines with offline RL, but where they filter transitions to curate a cleaner dataset, we train on the full dataset with noisy VLM labels. Gu et al. [17] shape rewards for offline RL with an LLM-generated subgoal order, but the LLM directly provides a mapping from low-dimensional states to subgoals, without using an automaton or accounting for errors in this mapping.

From natural language to formal specifications. LLMs can translate natural-language instructions into temporal logic [5, 8, 11, 29] and reward machines [2, 7, 27]. These methods translate one specification at a time, over propositions given in advance or, for Castanyer et al. [7], chosen per task. We instead derive the propositions jointly from all task descriptions, so that they are shared across tasks.

Conclusion

We have presented RM-VLM, a method for solving compositional tasks, including non-Markovian tasks, without a manually engineered labelling function. It uses an LLM to translate a natural-language task into an RM, a VLM to ground its atomic propositions in image observations, and a belief over RM states to mitigate labelling errors, all without fine-tuning the VLM. Across three different domains, RM-VLM is shown to outperform VLM-based rewards that judge the full task, demonstrating that composing grounded propositions with an RM is more effective than querying the VLM about the task directly.

Limitations. VLM labelling accuracy varies significantly across propositions, and the method works best when propositions correspond to visually unambiguous states. The RM state belief requires the VLM’s per-proposition true- and false-positive rates, which we estimate from a small set of labelled trajectories. Finally, RM expressiveness is limited to regular-language tasks and cannot capture properties such as counting.

Future work. In future work, we aim to extend the RM-VLM approach to hierarchical reward machines [14], which are effective in solving longer-horizon tasks. We plan also to learn a single policy that generalises across task specifications, considering ideas from instruction following with temporal logic [19, 51].

References

Environment Descriptions

GeoGrid

GeoGrid is an 8×88 \times8 grid world with six objects, a circle and a triangle in each of red, green and blue. At the start of each episode, the objects are placed according to one of 10 fixed layouts and the agent starts in a random empty cell. The agent moves in the four cardinal directions. Figure 4 shows one of the layouts.

GeoGrid with one of the fixed layouts

Figure 4. GeoGrid with one of the fixed layouts, as shown to the VLM. The orange cell is the agent.

Propositions. The ground-truth set of propositions is given below. Several propositions can hold at once, e.g. r and c when the agent stands on the red circle.

PropositionMeaning
rAgent stands on a red object (any shape)
gAgent stands on a green object (any shape)
bAgent stands on a blue object (any shape)
cAgent stands on a circle (any colour)
tAgent stands on a triangle (any colour)

Table 4 (PDF p. 11).

Offline dataset. We collected 1,000 episodes (46,890 transitions) of 336×336336 \times336 images, which we use both for offline RL and for training the distilled label classifier. Each episode follows one of the task RMs, chosen uniformly at random. With probability 0.7, the behaviour policy takes a step along the shortest obstacle-free path to the closest object that advances the RM, and otherwise it acts randomly.

VLM labelling. We label every frame (stride 1) with Gemma-4-31B-it, asking about one proposition at a time with the prompt in Listing 13. Each query includes two reference frames, one where the proposition holds and one where it does not. Every prompt is prefixed with the same scene description (Listing 1), and Listing 2 lists the proposition questions.

Scene: An 8x8 grid world rendered as a top-down image.
- The grid has black grid lines on a white background.
- Exactly one cell is highlighted solid ORANGE -- this is the
  agent's position.
- Some cells contain objects: a coloured shape drawn centred in
  the cell.
- Shapes are CIRCLE or TRIANGLE.
- Colours are RED, GREEN, or BLUE.
- There are up to six objects per layout -- one for each (colour,
  shape) pair.
- Cells that contain neither the agent nor an object are plain
  white.

The agent is 'on' an object when the orange highlight occupies the same cell as that object (the coloured shape is drawn on top of the orange background).

Listing 1: GeoGrid scene description

r: Is the orange agent cell currently on a RED object (i.e. a red
   circle or red triangle drawn on top of the orange cell)?
c: Is the orange agent cell currently on a CIRCLE (of any colour
   -- red, green, or blue)?

Listing 2: GeoGrid proposition questions (g and b are analogous to r, and t to c)

We distil these labels into a CNN that predicts the propositions from the frame resized to 84×8484 \times84, which is the classifier used at evaluation. Table 5 reports the accuracy of both the VLM and the distilled labels.

rgbctOverall
% Positive5.55.15.14.311.46.3
VLM
Accuracy99.699.799.799.499.599.6
Precision94.095.194.788.596.794.5
Recall98.998.799.198.798.898.9
Distilled
Accuracy100.0100.0100.0100.0100.0100.0
Precision100.099.8100.0100.0100.0100.0
Recall100.0100.0100.0100.0100.0100.0

Table 5. Per-proposition label accuracy (%) on GeoGrid. VLM: Gemma-4-31B-it labels. Distilled: the CNN distilled from them, used at evaluation. % Positive is the proportion of frames where each proposition holds, and Overall is micro-averaged over propositions.

OGBench-Scene

OGBench-Scene [38] is a robotic manipulation environment. It contains a drawer, a window, two lock buttons and a solid red cube. Its visualisation can be seen in Figure 5.

OGBench-Scene as shown to the VLM

Figure 5. OGBench-Scene as shown to the VLM (336×336336 \times336 frame, robot arm drawn transparent). Red handles and buttons indicate that the drawer and window are locked.

Propositions. The ground-truth set of propositions is given below.

PropositionMeaning
duDrawer is unlocked (its handle is not red; toggled by the left button)
wuWindow is unlocked (its handle is not red; toggled by the right button)
doDrawer is open
woWindow is fully open
ciCube is inside the drawer

Offline dataset. We use OGBench’s visual-scene-play dataset (1,000 trajectories, 10610^{6} transitions). We re-rendered its images at 336 × 336 from the stored simulator states.

VLM labelling. We label the frames with Gemma-4-31B-it in the same way as in GeoGrid, except that the VLM sees every 10th frame and we interpolate the labels in between. Every prompt is prefixed with the same scene description (Listing 3).

Scene layout:
- LEFT side: a drawer (white box with a sliding front panel).
- RIGHT side: a window (a sliding panel in a frame).
- BOTTOM CENTER: two lock buttons on pedestals. The LEFT button
  corresponds to the drawer lock; the RIGHT button corresponds
  to the window lock. A button is RED when the corresponding
  object is LOCKED, and WHITE/GREY when it is UNLOCKED.
- The window also has a handle bar on its frame that turns RED
  when locked.
- A solid RED cube is somewhere in the scene -- on the floor or
  inside the drawer. If the cube is not visible, it is inside
  the drawer. - When the drawer is CLOSED, the front panel and
  handle sit flush against the box.
- When the drawer is OPEN, the panel is displaced to one side,
  revealing a gap and the interior cavity.
- When the window is CLOSED, the handle bar sits at the top of
  the window frame, far from the buttons.
- When the window is OPEN, the handle has slid down so the handle
  bar is near the buttons.
- A transparent robot arm with a purple gripper which performs
  the manipulation.

Listing 3: OGBench-Scene scene description

Listing 4 lists the proposition questions.

du: Is the drawer unlocked? (The drawer is locked if its handle
    is red; it is unlocked if the handle is not red. The drawer
    gets unlocked/locked by pressing the left button on the
    table.)
do: Is the drawer open?
wo: Is the window fully open? (A partially open window does not
    count -- the window must be fully open with the handle slid
    all the way down near the buttons.)
ci: Is the cube inside the drawer?

Listing 4: OGBench-Scene proposition questions (wu is analogous to du)

We distil these labels into a CNN that predicts the propositions from the frame resized to 64 × 64, which is the classifier used at evaluation. Table 6 reports the accuracy of both the VLM and the distilled labels.

MiniWorld-Pickup

MiniWorld [9] is a library of configurable, egocentric and partially observable 3D environments. MiniWorld-Pickup, which we build

duwudowociOverall
% Positive51.854.531.936.117.038.3
VLM Accuracy98.397.074.659.099.385.7
Precision98.798.456.342.897.878.9
Recall98.096.290.140.398.485.3
Distilled Accuracy98.998.381.758.399.287.3
Precision99.599.164.241.497.281.5
Recall98.297.796.537.698.086.3

Table 6. Per-proposition label accuracy (%) on OGBench-Scene. VLM: Gemma-4-31B-it labels. Distilled: the CNN distilled from them, used at evaluation. % Positive is the proportion of frames where each proposition holds, and Overall is micro-averaged over propositions.

with it, contains a walled room with six objects (red box, red ball, blue box, blue ball, green box, green ball), placed according to one of 10 fixed layouts. The agent can turn left or right, move forward or backward, or pick up an object in front of it. The objects are consumed on pickup and no longer appear in the environment. Figure 6 shows the agent’s view.

MiniWorld-Pickup from the agent’s egocentric view

Figure 6. MiniWorld-Pickup from the agent’s egocentric view, as shown to the VLM (336 × 336 frame).

Propositions. Unlike in the other two environments, the propositions here are pickup events rather than properties of the state. A proposition is true only on the step where the agent picks up a matching object. Several can be true at once, e.g. picking up a red box makes both r and x true.

PropositionMeaning
rA red object (box or ball) was just picked up
gA green object (box or ball) was just picked up
bA blue object (box or ball) was just picked up
xA box (any colour) was just picked up
oA ball (any colour) was just picked up

Offline dataset. For offline RL and for training the distilled event detector, we collected a multi-task dataset with 5,000 episodes (728,355 transitions) where the state is a 336 × 336 egocentric image, with a horizon of 800 steps. Each episode follows one of the task RMs, with the sequence, safety, logic and alternation tasks drawn in a 1:2:2:2 ratio. With probability 0.9, the behaviour policy walks to the closest object that advances the RM without rejecting and picks it up, and otherwise it acts randomly.

VLM labelling. We label the episodes with Gemma-4-31B-it. Eight episodes do not fit in its 262,144-token context, so we leave them unlabelled and keep 4,992 of the 5,000. Every prompt is prefixed with the same scene description:

Scene: A first-person (egocentric) view inside a single 3D room
with brick walls and an asphalt floor. Scattered on the floor
are coloured objects: BOXES (cubes) and BALLS (spheres), in
RED, GREEN, and BLUE. The camera is tilted slightly downward.
An object is 'close and centered in front' when it is large
and near the bottom-centre of the view (the agent is right up
against it). Objects that have been picked up are removed
from the room.

Listing 5: MiniWorld-Pickup scene description

Since the propositions are pickup events, we ask the VLM when each object disappears. As in the other environments, we query each object separately, giving six queries per episode. Each query shows every frame of the episode (stride 1), numbered by its original index, followed by the disappearance question for that object (Listing 6 shows it for the red box).

At which frame does the red box disappear from the environment?
The red box can disappear AT MOST ONCE in the episode: the
agent consumes it by walking right up to it and picking it
up. The disappearance looks like this: in one frame the red
box is large and centred directly in front of the agent, and
in the next frame it is gone while the camera has NOT moved.
IMPORTANT: the red box merely being out of view (because the
agent looked or walked away) is NOT disappearance -- only
count it if it vanishes while the view stays still.
Conversely, if the agent walks right up to the red box until
it is large in the centre of the view, and the object is then
never visible again in ANY later frame, that IS a consumption --
do not miss these. Answer with the frame index of the FIRST
frame in which the red box has vanished, or -1 if it never
disappears.

Listing 6: MiniWorld-Pickup object disappearance question (red box)

Each reported disappearance frame is snapped to the nearest pickup action within ±4 frames to pin the exact transition, yielding per-proposition pickup events on {r,g,b,x,o}. We then distil these events into a small CNN that detects pickups from two consecutive 64 × 64 frames. We apply this detector only at frames where the agent takes the pickup action. The detector labels the evaluation episodes, and it also provides the labels for offline RL. To track the RM state we use the belief, setting each proposition’s noise to the detector’s measured true- and false-positive rates. Table 7 reports the accuracy of both the VLM and the distilled labels.

rgbxoOverall
% Positive0.90.80.81.11.41.0
VLM Accuracy100.0100.0100.0100.099.9100.0
VLM Precision99.299.699.799.198.399.0
VLM Recall98.396.895.896.497.497.0
Distilled Accuracy100.0100.0100.0100.0100.0100.0
Distilled Precision99.699.299.798.898.799.1
Distilled Recall99.098.998.898.498.998.8

Table 7. Per-proposition label accuracy (%) on MiniWorld-Pickup. VLM: Gemma-4-31B-it labels. Distilled: the pickup detector distilled from them, used at evaluation. % Positive is the proportion of frames where each proposition holds, and Overall is micro-averaged over propositions. Positives are rare, so precision and recall are more informative than accuracy.

Proposition, Reward-Machine and Label Prior Generation

We evaluate the generation steps of Sections 3.2 and 3.3 with Gemma-4-31B-it on the tasks in Table 1, over 10 runs per task,

using the recommended sampling settings (temperature 1.0, top-pp 0.95, top-kk 64) [16]. The prompts for the three steps are given in Listings 7, 8 and 12. Every prompt includes the environment’s scene description and possibly its physical constraints (Listing 11).

Proposition generation. The LLM generates one set of propositions from all task descriptions of an environment (Listing 7). Generated propositions can differ from the reference ones in naming or factorisation, e.g. on GeoGrid the LLM generates six object propositions instead of three colours and two shapes. To compare them, the same LLM at temperature 0 writes each generated proposition as a Boolean formula over the reference propositions. Across runs and environments, the generated propositions can express all reference propositions the tasks require. In addition, all but one of the 173 generated propositions appear in at least one of the RMs later generated with them.

RM generation. We additionally use the LLM to generate the RM for each task given the propositions (Listing 8). We test two prompting strategies: decomposed, where the LLM produces one RM per sub-task, and monolithic, where the LLM produces a single RM for the full task. Each generated RM is compared with the expert-written reference RM. Two RMs are equivalent if they have the same set of minimal accepting label sequences up to length L=15L = 15, and for the cyclic Loop task we compare the sequences that complete one cycle. For this check, decomposed RMs are composed via cross-product [33], and for generated propositions, the reference label sequences are translated into the generated alphabet using the formulas above. Given the reference propositions, the decomposed strategy produces an equivalent RM in every run, while the monolithic strategy fails on QGBench-Scene tasks that have multiple valid orderings as well as occasionally on MiniWorld-Pickup (Table 8). Over the generated propositions, the decomposed strategy does so in 114/120 runs, and the failures are malformed RMs, such as non-deterministic ones.

Label prior generation. For each reference RM, the LLM generates the label prior P(L∣u)P(L \mid u) of the RM state belief (Listing 12), from the same environment description and physical constraints as RM generation. It first classifies each proposition as lasting or momentary. A lasting proposition holds until something changes it, and a momentary one holds only at the step its event happens. The LLM also gives each proposition’s value at the start of the episode. For each RM state uu and lasting proposition pp, it then answers two questions: whether pp is true when the RM reaches uu, and whether a single action can change pp at the next step. A momentary proposition is false and can change in every state. We map each pair of answers to the probability P(Lp=1∣u)P(L_p=1 \mid u) that pp is true in uu, namely 1 (true, cannot change), 1−ϵ1-\epsilon (true, can change), ϵ\epsilon (false, can change) or 0 (false, cannot change), so a change that triggers an RM transition never has zero probability. Finally, the LLM lists the combinations of momentary propositions that can hold at a single step. The prior P(L∣u)P(L \mid u) is proportional to ∏pP(Lp∣u)\prod_p P(L_p \mid u) over the label sets whose momentary part is listed, and 0 otherwise. The ϵ\epsilon value is considered a hyperparameter, but by setting it to ϵ=0.005\epsilon=0.005 on OGBench-Scene and ϵ=0.116\epsilon=0.116 on GeoGrid and MiniWorld-Pickup, we can recover the expert-written reference. In fact, the LLM-generated prior matches the expert-written one in 119/120 runs, with the only error coming from a GeoGrid Logic run whose response does not follow the required format.

EnvTaskDecomposedMonolithicGen. props
GeoGridSequence10/1010/1010/10
GeoGridLoop10/1010/1010/10
GeoGridLogic10/1010/1010/10
GeoGridSafety10/1010/1010/10
OGBench-SceneOpen10/100/108/10
OGBench-SceneClose+Lock10/100/1010/10
OGBench-SceneCube-in-Drawer10/1010/1010/10
OGBench-SceneCube+Window10/100/1010/10
MiniWorld-PickupSequence10/1010/1010/10
MiniWorld-PickupLogic10/108/107/10
MiniWorld-PickupSafety10/109/1010/10
MiniWorld-PickupAlternation10/1010/109/10

Table 8. RM generation accuracy: fraction of runs producing a trace-equivalent RM (10 runs per cell, Gemma-4-31B-it). Decomposed and Monolithic use the reference propositions; Gen. props generates the propositions first and uses the decomposed prompt.

Reduction of Belief Reward to RM Reward

Proposition 1. If the RM state belief u~t\tilde{u}_t is one-hot for all tt (i.e. u~t[ut∗]=1\tilde{u}_t[u_t^*]=1 for some ut∗∈Uu_t^* \in U), then the task reward (Equation (5)) reduces to the standard RM transition reward:

δr(u~t−1,u~t)=δr(ut−1∗,ut∗).\delta_r(\tilde{u}_{t-1},\tilde{u}_t)=\delta_r(u_{t-1}^*,u_t^*).

Proof. Since u~t−1\tilde{u}_{t-1} is one-hot at ut−1∗u_{t-1}^*, the numerator and denominator of Equation (4) retain only the u=ut−1∗u=u_{t-1}^* term. Evaluating at u′=ut∗u'=u_t^*:

αt[ut∗]=C[ut−1∗,ut∗,L~t−1](αt−1[ut−1∗]+δr(ut−1∗,ut∗))C[ut−1∗,ut∗,L~t−1]=αt−1[ut−1∗]+δr(ut−1∗,ut∗).\alpha_t[u_t^*]=\frac{C[u_{t-1}^*,u_t^*,\tilde{L}_{t-1}]\left(\alpha_{t-1}[u_{t-1}^*]+\delta_r(u_{t-1}^*,u_t^*)\right)}{C[u_{t-1}^*,u_t^*,\tilde{L}_{t-1}]} =\alpha_{t-1}[u_{t-1}^*]+\delta_r(u_{t-1}^*,u_t^*).

Substituting into Equation (5) with one-hot beliefs:

δr(u~t−1,u~t)=(u~t)Tαt−(u~t−1)Tαt−1=αt[ut∗]−αt−1[ut−1∗]=δr(ut−1∗,ut∗).\delta_r(\tilde{u}_{t-1},\tilde{u}_t)=(\tilde{u}_t)^\mathsf{T}\alpha_t-(\tilde{u}_{t-1})^\mathsf{T}\alpha_{t-1} =\alpha_t[u_t^*]-\alpha_{t-1}[u_{t-1}^*] =\delta_r(u_{t-1}^*,u_t^*).

RM State Belief: Worked Example

Example 1 (Correlated propositions absorb VLM errors). Consider a “reach red” RM on GeoGrid (Appendix § 8) with the full proposition set P={R,G,B,◯,△}\mathcal{P}=\{R,G,B,\bigcirc,\triangle\}. The prior P(L∣u0)P(L\mid u_0) encodes that each object has both a colour and a shape:

P(◯∣u0)=5864,P(\bigcirc\mid u_0)=\frac{58}{64},
P({R,◯}∣u0)=P({R,△}∣u0)=P({G,◯}∣u0)=P({G,△}∣u0)=P({B,◯}∣u0)=P({B,△}∣u0)=164,P(\{R,\bigcirc\}\mid u_0)=P(\{R,\triangle\}\mid u_0)=P(\{G,\bigcirc\}\mid u_0) =P(\{G,\triangle\}\mid u_0)=P(\{B,\bigcirc\}\mid u_0)=P(\{B,\triangle\}\mid u_0)=\frac{1}{64},

with P(L∣u0)=0P(L\mid u_0)=0 for all other LL. In particular, RR alone is structurally impossible. Suppose that the per-proposition classifier rates are TPRp=0.9\mathrm{TPR}_p=0.9 and FPRp=0.05\mathrm{FPR}_p=0.05 for all pp, and the VLM predicts L~0={R}\tilde{L}_0=\{R\}. In this case, the VLM incorrectly predicts RR as true but correctly predicts all other propositions as false. If deterministic tracking were used, this false positive would immediately trigger a transition to the accepting state. With the RM state belief update, we compute u~1\tilde{u}_1 via Equation (3):

C[u0,u0,{R}]=5864⋅0.05⋅0.954⏟L=∅+116⋅0.05⋅0.12⋅0.952⏟L∈{{G,◯},{G,△},{B,◯},{B,△}}≈0.037,C[u_0,u_0,\{R\}]=\underbrace{\frac{58}{64}\cdot0.05\cdot0.95^4}_{L=\varnothing} +\underbrace{\frac{1}{16}\cdot0.05\cdot0.1^2\cdot0.95^2}_{L\in\{\{G,\bigcirc\},\{G,\triangle\},\{B,\bigcirc\},\{B,\triangle\}\}}\approx0.037,
C[u0,uA,{R}]=164⋅0.9⋅0.1⋅0.953⏟L={R,◯}+164⋅0.9⋅0.1⋅0.953⏟L={R,△}≈0.002.C[u_0,u_A,\{R\}]=\underbrace{\frac{1}{64}\cdot0.9\cdot0.1\cdot0.95^3}_{L=\{R,\bigcirc\}} +\underbrace{\frac{1}{64}\cdot0.9\cdot0.1\cdot0.95^3}_{L=\{R,\triangle\}}\approx0.002.

After normalisation, u~1[u0]≈0.94\tilde{u}_1[u_0]\approx0.94. Despite the erroneous prediction, the belief is still mostly concentrated on the initial state. In contrast, if the VLM predicts L~0={R,◯}\tilde{L}_0=\{R,\bigcirc\}, which is consistent with the prior, the balance shifts:

C[u0,u0,{R,◯}]=5864⋅0.052⋅0.953+2⋅164⋅0.05⋅0.1⋅0.9⋅0.952+2⋅164⋅0.052⋅0.12⋅0.95≈0.002.C[u_0,u_0,\{\mathrm{R},\bigcirc\}] = \frac{58}{64}\cdot0.05^2\cdot0.95^3 + 2\cdot\frac{1}{64}\cdot0.05\cdot0.1\cdot0.9\cdot0.95^2 + 2\cdot\frac{1}{64}\cdot0.05^2\cdot0.1^2\cdot0.95 \approx0.002.
C[u0,uA,{R,◯}]=164⋅0.92⋅0.953+164⋅0.9⋅0.05⋅0.1⋅0.952≈0.011.C[u_0,u_A,\{\mathrm{R},\bigcirc\}] = \frac{1}{64}\cdot0.9^2\cdot0.95^3 + \frac{1}{64}\cdot0.9\cdot0.05\cdot0.1\cdot0.95^2 \approx0.011.

After normalisation, u~1[uA]≈0.84\tilde{u}_1[u_A] \approx0.84. As the observation is consistent with the prior, the belief shifts towards the accepting state.

Choice of Offline RL Algorithm

To test whether the benefits of RM-VLM are tied to IQL, we repeat the OGBench-Scene evaluation with FQL (Table 9). RM-VLM again outperforms the non-RM baselines on all OGBench-Scene tasks, showing that the gains are not specific to IQL. Adding dense VLM progress within transitions (RM-VLM+GVL) performs on par with or slightly above RM-VLM alone on three of four tasks and slightly below it on Cube-in-Drawer. FQL solves Close+Lock (0.92) from the same VLM-based reward on which IQL reaches 0.53, indicating that it is more robust to the labelling errors that limit IQL on this task (Table 3). Conversely, FQL performs worse than IQL on the two cube tasks.

TaskBCGVLVLM-SDRM-VLMRM-VLM+GVL
Open0.60 ± 0.050.73 ± 0.120.32 ± 0.120.99 ± 0.010.97 ± 0.02
Close+Lock0.09 ± 0.030.13 ± 0.080.10 ± 0.040.92 ± 0.040.93 ± 0.06
Cube-in-Drawer0.04 ± 0.020.04 ± 0.040.02 ± 0.020.61 ± 0.060.56 ± 0.08
Cube+Window0.01 ± 0.010.02 ± 0.010.03 ± 0.020.47 ± 0.070.51 ± 0.09

Table 9. OGBench-Scene task success rates with FQL [39] (mean ± std over 5 seeds). Values within 95% of the best per row in bold.

Training Details and Hyperparameters

We list the hyperparameters used for offline RL with IQL [21] in Table 10. Table 11 lists the hyperparameters of the FQL results on OGBench-Scene (Table 9) and of the online PPO results on GeoGrid (§ 4.4).

Evaluation. For each run, we select the checkpoint with the best training-time evaluation and report its success on 200 held-out episodes whose seeds are disjoint from those used for selection. Training-time evaluation runs every 5×1045 \times10^4 steps on GeoGrid (10 episodes, one per layout), every 2×1042 \times10^4 steps on OGBench-Scene (50 episodes) and every 10510^5 steps on MiniWorld-Pickup (50 episodes).

When doing the RM state belief ablation (Table 3), the Naive and IBU variants use the un-augmented RMs on OGBench-Scene, as the extra RM states (e.g. unlocked) exist only to support the state-dependent structural prior. On GeoGrid and MiniWorld-Pickup all methods use the same RM.

Compute. We used a cluster on NVIDIA H200 GPUs. A single offline run costs about 2.5 GPU-hours on GeoGrid, 4 on OGBench-Scene with IQL and 3 with FQL, and 8.5 on MiniWorld-Pickup; an online PPO run on GeoGrid costs about 3. Labelling with Gemma-4-31B-it, served by SGLang in FP8, costs about 70 GPU-hours for the propositions and 70 for the GVL progress estimates on OGBench-Scene, 125 and 120 respectively on MiniWorld-Pickup, and roughly 30 each on GeoGrid, which was labelled on a GH200 GPU.

Controlled Label Noise on GeoGrid

The VLM labels on GeoGrid are nearly perfect (Table 5), so all RM tracking variants in Table 3 perform equally well. We therefore inject synthetic noise into the ground-truth labels of the GeoGrid Logic and Safety tasks and train the three variants of Section 4.5 on them. Each proposition label in the dataset is flipped independently with probability ϵ∈{0,0.005,0.02,0.05}\epsilon\in\{0, 0.005, 0.02, 0.05\}. At evaluation, the labels fed to the policy’s RM tracking are flipped at the same rate, while success is judged on the true RM state. Under Naive tracking, these rates corrupt the RM state in 15%, 46% and 75% of the Logic episodes and 11%, 37% and 64% of the Safety episodes. We follow the setting of the GeoGrid runs in Table 2, only setting the TPRp=1−ϵ\mathrm{TPR}_p = 1 - \epsilon and FPRp=ϵ\mathrm{FPR}_p = \epsilon (0.99 and 0.005 at ϵ=0\epsilon= 0). For evaluation, we report success on 200 held-out episodes, with the best checkpoint by 20 evaluations of 10 episodes.

Table 12 reports the results. Belief degrades most gracefully on both tasks, and its gap to Naive widens with the noise, from +0.07 to +0.36 on Logic and from +0.08 to +0.37 on Safety. IBU collapses on Logic from ϵ=0.02\epsilon= 0.02, as its flat prior spreads the belief over RM states, so the structural prior accounts for the remaining gain. We also evaluate the impact of inaccurately specifying the TPR and FPR used by Belief, assuming half or twice the true flip rate on GeoGrid Logic (Table 13). Halving the rate does not reduce success, and doubling it costs only 0.02 at ϵ=0.02\epsilon= 0.02. At ϵ=0.05\epsilon= 0.05, however, the doubled rate makes the belief too diffuse to learn from.

Table 13: Belief on GeoGrid Logic with a misspecified noise model (mean ± std over 5 seeds). The assumed flip rate is 0.5×, 1× or 2× the true rate ϵ\epsilon.

ϵ\epsilonAssumed 0.5×Assumed 1×Assumed 2×
0.020.79 ± 0.020.79 ± 0.020.77 ± 0.02
0.050.54 ± 0.050.52 ± 0.020.00 ± 0.00

Table 13.

Table 10: Offline RL (IQL) hyperparameters for the main results. All methods within an environment share these values, except that the GeoGrid and MiniWorld-Pickup baselines use a CNN-GRU encoder.

HyperparameterGeoGridOGBench-SceneMiniWorld-Pickup
Training steps10610^{6}10610^{6}7×1057 \times10^{5}
Batch size256256256
OptimiserAdamAdamAdam
Learning rate3×10−43 \times10^{-4}3×10−43 \times10^{-4}3×10−43 \times10^{-4}
Discount γ\gamma0.990.990.99
IQL expectile0.70.850.6
Advantage-weighting temperature3.010.03.0
Max advantage weight100100100
Target-network EMA rate0.0050.0050.005
Observation / encoder84×84 image, CNN64×64 image (3-frame stack), CNN64×64 image (3-frame stack), CNN
Baseline encoderCNN-GRU (512)CNN (as above)CNN-GRU (512)
Reward scalerreturn-based (×10310^{3})nonereturn-based (×10310^{3})
RM value-iteration discount γRM\gamma_{RM}0.90.90.9

Table 10.

Table 11: Hyperparameters of the FQL results on OGBench-Scene (Table 9) and of the online PPO results on GeoGrid (Section 4.4).

HyperparameterValue
FQL, OGBench-Scene
Training steps10610^{6}
Batch size256
Learning rate3×10−43 \times10^{-4}
Discount γ\gamma0.99
Target-network EMA rate0.005
BC coefficient α\alpha3
Flow steps10
Target QQ aggregationmean
QQ-loss normalisationyes
Reward scale100
Actor / critic MLP4×5124 \times512
Observation / encoder64×64, 3-frame stack, CNN
Evaluation interval / episodes2×1042 \times10^{4} / 50
PPO, online GeoGrid
Environment steps10710^{7}
Parallel environments32
Rollout length (per env.)2048
Minibatch size8192
Epochs per update10
Learning rate3×10−43 \times10^{-4}
Discount γ\gamma0.99
GAE λ\lambda0.95
Clip range0.2
Entropy coefficient0.05
Value-loss coefficient0.5
Max gradient norm0.5
Observation / encoder84×84, CNN
RM value-iteration discount γRM\gamma_{RM}0.9

Table 11.

Table 12: Task success on GeoGrid under synthetic label noise (mean ± std over 5 seeds). ϵ\epsilon is the probability of flipping each proposition label. Values within 95% of the best per row in bold.

ϵ\epsilonNaiveIBUBelief
Logic
00.98 ± 0.020.91 ± 0.050.99 ± 0.00
0.0050.84 ± 0.010.74 ± 0.060.91 ± 0.04
0.020.55 ± 0.020.00 ± 0.000.79 ± 0.02
0.050.16 ± 0.020.00 ± 0.000.52 ± 0.02
Safety
00.95 ± 0.010.96 ± 0.010.94 ± 0.02
0.0050.82 ± 0.020.80 ± 0.020.90 ± 0.02
0.020.70 ± 0.030.75 ± 0.020.85 ± 0.01
0.050.42 ± 0.030.59 ± 0.020.79 ± 0.03

Table 12.

H Prompts

This appendix collects the prompts used throughout our pipeline.

Proposition generation

You are given descriptions of a desired reward function in English. Your job is to construct a set of propositions (high-level events) that will help decompose these tasks into sub-goals suitable for reward machine construction. When defining propositions, ensure that no two propositions are logical negations of each other.

Guidelines:
- Each proposition should describe an event or condition that the tasks refer to directly: the completion of an action a task names, or a state a task asks to reach or to avoid. Do not introduce propositions for preconditions or intermediate configurations needed to achieve them.
- Distinguish exactly the objects and attributes that the tasks distinguish, so that every sub-goal and constraint in the tasks can be written as a boolean formula over the propositions.
- Do not use aggregate or counting propositions; the reward machine keeps track of progress over time.

Please only include propositions that are necessary for representing the tasks.

Scene description:
{SCENE_DESCRIPTION}

These propositions should help represent the following tasks:
- {TASK_1}
- {TASK_2}
- ...

For each proposition, provide a short lowercase symbol (e.g. ab, bc) used in logical formulas and a brief description of what the proposition means.

Return ONLY the propositions, one per line, in this exact format:
<symbol> = <description>

Do not include any other text, headers, or explanations.

Listing 7: Proposition Generation Prompt

Reward machine generation

The decomposed prompt is shown below. {SCENE_DESCRIPTION} is the environment description followed by its physical constraints (Listing 11), and {PROPOSITIONS} is the reference or the generated proposition set.

You are an expert reward machine designer.
Scene description:
{SCENE_DESCRIPTION}

You are given the following task:
- {TASK}
And the set of propositions you can use to express the task with.
{PROPOSITIONS}

The presented task can be expressed using a set of reward machines. If the task involves sub-goals that can be achieved independently, express each as a separate reward machine. The sub-task reward machines will later be composed via cross-product. Two sub-goals are independent when neither has to be achieved before the other and neither's propositions constrain the other. Keep independent sub-goals in separate reward machines, even when each sub-goal has its own internal sequence of stages. Only combine behaviours into one reward machine when one stage must follow another within the same line of progress, or when a constraint must hold throughout the task. If a constraint must hold at every step throughout the task (e.g., 'never pick up X'), encode it as reject transitions within the main task RM rather than as a separate constraint RM. If two consecutive transitions carry the identical guard formula, collapse them into one: A->B with guard G followed by B->C with the same G becomes A->C with guard G. {SHARED_INSTRUCTIONS} Please return these reward machines.

Reward Machine states should be numbered uA, uR, u0, u1, u2, u3, ..., with uA always being the accepting state, uR always the rejecting state and u0 always the initial state. Transitions should be represented as a tuple (i, j, phi, r), where i and j are the start and Reward Machine states of the transition, respectively, phi is a logical formula over the set of propositional symbols (use "=" to represent "not", "&" to represent "and", and "|" to represent "or", and write the formula in disjunctive normal form), and r is the reward for the transition. Your output should be the transitions in the Reward Machine, one per line, in the tuple form shown above, e.g. (u0, u1, ~X & Y, 0), with no other punctuation. For brevity, do not spell-out self-loop transitions that provide 0 reward in the output. Rewards: use 0 for intermediate transitions, 1 for reaching uA, and -1 for any backward transition that leaves uA.

To parse this output easily, please return in the following format:
RM#1:
<transitions_go_here>
RM#2:
<transitions_go_here>
...

Do not include any reasoning, explanation, or commentary -- only the RM blocks.

Listing 8: Reward Machine Generation Prompt (decomposed)

{SHARED_INSTRUCTIONS} is the following text, used by both the decomposed and the monolithic prompt: Assume the initial state requires the maximum number of steps to complete the task -- no sub-goal is already satisfied. If a precondition is already satisfied at runtime, the RM will simply skip that transition immediately. Decompose each task into the maximum number of meaningful intermediate states that track progress. Do not add shortcut transitions that skip intermediate states. When the task has a necessary logical precondition, please include it in the reward machine even if it is not directly described by the task description. When the environment states that one condition must hold before another can be achieved, give that precondition its own transition, reached before the transition it enables. Guard each backward transition with only the negation of the condition that established the state it leaves. If the environment describes a condition as a lasting state that can later become false again, include backward transitions from every state where that condition was established -- not just from the accepting state. Do not add backward transitions for conditions the environment describes as momentary or as one-off events. When multiple propositions together identify a single entity, use their conjunction in guards to distinguish individual entities. A guard mentioning only one property creates non-determinism if the omitted property matters for tracking progress. Transition guards from the same state must be mutually exclusive -- no valuation should satisfy more than one guard. For repeating or cyclic tasks, do not use an accepting state (uA). Instead, cycle back to the initial state and give +1 reward for completing each cycle. The cyclic RM should contain only the transitions needed for one cycle; do not add reject states unless the task description explicitly mentions something to avoid.

Shared RM design instructions

Figure 9. Shared RM design instructions

The monolithic prompt is identical except that the paragraph describing the decomposition is replaced by the following, and it asks for a single RM#1 block:

Reward Machine Generation Prompt (monolithic): differing paragraph

Figure 10. Reward Machine Generation Prompt (monolithic): differing paragraph

Physical constraints appended to the scene description

Figure 11. Physical constraints appended to the scene description

OGBench-Scene physical constraints

Figure 12.

Label prior generation

The prompt receives the same scene description and physical constraints as RM generation (Listing 11). The JSON template at the end is generated from the states and propositions of the given RMs.

Label prior generation prompt

Figure 13.

Listing 10: Reward Machine Generation Prompt (monolithic): differing paragraph

Express this task as a single reward machine. If the task involves sub-goals that can be achieved independently, the RM must handle all valid orderings of those sub-goals internally. Two sub-goals are independent when neither has to be achieved before the other and neither's propositions constrain the other. If a constraint must hold at every step throughout the task (e.g., 'never pick up X'), encode it as reject transitions within the RM. If two consecutive transitions carry the identical guard formula, collapse them into one: A->B with guard G followed by B->C with the same G becomes A->C with guard G. {SHARED_INSTRUCTIONS} Please return this reward machine.

OGBench-Scene: Physical constraints:

  • The drawer/window must be unlocked before it can be opened or closed.

  • The lock only freezes the handle, so it can be engaged or released whether the drawer/window is open or closed. Locking it while open leaves it open until it is unlocked again.

  • The cube can only be put inside the drawer while the drawer is open, but once it is inside it stays inside even if the drawer is later closed.

  • Locked/unlocked, open/closed and the cube's location are lasting states, and each can change back later: an opened drawer can be closed again, and a released lock can be re-engaged.

GeoGrid: Physical constraints:

  • The agent occupies a single cell, so it is on at most one object at a time: no two colours, and no two shapes, can hold in the same step.

  • Each object has exactly one colour and exactly one shape, so a colour never holds without a shape and a shape never holds without a colour.

  • Being on an object is momentary: it holds only while the agent stands on that object, and stops as soon as the agent moves to another cell.

  • The valid observations are: nothing (empty cell), or exactly one colour-shape pair from {r&c, r&t, g&c, g&t, b&c, b&t}. A guard using only a colour (e.g., 'r') matches two objects; use the conjunction (e.g., 'r&c' or 'r&t') when those objects must be tracked separately.

  • Since observations are momentary, the last required visit should directly trigger the transition to uA. When multiple paths lead to uA, connect each path directly to uA with its own guarded transition rather than merging paths through an intermediate state.

MiniWorld-Pickup: Physical constraints:

  • The agent picks up at most one object at a time, so no two colours can hold in the same step, and a box and a ball cannot both hold in the same step.

  • Every object has exactly one colour and is either a box or a ball, so a colour never holds without a box or ball and a box or ball never holds without a colour.

  • There is exactly one box and one ball of each colour (6 objects total). After picking up one colour-kind pair (e.g., r&x), the only remaining object of that colour is the other kind (e.g., r&o), so the same conjunction cannot occur twice.

  • Picking up an object is an event that happens in a single step, not a lasting state, and it cannot be undone: the object is removed from the room.

  • The valid observations are: nothing (no pickup), or exactly one colour-kind pair from {r&x, r&o, g&x, g&o, b&x, b&o}. A guard using only a colour (e.g., 'r') matches two distinct objects; use the conjunction (e.g., 'r&x' or 'r&o') when those objects must be tracked separately.

  • Since each pickup is instantaneous, a task is complete the moment the last required pickup occurs -- the pickup event itself should trigger the transition to uA.

  • Since pickups are irreversible, when the task specifies a strict ordering, add reject transitions at each state for every pickup that is not the next expected one.

Each RM tracks these propositions: {RM_PROPOSITIONS}

We need to know, for every RM state u and every proposition p used by that RM, what holds at the time steps when that RM is in state u. First classify every proposition as LASTING or MOMENTARY:

  • LASTING: it describes a condition of the world that, once it holds, keeps holding until something changes it.

  • MOMENTARY: it describes an event that holds only at the single time step at which the event happens. A MOMENTARY proposition holds only at the step at which its event happens, which is the step that triggers the RM transition, so in every RM state u its value is FALSE and its next_step_change is YES. Answer the questions below in full for the LASTING propositions.

Then give, for every proposition, its value (TRUE or FALSE) at the start of the episode, in the situation the task describes (where the task says nothing, assume no sub-goal is already satisfied). Use it for the initial state u0 and for every state the RM can be in before that proposition has changed.

Answer two separate questions for each pair of an RM state u and a proposition p:

  • value: Is p true at the moment the RM reaches u, either at the start of the episode or through a transition into u? Answer TRUE or FALSE.

  • next_step_change: While the RM is in u, can a single action of the agent change the value of p at the next time step? Answer YES if this is possible in at least one situation the RM can be in while in u, even if the change would move the RM to another state. Answer NO if, in every such situation, changing p would first require another proposition to change in a way that moves the RM out of u, or if the physical constraints forbid changing p at all.

Reason from the physical constraints and from how the RM can reach u: consider every path into u, including the initial state and backward transitions.

In addition, at each time step the labelling function returns the set of propositions that are true. For each RM, list every combination of that RM's MOMENTARY propositions that can occur at a single time step, and no others. Write each combination as its true propositions joined by '&' (e.g. a&b), and the combination in which none of them is true as "empty". LASTING propositions are not part of this list (their values in each state are given by your answers above); write ["empty"] for an RM without MOMENTARY propositions. Check each combination against the physical constraints: a combination is possible unless a constraint rules it out.

Output a single JSON object inside a ```json code block with exactly this structure, replacing each "..." type with LASTING or MOMENTARY, each "..." value with TRUE or FALSE, each "..." next_step_change with YES or NO, each "..." reason with one short sentence, and each label_sets list with the label sets. {JSON_TEMPLATE} Output nothing after the code block.

Listing 12: Label Prior Generation Prompt

Proposition labelling

The labelling prompt takes a numbered list of propositions, each given by its key and its question. In our experiments each query contains a single proposition. Each query comes with one reference frame where it is true and one where it is false.

You are an expert at analyzing robot manipulation images.
{SCENE_DESCRIPTION}

For each frame, determine whether each of the following propositions is true (1) or false (0): {PROPOSITION_LIST}

For every proposition, first write a brief analysis of the visual evidence before providing the binary value.

Output a single JSON object whose keys are frame indices (as strings) and whose values are objects mapping proposition keys to 0 or 1. Example format: {"0": {"<prop>": 0 or 1}, "1": {"<prop>": 0 or 1}, ...}

Before the episode frames, here are reference examples for each proposition—one frame where the proposition is TRUE and one where it is FALSE. Use these to anchor what the positive and negative states look like in this environment; the actual per-frame judgements below may still be either value. Reference: [<prop>] = 1 (TRUE) [IMAGE] Reference: [<prop>] = 0 (FALSE) [IMAGE]

Now the episode frames: You are given {N} frames from a robot manipulation episode in temporal order. Frame 0: [IMAGE] Frame 1: [IMAGE] ...

Listing 13: Proposition Labelling Prompt

Progress estimation (GVL)

The following prompts are used for VLM-based progress estimation. The GVL baseline asks for whole-task progress, and RM-VLM+GVL asks for progress toward each proposition (Table 2 and Section 4.5.2). For OGBench-Scene, RM-VLM+GVL also queries GVL for the progress toward each negated proposition, using a frame where the proposition holds as the 0% reference. In Ge-OGrid and MiniWorld-Pickup, l^p(s)=1−ℓp(s)\hat{l}_p(s) = 1 - \ell_p(s) is read from the grounding labels. For MiniWorld-Pickup, {TASK_DESCRIPTION} is the scene description (Listing 5) followed by a TASK: line holding the task or proposition, and an image of the empty room is the 0% reference frame. Since a pickup requires first reaching the object, the per-proposition goal of RM-VLM+GVL is a matching object being close and centred, e.g. for r “A red object (box or ball) is close and centered in front of the agent”.

You are an expert roboticist tasked to predict task completion percentages for frames of a robot for the task of '{TASK_DESCRIPTION}'.
The task completion percentages are between 0 and 100, where 100 corresponds to full task completion.
Note that the following frames are in random order, so please pay attention to the individual frames when reasoning about task completion percentage.

[FRAMES]

Now, for the task of '{TASK_DESCRIPTION}', output the task completion percentage for the following frames that are presented in random order. For each frame, format your response as follows. Frame {i}:
Frame Description: {description}, Task Completion Percentage: {percentage}%

Do not omit any frame.

Listing 14: Progress Estimation Prompt (GVL)

Success detection (VLM-SD)

The VLM-SD baseline asks for the first frame at which the whole task is completed. {TASK_DESCRIPTION} is the scene description followed by the task’s language command. In MiniWorld-Pickup, the episode is shown at stride 8.

You are an expert at analyzing robot manipulation trajectories.

{TASK_DESCRIPTION}

This task requires observing the sequence of frames to determine
its completion.
Carefully reason whether the complete task has been completed at
each frame.

You are given {N} frames from a robot manipulation episode in
temporal order. For each frame, analyze whether ALL sub-goals
of the task have been achieved.
Output a single JSON object:
{"first_success_frame": <int>}
where the value is the 0-based frame index of the FIRST frame
where the task is fully completed. If the task is never
completed in the episode, return:
{"first_success_frame": -1}
Frame 0:
[IMAGE]
Frame 1:
[IMAGE]
...

Listing 15: Success Detection Prompt (VLM-SD)

Use of AI-Assisted Technologies

The authors used Claude models (Anthropic) through Claude Code as an interactive assistant for writing and refactoring experiment code, including figure-generation scripts, launching and monitoring runs, aggregating results, drafting and editing text, and writing the Matplotlib code used to render Figure 1. All methods, experiments, claims and final text were designed, decided and verified by the authors, who take full responsibility for the content.

References

  1. [1]Alessandro Abate, Giuseppe Di Giacomo, Mathias Jackermeier, Jan Kretínský, Maximilian Prokop, and Christoph Weinhuber. 2026. Semantically labelled automata for multi-task reinforcement learning with LTL instructions. arXiv preprint arXiv:2602.06746 (2026).
  2. [2]Shayan Meshkat Alsadat, Jean-Raphaël Gaglione, Daniel Neider, Ufuk Topcu, and Zhe Xu. 2025. Using Large Language Models to Automate and Expedite Reinforcement Learning with Reward Machine. In 2025 American Control Conference, ACC 2025, Denver, CO, USA, July 8-10, 2025. IEEE, 206–211. doi:10.23919/ACC63710.2025.11107701
  3. [3]Leo Ardon, Daniel Furelos-Blanco, Roko Parac, and Alessandra Russo. 2024. FORM: Learning expressive and transferable first-order logic reward machines. arXiv preprint arXiv:2501.00364 (2024).arxiv.org/abs/2501.00364
  4. [4]Kate Baumli, Satinder Baveja, Feryal Behbahani, Harris Chan, Gheorghe Comanici, Sebastian Flennerhag, Maxime Gazeau, Kristian Holsheimer, Dan Horgan, Michael Laskin, et al. 2023. Vision-language models as a source of rewards. arXiv preprint arXiv:2312.09187 (2023).
  5. [5]Amir Bayat, Necmiye Ozay, Alessandro Abate, and Raphael M Jungers. 2026. End-to-End Abstraction-Based Control with LLM-Enhanced NL-to-LTL Translation. arXiv preprint arXiv:2606.30163 (2026).DOI
  6. [6]Alberto Camacho, Rodrigo Toro Icarte, Taryn Q Klassen, Richard Anthony Valenzano, and Sheila A McIlraith. 2019. LTL and beyond: Formal languages for reward function specification in reinforcement learning. In IJCAI, Vol. 19. 6065–6073.
  7. [7]Roger Creus Castanyer, Faisal Mohamed, Pablo Samuel Castro, Cyrus Neary, and Glen Berseth. 2025. ARM-RM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning. arXiv preprint arXiv:2510.14176 (2025).arxiv.org/abs/2510.14176
  8. [8]Yongchao Chen, Rujul Gandhi, Yang Zhang, and Chuchu Fan. 2023. NL2LTL: Transforming Natural Languages to Temporal Logics using Large Language Models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 2023, Houda Bouamor, Juan Pino, and Kalika Bali (Eds.). Association for Computational Linguistics, 15880–15903. doi:10.18653/V1/2023.EMNLP-MAIN.985DOI
  9. [9]Maxime Chevalier-Boisvert, Bolun Dai, Mark Towers, Rodrigo Perez-Vicente, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and J K Terry. 2023. Minigrid & minihworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. Advances in Neural Information Processing Systems 36 (2023), 73383–73394.
  10. [10]Jacques Cloete, Mathias Jackermeier, Ioannis Havoutis, and Alessandro Abate. 2026. PracT LTL: Learning to generalize across symbols in LTL instructions for multi-task RL. arXiv preprint arXiv:2601.22891 (2026).
  11. [11]Matthias Cosler, Christopher Hahn, Daniel Mendoza, Frederik Schmitt, and Caroline Trippel. 2023. nl2spec: Interactively Translating Unstructured Natural Language to Temporal Logics with Large Language Models. In Computer Aided Verification - 35th International Conference, CAV 2023, Paris, France, July 17-22, 2023, Proceedings, Part II (Lecture Notes in Computer Science, Vol. 13965), Konstantin Enea and Akash Lal (Eds.). Springer, 383–396. doi:10.1007/978-3-031-37703-7_18DOI
  12. [12]Yuqing Du, Ksenia Konyushkova, Misha Denis, Akhil Raju, Jessica Landon, Felix Hill, Nando De Freitas, and Serkan Cabi. 2023. Vision-language models as success detectors. arXiv preprint arXiv:2303.07280 (2023).arxiv.org/abs/2303.07280
  13. [13]Daniel Furelos-Blanco, Mark Law, Anders Jonsson, Kryssia Broda, and Alessandra Russo. 2021. Induction and exploitation of subgoal automata for reinforcement learning. Journal of Artificial Intelligence Research 70 (2021), 1031–1116.
  14. [14]Daniel Furelos-Blanco, Mark Law, Anders Jonsson, Kryssia Broda, and Alessandra Russo. 2023. Hierarchies of Reward Machines. In International Conference on Machine Learning (ICML).
  15. [15]Daniel Furelos-Blanco, Charles Pert, Frederik Kelbel, Alex F. Spies, Alessandra Russo, and Michael Dennis. 2025. Beyond Fiske: Unsupervised Environment Design for Task-Level Pairs. In Fortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-27, 2026. Sven Koenig, Chad Jenkins, and Matthew E. Taylor (Eds.). AAAI Press, 21145–21153. doi:10.1609/AAAI.V40I25.39258
  16. [16]Gemma Team. 2026. Gemma 4 Technical Report. arXiv:2607.02770 [cs.CL]. https://arxiv.org/abs/2607.02770
  17. [17]Chengyang Gu, Yuxin Pan, Hui Xiong, and Yize Chen. 2026. STO-RL: Offline RL Under Sparse Rewards via LLM-Guided Subgoal Temporal Order. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2026, Paphos, Cyprus, May 25-29, 2026, Viviana Mascardi, John Thangarajah, Chris Amato, and Louise A. Dennis (Eds.). ACM, 2317–2326. doi:10.65109/EHJQ3648DOI
  18. [18]Kuo-Han Hung, Pang-Chi Lo, Jia-Fong Yeh, Han-Yuan Hsu, Yi-Ting Chen, and Winston H Hsu. 2024. VICTOR: Learning hierarchical vision-instruction correlation rewards for long-horizon manipulation. arXiv preprint arXiv:2405.16545 (2024).arxiv.org/abs/2405.16545
  19. [19]Mathias Jackermeier and Alessandro Abate. 2025. DeepLTL: Learning to efficiently satisfy complex LTL specifications for multi-task RL. In International Conference on Learning Representations (ICLR).arxiv.org/abs/2410.04631
  20. [20]Matthew Jackson, Uljad Berdica, Jarek Liesen, Shimon Whiteson, and Jakob Foerster. 2025. A clean slate for offline reinforcement learning. Advances in Neural Information Processing Systems 38 (2025), 161052–161083.arxiv.org/abs/2504.11453
  21. [21]Ilya Kostrikov, Ashvin Nair, and Sergey Levine. 2021. Offline reinforcement learning with implicit q-learning. arXiv preprint arXiv:2110.06169 (2021).arxiv.org/abs/2110.06169
  22. [22]Yen-Ling Kuo, Boris Katz, and Andrei Barbu. 2020. Encoding formulas as deep networks: Reinforcement learning for zero-shot execution of LTL formulas. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 5604–5610.arxiv.org/abs/2006.01110
  23. [23]Tony Lee, Andrew Wagenmaker, Karl Pertsch, Percy Liang, Sergey Levine, and Chelsea Finn. 2026. RoboReward: General-Purpose Vision-Language Reward Models for Robotics. arXiv preprint arXiv:2601.00675 (2026).arxiv.org/abs/2601.00675
  24. [24]Borja G. León, Murray Shanahan, and Francesco Belardinelli. 2022. In a Nutshell, the Human Asked for This: Latent Goals for Following Temporal Specifications. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net. https://openreview.net/forum?id=rUwm9wCjURVarxiv.org/abs/2110.09461
  25. [25]Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. 2020. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 (2020).arxiv.org/abs/2005.01643
  26. [26]Andrew C Li, Tizhon Q Chen, Toryn Q Klassen, Pashootan Vaezipoor, Rodrigo T Icarte, and Sheila A McIlraith. 2024. Reward machines for deep RL in noisy and uncertain environments. Advances in Neural Information Processing Systems 37 (2024), 110341–110368.arxiv.org/abs/2406.00120
  27. [27]Andrew C Li, Toryn Q Klassen, Andrew Wang, Parand A Alamdari, and Sheila A McIlraith. 2025. Grounding Language in Agentic Behaviours using Limited Data. arXiv preprint arXiv:2507.10741 (2025).arxiv.org/abs/2507.10741
  28. [28]Jason Xinyu Liu, Ankit Shah, Eric Rosen, Mingxji Jia, George Kondaris, and Stefanie Tellex. 2024. Skill transfer for temporal task specification. In 2024 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2535–2541.DOI
  29. [29]Jason Xinyu Liu, Ziyi Yang, Irhad Idrees, Sam Liang, Benjamin Schornstein, Stefanie Tellex, and Ankit Shah. 2023. Grounding Complex Natural Language Commands for Temporal Tasks in Unseen Environments. In Conference on Robot Learning, CoRL 2023, 6-9 November 2023, Atlanta, GA, USA (Proceedings of Machine Learning Research, Vol. 229), Jie Tan, Marc Toussaint, and Kourosh Darvish (Eds.). PMLR, 1084–1110. https://proceedings.mlr.press/v229/liu23d.htmlarxiv.org/abs/2302.11649
  30. [30]Yecheng Jason Ma, Joey Hejna, Chuanyun Fu, Dhruv Shah, Jacky Liang, Zhuo Xu, Sean Kirmani, Peng Xu, Danny Driess, Ted Xiao, et al. 2024. Vision language models are in-context value learners. In The Thirteenth International Conference on Learning Representations.arxiv.org/abs/2411.04549
  31. [31]Yecheng Jason Ma, Vikash Kumar, Amy Zhang, Osbert Bastani, and Dinesh Jayaraman. 2023. Liv: Language-image representations and rewards for robotic control. In International Conference on Machine Learning. PMLR, 23301–23320.
  32. [32]Yecheng Jason Ma, William Liang, Guanzhi Wang, De-An Huang, Osbert Bastani, Dinesh Jayaraman, Yuke Zhu, Linxi Fan, and Anima Anandkumar. 2024. Eureka: Human-Level Reward Design via Coding Large Language Models. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net. https://openreview.net/forum?id=EiuRuo5SFarxiv.org/abs/2310.12931
  33. [33]Cyrus Neary, Zhe Xu, Bo Wu, and Ufuk Topcu. 2020. Reward machines for cooperative multi-agent reinforcement learning. arXiv preprint arXiv:2007.01962 (2020).DOI
  34. [34]Andrew Y Ng, Daishi Harada, and Stuart Russell. 1999. Policy invariance under reward transformations: Theory and application to reward shaping. In IcmI, Vol. 99. Citeseer, 278–287.
  35. [35]Lorenzo Nodari. 2023. Adversarial attacks to reward machine-based reinforcement learning. arXiv preprint arXiv:2311.09104 (2023).
  36. [36]Matteo Pannacci, Andrea Fanti, Elena Umili, and Roberto Capobianco. 2026. Grounding LTL Tasks in Sub-Symbolic RL Environments for Zero-Shot Generalization. arXiv preprint arXiv:2602.09761 (2026).arxiv.org/abs/2602.09761
  37. [37]Roko Parac, Lorenzo Nodari, Leo Ardon, Daniel Furelos-Blanco, Federico Cerutti, and Alessandra Russo. 2024. Learning robust reward machines from noisy labels. arXiv preprint arXiv:2408.14871 (2024).DOI
  38. [38]Seohong Park, Kevin Frans, Benjamin Eysenbach, and Sergey Levine. 2024. OGBench: Benchmarking offline goal-conditioned rl. arXiv preprint arXiv:2410.20092 (2024).arxiv.org/abs/2410.20092
  39. [39]Seohong Park, Qiyang Li, and Sergey Levine. 2025. Flow Q-Learning. In Proceedings of the 42nd International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 267), Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu (Eds.). PMLR, 48104–48127. https://proceedings.mlr.press/v267/park25f.htmlarxiv.org/abs/2502.02538
  40. [40]Amir Pnueli. 1977. The Temporal Logic of Programs. In 18th Annual Symposium on Foundations of Computer Science. IEEE, 46–57.
  41. [41]Dean A Pomerleau. 1988. ALVINN: An autonomous land vehicle in a neural network. Advances in neural information processing systems 1 (1988).
  42. [42]Wenjie Qiu, Wensen Mao, and He Zhu. 2023. Instructing goal-conditioned reinforcement learning agents with temporal logic objectives. Advances in Neural Information Processing Systems 36 (2023), 39147–39175.DOI
  43. [43]Juan Rocamonde, Victoriano Montesinos, Elvis Nava, Ethan Perez, and David Lindner. 2023. Vision-language models are zero-shot reward models for reinforcement learning. arXiv preprint arXiv:2310.12921 (2023).arxiv.org/abs/2310.12921
  44. [44]John Schulman, Filip Wolski, Prafulla Dhariwal, Alex Radford, and Oleg Klimov. 2017. Policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017).arxiv.org/abs/1707.06347
  45. [45]Sumedh Sontakke, Jesse Zhang, Sébastien M. R. Arnold, Karl Pertsch, Erdem Biyik, Dorsa Sadigh, Chelsea Finn, and Laurent Itti. 2023. RoboCLIP: One Demonstration is Enough to Learn Robot Policies. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (Eds.). http://papers.nips.cc/paper_files/paper/2023/hash/ae54ce310476218f26dd48c1626d5187-Abstract-Conference.htmlarxiv.org/abs/2310.07899
  46. [46]Haoyuan Sun and Feng Wu. 2023. Less is more: Refining datasets for offline reinforcement learning with reward machines. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. 1239–1247.
  47. [49]Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila A. McIlraith. 2022. Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. Journal of Artificial Intelligence Research 73 (2022), 173–208.DOI
  48. [50]Elena Umili, Francesco Argenziano, Aymeric Barbin, and Roberto Capobianco. 2023. Visual Reward Machines. In Proceedings of the 17th International Workshop on Neural-Symbolic Learning and Reasoning, La Certosa di Pontignano, Siena, Italy, July 3-5, 2023 (CEUR Workshop Proceedings), Artur S. d’Avila Garcez, Tarek R. Besold, Marco Gori, and Ernesto Jiménez-Ruiz (Eds.). CEUR-WS.org, 255–267. https://ceur-ws.org/Vol-3432/paper23.pdfDOI
  49. [51]Pashootan Zaeizoor, Andrew C Li, Rodrigo A Toro Icarte, and Sheila A Mcilraith. 2021. Ltl2action: Generalizing ltl instructions for multi-task rl. In International Conference on Machine Learning. PMLR, 10497–10508.
  50. [52]Sreyas Venkataraman, Yufei Wang, Ziyu Wang, Navin Sriram Ravie, Zackory Erickson, and David Held. 2025. Real-World Offline Reinforcement Learning from Vision Language Model Feedback. In IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2025, Hangzhou, China, October 19-25, 2025. IEEE, 13452–13459. doi:10.1109/IROS60139.2025.11246918DOI
  51. [53]David Venuto, Sami Nur Islam, Martin Klissarov, Doina Precup, Sherry Yang, and Ankit Anand. 2024. Code as reward: Empowering reinforcement learning with vlms. arXiv preprint arXiv:2402.04764 (2024).arxiv.org/abs/2402.04764
  52. [54]Yufei Wang, Zhanyi Sun, Jesse Zhang, Zhou Xuan, Erdem Biyik, David Held, and Zackory Erickson. 2024. Rl-vlmf: Reinforcement learning from vision language foundation model feedback. arXiv preprint arXiv:2402.03681 (2024).arxiv.org/abs/2402.03681
  53. [55]Yanwei Wang, Tsun-Hsuan Wang, Jiayuan Mao, Michael Hagenow, and Julie Shah. 2024. Grounding language plans in demonstrations through counterfactual perturbations. arXiv preprint arXiv:2403.17124 (2024).arxiv.org/abs/2403.17124
  54. [56]Tianbao Xie, Sihe Zhao, Chen Henry Wu, Yitao Liu, Qian Luo, Victor Zhong, Yanchao Yang, and Tao Yu. 2024. Text2Reward: Reward Shaping with Language Models for Reinforcement Learning. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net. https://openreview.net/forum?id=tUM39YTRxH
  55. [57]Beyazıt Yalçınkaya, Niklas Lauffer, Marcell Vazquez-Chanlatte, and Sanjit A Seshia. 2024. Compositional automata embeddings for goal-conditioned reinforcement learning. Advances in Neural Information Processing Systems 37 (2024), 72933–72963.arxiv.org/abs/2411.00205
  56. [58]Yunhao Yang, Cyrus Neary, and Ufuk Topcu. 2024. Multimodal Pretrained Models for Verifiable Sequential Decision-Making: Planning, Grounding, and Perception. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024, Auckland, New Zealand, May 6-10, 2024, Mehdi Dastani, Jaime Simão Sichman, Natasha Alechina, and Virginia Dignum (Eds.). International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2011–2019. doi:10.5555/3563537.3663065DOI
  57. [59]Lotfi A Zadeh. 1965. Fuzzy sets. Information and control 8, 3 (1965), 338–353.
  58. [60]Yinuo Zhao, Jiale Yuanz, Zhiyuan Xu, Xiaoshuai Hao, Xinyi Zhang, Kun Wu, Zhengping Che, Chi Harold Liu, and Jian Tang. 2025. Training-Free Generation of Temporally Consistent Rewards from VLMs. In IEEE/CVF International Conference on Computer Vision, ICCV 2025, Honolulu, HI, USA, October 19-25, 2025. IEEE, 8133–8143. doi:10.1109/ICCV51701.2025.002762arxiv.org/abs/2507.04789
  59. [61]Christos Ziakas and Alessandra Russo. 2025. VITA: Zero-Shot Value Functions via Test-Time Adaptation of Vision-Language Models. arXiv preprint arXiv:2506.10085 (2025).arxiv.org/abs/2506.10085

Paper details

vlnc:W_8njchsfx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 12

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Code

View statement
Looking for related papers…
Contents