Reward Translation via Reward Machine in Semi-Alignable MDPs
Authors: Yun Hua
Haosheng Chen
Wenhao Li
Bo Jin
Baoxiang Wang
Hongyuan Zha
Xiangfeng Wang
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Reward Shaping
Primary area: reinforcement_learning

Abstract: Addressing reward design complexities in deep reinforcement learning is facilitated by knowledge transfer across different domains. To this end, we define \textit{reward translation} to describe the cross-domain reward transfer problem. However, current methods struggle with non-pairable and non-time-alignable incompatible MDPs.
This paper presents an adaptable reward translation framework \textit{neural reward translation} featuring \textit{semi-alignable MDPs}, which allows efficient reward translation under relaxed constraints while handling the intricacies of incompatible MDPs. Given the inherent difficulty of directly mapping semi-alignable MDPs and transferring rewards, we introduce an indirect mapping method through reward machines, created using limited human input or LLM-based automated learning.
Graph-matching techniques establish links between reward machines from distinct environments, thus enabling cross-domain reward translation within semi-alignable MDP settings. This broadens the applicability of DRL across multiple domains. 
Experiments substantiate our approach's effectiveness in tasks under environments with semi-alignable MDPs.

Reward Translation via Reward Machine in Semi-Alignable MDPs
Yun Hua" Haosheng Chen
Wenhao Li
Bo Jin 3
Baoxiang Wang* Hongyuan Zha 4 Xiangfeng Wang 25
Abstract
autonomous driving (Zhu al., 2018), and precision agricul- ture management (Li et al., 2021). However, it is recognized that the effectiveness of current DRL methods hinges on the quality of the provided reward signals. Dense rewards require significant engineering effort in practical applica- tions (Fickinger et al., 2021), and non-Markovian reward signals are often produced by humans (MacGlashan et al., 2017), potentially hindering the training process. In light of these challenges, it is important to consider how hu- mans excel at drawing their own experiences to learn and apply skills across various domains. Specifically, hu- mans demonstrate a unique ability to recognize latent struc- tural similarities between tasks in related but distinct areas, which enables them to abstract skills from differences. They adeptly learn from parttppatyyoo observations that lack explicit correspondence internal seff-representations (Stadie et al., 2017; Liu et al., 2018; Sermanet et al., 2018) perform- ing tasks like finding a path on map and navigating to destination in real life-or imitating experts with different embodiments (Gupta et al., 2017: Rizzolatti and Craighero, 2004; Liu et al., 2019) unfamiliar environments (Liu et al., 2019). Endowing RL agents with this ability and transfer re- wards across different domains could greatl enhance their learning efficiency and reduce the efforts in reward design.
Addressing reward design complexities in deep reinforcement learning is facilitated by knowl- edge transfer across different domains. To this end, we define reward translation to describe the cross-domain reward transfer problem. How- ever, current methods struggle with non-pairable and non- con-time-alignan paper presents an adaptable reward translation framework neural reward translation featuring semi-alignable MDPs, which allows efficient re- ward translation under relaxed constraints while handling the intricacies of incompatible MDPs. Given the inherent difficulty of directly mapping semi-alignable MDPs and transferring rewards, we introduce indirect mapping method through reward machines, created using limited human input or LLM-bbsed automated learning. Graph- matching techniques establish links between re- ward machines from distinct environments, thus enabling cross-domain reward translation within semi-alignable MDP settings. This broadens the applicability of DRL across multiple domains. Experiments substantiate our approach's 's effec- tiveness in tasks under environments with semi- alignable MDPs
incompatible MDPs. This
Existing efforts for transferring rewards across various do- mains primarily focus on cross-domain imitation learning, including three main types of domain discrepancies: dy- namies (Liu al., 2019), embodiment (Gupta al., 2017: Hudson et al., 2022), and viewpoint mismatch (Jiang et al., 2020; Stadie et al., 2017). These approaches require paired and time-aligned demonstrations, often hard to handle more than one descriptor at once. Subsequent advances, such as DAIL (Kim et al., 2020) and other works using Cycle- GAN (Raychaudhuri et al., 2021) and Maaoov-asssessteinn distance (Fickinger et al., 2021), relax some constraints, allowing algorithms automatically learn observation and action mappings from unpaired and unaligned demonstra- tions. However, they still struggle with incompatible MDPs which are non-pairable and non-time-alignale tasks.
1. Introduction
Deep reinforcement learning (DRL) has made notable strides in areas such as gaming (Mnih et al., 2015; Lam- ple and Chaplot, 2017), robotic control (Kober et al., 2013),
'Equal contribution ! Antai College of Economics and Manage- ment, Shanghai Jiao Tong University, Shanghai, China SScoool of Computer Science and Technology, East China Normal Uni- versity, Shanghai, China 'School of Software Engineering, Tongji University, Shanghai, China "School of Data Science, The Chi- nese University of Hong Kong. Shenzhen, Shenzhen, China KKey Laboratory of Mathematics and Engineering Applications, East China Normal University, Shanghai, China. Correspondence to: Xiangfeng Wang <xfwang @ www.c.ccc..u.......
In this paper, we introduce the concept of reward translation, deseribing cross-domain reward transfer in reinforcement learning as a process akin to translation between differ- ent languages. We further introduce semi-alignable MDPs. which describe incompatible MDPs sharing abstract
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
SSa
Somi- Aligabble MDPs T "1S. (l)
Environments with sunse
Alignable MDPs T 4)) ((in))
NCMb
Figure 1. The distinction between alignable and semi-alignable MDPs involves injective mappings. In NChain environments and the HalfCheetah-v3, agents aim for point F. Alignable MDPs exhibit state and action space injections, seen in the NChain examples (Eavironment y to 2'). Semi-alignable MDPs, as in a common goal, enabling mappings hetween abstract "goal" and "skill" spaces.
pairings (Environment 2), lack these injections but share
alignment, as illustrated in Figure 1. By further abstracting tasks to focus on skills and sub-tasks, semi-at semi-alignable MDPs permit high-level mapping across domains, more similar to human learning processes. Our goal is to establish frame- work capable of learning these high-level mappings within generalized cemi-alignable MDPs and reusing rewards to enhance training efficiency in new domains. To achieve this, we must abstract tasks to obtain alignable skill and abstract spaces. Reward machines (RMs) provide a bridge to dis- cover task structures with non-Markovian reward functions through the use of high-level events and abstract check- points (Icarte et al., 2022). We propose the neural reward translation (NRT) framework to tackle the reward transfer problem within semi-alignable MDPs. NRT leverages RMs to distill abstract alignments and transfer reward signals between domains.
environments operate under semi-aligned MDPs.
2. Related Works
Domain transfer in RL. Various works have conducted transfer learning in the reinforcement learning area (Taylor and Stone, 2009; Zhu et al., 2023). To deal with trans- fer learning between different domains, primitive meth- ods always try to use the hand-craft features along with distance metric between the imitation agent and the ex- pert. For example, Ammar and Taylor (2011) established a shared state space between MDP in different domains and learns a map between states, while Ammar et al. (2015) ap- plies unsupervised manifold alignment learn linear maps between states possessing similar local geometrie proper- ties. Existing efforts for domain transferring primarily fo- cus on cross-domain imitation learning, relying on three key domain descriptors: dynamics (Liu et al., 2019), em- bodiment (Gupta et al., 2017; Hudson et al., 2022), and viewpoint mismatch (Jiang al., 2020; Stadie et al., 2017). Generally, these approaches acquire states corresponding proxy tasks and paired, time-aligned demonstrations to leam state map or state encoder using deep learning methods. DAIL (Kim et al., 2020) proposes comprehensive frame- work encompassing all three types and employs GAMA to autonomously learn alignment between MDPs from dis- tinet domains. Moreover, xDIO (Raychaudhuri et al., 2021) uses CycleGAN for alignment with state-only demonstra- tions, and GWIL (Fickinger al., 2021) employs Gromov- Wasserstein distance to eliminate proxy task need. These domain transfer approaches assume alignable MDPs, which are often scarce in real-world applications. In contrast, this paper aims to distill abstract alignment from semi-alignable expert demonstrations and transfer it to the imitation agent through an additional reward signal, circumventing the need for alignable MDPs and contributing more general do- main transfer in reinforcement learning.
The primary contributions of this paper are as follows:
1) The introduction of semi-alignable Markov decision pro- cesses (MDPs), providing a crucial theoretical foundation for facilitating reward translation in cross-domain reinforce- ment learning and extending beyond alignable MDPs.
2) The development of a novel framework called neural reward translation (NRT), designed to address the reward translation problem within alignabee MDPs by build- ing upon the foundation provided by reward machines. Moreover, we incorporate an innovative reward machine generator that utilizes large language models for the auto- matic generation of reward machines.
3) The proposal of several semi-alignn alignali environments showeasing the effectiveness of the Neural Reward Trans- lation approach in handling reward translation tasks where
An carly-stage version of the code is available at: translation. Note that the code- base is still under development and may lack full documentation or polish.
2

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
Reward Machine. Reward machines (RM) were initially introduced as class of finite state machines by (Icarte et al., 2018). These machines were designed to unveil the struc- ture of non-Markovian reward functions in tasks represented by high-level events (i.e., propositional variables). Icarte et al. (2018) combined Q-learning with reward machines, proposing QRM, the first reinforcement learning method within RM. Subsequently, Icarte et al. (2022) introduced counterfactual experiences for reward machines (CRM), modified version of QRM capable of learning single Q- function that considers RM states as inputs, thus enhancing compatibility with deep neural networks. Icarte et al. (2022) proposed hierarchical reinforcement learning for reward ma- chines (HRM) to accelerate policy learning, albeit possibly converging sub-optimal solutions. Icarte et al. (2023) formulated a discrete optimization problem for experience- based learning of reward machines in partially observable environments. Reward machines have been applied to solve problems in robotics (Camacho et al., 2021; DeFazio and Zhang, 2021; Shah et al., 2020), multi-agent reinforcement learning (Neary et al., 2021), lifelong reinforcement learn- ing (Zheng et al., 2022), self- self-paced reinforcement learn- ing (Koprulu and Topcu, 2023) and offline reinforcement learning (Sun and Wu, 2023). Unlike these studies, our paper seeks to employ reward machines to uncover task structures in reinforcement learning and facilitate reward signal transfer between tasks from different domains.
the theoretical foundation.
3.1. Reward Translation
In this study, reward translation refers to cross-domain reward transfer in reinforcement learning. Formally, it involves translating rewards from source domain X to target domain Y. Conventional cross-domain methods assume alignable MDPs, employing formulation where state-action alignment between source and target domains is predefined:
Ty (g) - Tx (T)) (y)):
(I)
where s denotes the state, a represents the executed action, and T- is an inverse transformation function mapping el- ements in Y back to their counterparts in X. This direct mapping approach relies strictly on original state-action pairs, rendering it ineffective for non-alignable MDPs lack- ing pairability and amee-llignability To address this limi- tation, we propose a soft version reward translation, which enables reward transfer based on embedded state-action representations:
Ty Ty(e(sy ag)) = r== (e(sg, ay))),
(2)
where e is an embedding function that projects state-action pairs from different domains into a shared latent space. Fig- ure I compares these translation approaches, illustrating how high-level abstractions, "Goal" and "Skill," serve as embeddings for state and action, facilitating reward transla- tion in MDPs without strict pairability and aine-aiignability. A detailed discussion of "Gol"" and "Skill" follows in the next subsection.
Reinforcement learning abstraction. Our work is also related to reinforcement learning abstraction, which aims to improve the efficiency and scalability of reinforcement learn- ing algorithms when dealing with complex tasks by creat- ing abstract representations of environments or tasks (Abel, 2022). Various types of abstractions have been explored, including state (Zhang et al., 2020; Abel et al., 2019; Ka- malaruban et al., 2020; Cortese et al., 2021), action (Şimşek et al., 2005; Machado et al., 2017). and temporal transi- tion (Abel et al., 2020; Biza and Platt, 2019; Ma et al., 2021: Yang et al., 2021). Reward machines can also be considered as a reinforcement learning abstraction method. However, while these works mainly focus on creating abstract repre- sentations for a single environment or task to reduce the complexity of the state and action spaces, thus making the task easier to learn, our paper aims to use abstraction to achieve high-level knowledge transfer between different reinforcement learning environments.
3.2. Semi-Alignable MDPs
To delincate the soft reward translation problem formulated in Equation. (2), we present the notion of semi-alignable MDPs (Illustrated in Figure 1) to portray incompatible MDPs with concealed maps. In this paper, we elegantly introduce the notions of ""goll" and "skill," symbolized as and w. These concepts encapsulate the essence of high- level states and actions, which can be succinetly conveyed through the equation (6, w) e(s, a). To offer tangi- ble interpretation, a "goal" may be likened to series of checkpoints in games, representing coarse- soase--raiied states. In contrast, "skill" captures the nuances of incremental dif- ferences between each step's s "goals.""
" The infinite horizon Markov decision process (MDP) M can be augmented to be described as a tuple (S, A, B, W, Pr, Pr r), where S signifies the state space, A represents the action space, Pr indicates the transition function based on state and action, while Pr denotes the deterministic transition function on "goal" and r refers to the reward function. The infinite horizon Markov decision process (MDP) M can be aug- mented to be described as a tuple (S, A, B, W, Pr, Pr rr)
3. Preliminaries
Before a comprehensive introduction of the neural reward translation (NRT) framework. it is pertinent to present an overview of the problem context concerning reward transla- tion, outline the principles of semi-alignable MDPs as well as the introduction about reward machine, as this underpins
3

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
where S signifies the state space, A represents the action space, B denotes the set of abstract states "goals", W represents the set of possible transitions between abstract states, Pr indicates the transition function based on state and action, Pr denotes the deterministic transition func- tion on abstract states, and r refers to the reward function. Let B = Hi= and W = {w* Yi=o denote the extended "goal" space and "skill" space, respectively. The augmented MDP for the environment within domain I can be defined as .M = (S.,, As. B., Way Pr,,, .r@.r" ). Additionally, we introduce an intelligible albeit less rigorous definition of semi- remi-alignable MDPs. For the extended MI and My. if there exist injections between (w's E Ws. big E B,) and (w) E Wg y, by E By), they are deemed semi-alignable MDPs. While the precise definition of semi-alignable MDPs is an extension of the MDP alignability theory and the MDP reduction definition proposed by (Kim et al., 2020).
(a) HalfCheetah-v3 task. The target of the robot is reach F.
LA,OP)
10,00,
12.00
(b) Reward machine for HalfCheetah-v3 task. fo F de- notes the terminal state.
Figure 2. Example of reward machine for HalfChectah-v3. The reward machine is designed by (learte et al., 2022).
3.3. Reward Machine
Definition 3.1. An MDP semi-reduction from M to My. denoted as My ε My can be represented by tuple
The formulation of reward machines, which are designed to unveil the organization of non-Markovian reward functions related to tasks characterized by high-level events. Reward machines is typically defined (Icarte et al., 2018);
r (d 1b), Φ: B2 + By: 1b W + Wy.
Definition 3.3. (Reward Machine). Given set of propo- sitional symbols P. a set of (environment) states S, and action domain æ, a finite state reward machine (RM) is defined as tuple ReSA = (U, uo. F, P. Su, 5x), where: U S S represents a finite collection of states, u0 E U denotes the initial state, defines a restricted subset of terminal states (F nu = 2), P signifies the set of proposi- tional symbols, 8, characterizes the tranettransitio function 8n : U - [ P + U}. and o, embodies the state-reward function 8, U - UU X E..
For all (b2, Wx. by: wy) E B2 We xy Wy we have 1). w-optimality:
Om, (ba; Wxr 1, { Our, Cl =
Oar, (by, wy) = = 6 (b,, # 22 (wy) ) + Ø,
where (b, w) = 1 implies that (b, w) exists in M and is produced by the optimal policy:
2). b-dynamic: if M,,, (by, wyy) = 1, we have
It should be emphasized that employing a reward machine in reinforcement learning necessitates the extension of the fundamental MDP.
pry (by, wy)= á ( (bx, wx)) by (by) wa EΦ (wy)
By distilling "goals" and "skills" for optimal policies M and My. a graph of goal-skill trajectories emerges. Fig- ure 3.2 displays this with HalfCheetah-v3 and NChain in- stances. When MDP semi-reduction is present, homomor- phic trajectories reveal underlying structural similarities between M, and My. We then define semi-alignable:
Definition 3.4. (MDP with Reward Machine). An MDP integrated with Reward Machine is represented as tuple TRYSa = (S, A, Pr, P, I. U, no. 8,, 5,), where S, A, Pr, pertain to the state space, action space, transi- tion function, and discount factor in the original MDP, while P. U, uo, da, 8, are determined by the RM. Additionally, L symbolizes a labelling function L S x A
Definition 3.2. Two MDPs Ma and My are semi-alignable if and only if Ma ž My or My > Ma, where Me and My are any two MDPs in domain X' and domain V, while Mr > My conveys that there exists tuple (ø, 1b) enabling semi-reduction from Mg to My.
2".
In each step, the agent executes action a in the MDP, tran- sitioning from state s to s', while the RM changes to state n' = 5,( u, L(s'),, rewarding f(s, a, u, u'). Figure il- lustrates an RM example for HalfCheetah, where the robot aims to reach target F within set number of steps. Unlike RL environmental states (s), RMs possess states (u) and transitions depending on P. denoting the robot's 's relative
Efficiency in achieving the target within (2) improves after applying the semi-reduction definition. However, accessing abstract "goal" and "skill" directly is challenging, making semi-reduction establishment difficult. Therefore, we utilize the reward machine (RM) to indirectly link these two spaces.
L is labeling function that assigns to each transition (s, a,s') of atomic propositions P. indicating which events are consid- ered to have occurred during that transition.

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
Target Task Training
Transfirna Reward Functiun
Reward Translation
Emircnment (Target)
Reward Machine Generntor
Adic
Inneeeer Bosttybe
Gasl Doctpte
Reward machise for Environment
Sapple
Experi Knowledge
Seai dige MDDs
Reward Machine Generation
Emvrroment Y (Seunad)
Roward Machine
Gadl Dow lpir
Generasor
Reward muchine for Pavinement
Experi
Knowledge
Figure 3. An overview of the Neural Reward Translation (NRT) framework: 1) Reward machine generation uses a generator to construct RMs based on task and environment descriptions through expert design. 2) Reward translation aligns source and target RMs using graph matching, facilitating reward transfer. 3) Target task training leverages transferred rewards efficient learning.
position to the target. The path has six checkpoints; cross- ing one causes the RM state to advance. RMs decompose RL problems, providing gaaseeeraiied disassembly to in- form generalized cross-domain knowledge, crucial due to significant differences among diverse tasks in fine-grained states, actions, and transitions because such coarse grainne disassembly will provide a channel to indirectly access to the "goal" and "skill" within semi- alii-alige MDPs. Ulti- mately, the reward machine state space materializes as an injective mapping originating from the agent state space S. We can now propose the following theorem to establish rigorous connection between "goal" and "skill" with RMs:
4. Reward Translation via Reward Machine
In this section, we introduce the primary framework, Neural Reward Translation (NRT), devised to address the proposed reward translation problem between reward machines. The NRT framework comprises three core components: 1) re- ward machine generation component; 2) reward translation component; and 3) target task training component. The Reward Machine (RM) generation component constructs RMs based on task and environment descriptions, leverag- ing expert knowledge and an RM Generator. This study also integrates Large Language Model (LLM) for auto- mated RM construction. The reward translation component employs standard graph matching algorithms to align gener- ated RMs from the source task the target task transfer reward. During target task training, the agent learns within the target environment, leveraging transferred rewards from the source task to enhance learning efficiency.
Theorem 3.5. Given a reward machine RisA for an en- vironment x, posited that a "goal" space B. and a "skill" space Wz exist. Furthermore, injective mappings O2 UN + B, and T, Ps- + Wa are also postulated to exist. Under these stipulations, the ensuing relationships emerge:
Reward Machine Generation. The primary role of this component to construct reward machines by incorporating domain knowledge. Typically, experts manually design re- ward machines based on environment and target information (Icarte et al., 2018). In this work, also propose method to construct reward machines using large language models (LLMs). However, since this is not the core focus of our study, we provide only a brief discussion.
1) For any "goal" by E By, there exists a unique reward machine state w E U or fü Fr such that (z(,() byg or ( Pr.
2) For any "skill" w E W.P. there exists unique proposi- tional symbol p', E Pr. such that T (p')) w/z
A comprehensive proof is in Appendix A.1. This theorem enables recasting the reward translation problem into the more tractable reward machine transfer problem. Each re- ward machine, represented as a finite state machine by a graph, transforms the task into a graph matching problem for transfer between two reward machines.
The LLM is supplied with environment, observation, ac- tion, and target descriptions, detailing the task and domain alongside the definition of reward machine. To facilitate few-shot learning in new tasks, examples of reward machine
5

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
generation are also included. Due to the complexity of learning reward machines, the LLM must consider various aspects such the design of propositional symbols, the injection between the agent's 's observations and RM states, and the RM transitions. We utilize a chain of thought (COT) approach when designing the training prompt for the LLM. Generally, our prompt sequentially poses three questions to the LLM, enabling the development of an RM structure for given environment: i) Design the set of propositional symbols P for (ENV) environment; ii) Design the get event function for (ENV) environment; iii) Design the reward machine for (ENV) environment.
Reward Translation. The focus of this component is to achieve effective reward translation between source and target tasks within distinct domains under semi-alignable Markov Decision Processes (MDPs). Initially, during the reward machine generation component, the Neural Reward Translation (NRT) method constructs reward machines for both source and target tasks. And the reward machine for the source task incorporates a dense reward obtained from its learned optimal value function.
Subsequently. this component transfers the dense reward originating from the source task's ' reward machine to the target task's 's reward machine. As the reward machines are aligned via graph matching, NRT defines two types of re- lationships between the reward machines and seeks to ac- complish reward translation based on these relationships. Definitions for isomorphic and homomorphic reward ma- chines are presented accordingly (In the following of this paper, we use 9 and h to represent the map between reward machine states).
Firstly, to design the set of propositional symbols P. the LLM needs to identify key events within the task description and utilize them as portion of the propositional symbols. Next, in order to design the get event function, the LLM must establish a mapping between events that are accessi- ble in the environment code and the propositional symbols. Subsequently, Python code is generate by LLM, enabling the agent to access reward machine events and states. Fi- nally, to construct the reward machine, the LLM reviews the propositional symbols and extracts general states E U as well as terminal states ʃ E F. The LLM formulates reward machine transitions, including sparse rewards exclusively present upon task completion. Detailed prompts can be found in Appendix A.3.
Definition 4.1. (Isomorphic reward machine). Let RisA and RA denote two reward machines. Rÿss a iso- morphie reward machine to Ry A bijections h Pa - Py and g Uug - U, such that pt} h(pt), = h (pt)) and ut = g(u(), u², = (
RySA if and only if there exist
Considering the priorly introduced bijections b. O(u)) and p, E P: w, l'(:;) in Theorem. 3.5, Theorem 4.2 is utilized to characterize the correlation among semi-alignable MDPs with isomorphic reward machines.
However, the generated or expert designed reward machine only contains sparse rewards; therefore, NRT introduces a denser reward for the source task's ' reward machine. At each stage, the agent operates within the environment and executes action transitioning from state to s' in the MDP. The RM progresses from state u to u' = S1, L(s'),, and the agent acquires a reward comprised of the original reward and the reward from the RM:
Theorem 4.2. If M, and My are two MDPs satisfying My m My and My 2 Ma, then their tasks possess isomor- phic reward machines RPsA and R'pSA-
The comprehensive proof can be found in Appendix A. For MDPs M, and My. should isomorphic reward machines exist for their tasks, a reinforcement learning agent's ' reward function in M, can be represented as:
Ass, a, s', u. w/) = r(s, a, s') +6, w., (,, L(s)). (3)
5, is depicted using a potential-based reward shaping frame- work to maintain policy consistency:
3t fy (sy. ays Sy's uy uy') r Bys sy') + 6% (Ug. Uy Uy'),
(6)
(4) where RR represents the discount parameter. Moreover, to compute the potential value of the corresponding reward machine state, NRT incorporates the expert of optimal value function of the agent in source task g as follows:
(u, = 7R)((") - p(u),
and if M, employs the transferred o;, the reward function will be indicated by:
Fyy (sy: Oy. sy', My u,,) = ry (sy: ay sy + (o(((((()))))))))))()) g(u,")) ").
Given that both 87th and 8y employ potential- reward shaping, we can deduce the following equation by examin- ing the following potential-based reward shaping properties:
(u) = Egas [V* (st, 24 i, =]]]
(5)
T-1
T-1 Fo
Consequently, RMs for both source and target tasks are gen- crated, while the obtained reward machine for the source task possesses& a dense reward derived from its learned opti- mal value function. The subsequent challenge involves the transfer of dense rewards from the source task to target task.
Σ ==0
-
(ag))
(8)
==0
where T represents the task duration, and I donates (e), aby st,1, .,y, u,t1). The above relations also hold for
6

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
transferring state reward functions from Mg Mg How- ever, isomorphic reward machines impose restrictive condi- tions demanding a bijection between semi-alignable MDPs reward machines. Therefore, homomorphic reward ma- chines are introduced as a more flexible formulation.
ward received from the source task within distinct domain. In the stage, the agent operating in the target task has access to the transferred reward function. The agent acquires ob- servation sy from the target task environment at every step of training. This observation is subsequently fed into the reward machine, which yields the corresponding reward ma- chine state Uy Given the observation and reward machine state (sy, Sy's My.. Uy the agent acquires the transferred reward ry' (sy, ay: Sy' My. Myy )) from the transferred reward function. Subsequently, the agent can employ diverse rein- forcement learning algorithms to train its policy, aiming to maximize the aggregate transferred reward:
Definition 4.3. (Homomorphic reward machine). Let RisA and Rys.A denote two reward machines. RysA homomorphic reward machine to PSS A if and only if there exist injections h: Pz + Py and Ug + U4 such that P h(pp)) and ui g (.,).
Additionally, considering the bijections b, = (u,) and P: E P: Wi = ((p;) introduced in Theorem 3.5, Theo- rem 4.4 is utilized to characterize the correlation among semi-alignable MDPs with homomorphic reward machines.
[(0) = Err,rup rup ES (8 0g
uy u
(10)
Theorem 4.4. If Ma and My are two MDPs satisfying either My ž Ma or Mr ž My then their tasks possess homomorphic reward machines PSA and R PSA'
where J(0) denotes the objective function dependent on the policy parameters 0, and ' represents the time horizon.
The comprehensive proof can be found in Appendix A.1. For MDPs M2 and My. M2 = My. the reinforcement learning agent's reward function in My is denoted as in Equation (6). When My employs the transferred state re- ward functions from the reward machine of Me, the re- ward function remains consistent with Equation (7) while maintaining the characteristics described in Equation (8). Nevertheless, transferring rewards from My to M,, necessi- tates the development of a piecewise function as depicted in Equation (9), due to the absence of a bijection.
5. Experiments
This section presents experiments addressing two primary re- search questions: 1) Can the NRT framework effectively ex- tract abstract alignments from semi-alignable MDPs across reinforcement learning domains? 2) Does transferred re- ward, based on abstract alignment, enhance efficiency and performance in target task training? To investigate these questions, we evaluate the NRT framework in two sparse re- ward settings: 3D Visual Navigation and MuJoCo, verifying both isomorphic and homomorphic reward machines. We use the state-of-the-ar Proximal Policy Optimization (PPO) algorithm as the baseline and conduct an ablation study with three variants: PPO-RM, PPO-NKT(Reward) and PPO- NRT(RM+RRward) PPO-RM augments the agent's obser- vation with the reward machine state but does not trans- fer rewards. PPO-NRT(Reward) transfers rewards without incorporating the reward machine state in the observation. PRO-NRT(RM-Rewaa integrates both reward transfer and reward machine state information. Due to space constraints, detailed experimental descriptions are in Appendix A.4.
5V Fx (S Cne Uay Sn' Uny Uny') (8 Ozz 8z
(u ' if Ug g(uy) and uz = g(u,'), (9) (us, Un otherwise.
As result, a reward translation channel is established be- tween semi-alignable MDPs. To transfer the reward func- tion, corresponding reward machines are first constructed, and subsequently, the state reward function for the original task computed using Equation 5.
5.1. 3D Visual Navigation
In the 3D visual navigation environment, we selected the Sign task in the Miniworld Setevalier-Boiveer et al., 2023) as the target task, with the Text-Sign task serving as the orig- inal task. Figures. depict the original and target tasks, re- spectively. In the Miniworld-SS -ign environment, the agent re- ceive a sparse reward only if it reaches all the targets includ- ing the red key, the blue box and the red box. Figure. 5(a) illustrates the reward transfer between the isomorphic re- ward machines in the Text-Sign and Miniworld-Sin tasks. From Figure. 5(b), our results show that in the Miniworld- Sign environment, where rewards are sparse, both PPO and PPO-RM 110-RM-desppte using original or extended observations
(a) Original task: Texi-Sign (b) Target task:
Miniworld-
Sign
Figure The Sign task for the 3D Visual Navigation environment.
Target Task Training. The primary goal of this component to instruct the target task by utilizing the transferred re-
7

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
Madhine Minisorkl-Sig
NCbain
(-0,
A
(UL1)
(0:7)
B
C
D
Tirget
(A.ST.)))
LR 39.00
(C,04))
LD, 863.79
(a) Original task: NChain
(-
(-4,9)
(-
Reward Machine
(a) Text-Sign to Miniworld-Sae Sign
Ant-v3
(b) Target task: Mujoco-Ant
PPC--NE
IPC MERTIAN Romwal)
Figure 6. The Ant task in Mujcoco environments.
PRO
1.50
Rovend
(b) Learning curve for Miniworld-Sign
Figure 5. Experiment for the 3D Visual Navigation environment. (a) The isomorphic reward machines and the cross domain reward transfer process for Text-Sign and Miniworld-Sign: (b) The learn- ing curve for Miniworld -iin environment.
(a) Learning curve for Mujoco-An
with reward machine information- struggle to overcome the sparse reward issue. In contrast, (PO-NR)(Rewarrd) and PPO-NRT(RM+Rewar)) which leverage transferred rewards, significantly alleviate the problem and achieve superior performance. These findings highlight the effec- tiveness the NRT framework in extracting alignments from almi-alignable MDPs and improving training through the transfer of rewards within isomorphic reward machines.
Rewari Machiie For Majoc
Toastr
Renoat Madiinn NChhin
(b) NChain Mujoco
5.2. Mujoco Experiment
We conducted experiments using Mujoco environments, se- lecting HalfCheetah, Hopper, and Ant target tasks, with simplified NChain game the source task. Due to space constraints, we present only MuJoCo-Am results in the main text, while the full results are included in the Appendix. A.4. Figure 12 in the Appendix illustrates the experimental en- vironments. All target tasks follow the standard OpenAl Gym settings (Brockman et al., 2016) but employ sparse rewards, where the agent receives r 1000 only upon reaching predefined goals. The source task involves navigat- ing a linear state sequence to reach point F, earning sparse reward. Figure 6 presents the original and target tasks in MuJoCo-Ant training. Figure 7(b) depicts the generated reward machine and the cross-domain reward transfer pro- cess from NChain MuloCo, applicable all three target
Figure 7. Experiment for the Mujoco-Ant environment. (a)The ho- momorphic reward machine and cross-domain reward transfer process of NChain to Mujoco. (b) The learning curve for Ant task.
tasks. The reward machines for the source and target tasks exhibit homomorphism, enabling the source task's 's reward signals to guide learning the target environments. As shown in Figure 7(a), our results indicate that extremely sparse reward settings, augmenting observations with re- ward machine information alone is insufficient. However, leveraging transferred rewards substantially mitigates the sparsity issue, significantly improving learning efficiency. Notably, in Ant-v3 tasks, PPO-NRT(Rewardd achieves the best performance.
8

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
6. Conclusion
Haitham Bou Ammar and Matthew E Taylor. 2011. Rein- forcement learning transfer via common subspaces. In International Workshop on Adaptive and Learning Agents. 21-36.
In conclusion, this paper introduced the concept of semi- alignable MDPs alongside the Neural Reward Translation (NRT) framework facilitate reward translation in rein- forcement learning to reduce reward design complexities. NRT employs reward machines to address reward transla- tion challenges within semi- aami-alignable MDPs and features an innovative large language model-based generator for the automatic generation of reward machines. Our method significantly enhances training efficiency across various en- vironments. Although challenges persist in constructing appropriate reward machines and deciphering relationships in complex tasks, future rescarch endeavors will continue to explore the vast potential of semi-alignable MDPs and work towards broadening NRT's applicability in a diverse range of situations and domains.
Ondrej Biza and Robert Platt. 2019. Online Abstraction with MDP Homomorphisms for Deep Learning. In Proceed- ings of the 18th International Conference Autonomous Agents and MultiAgent Systems. 1 1125-1133.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. 2016. OpenAl Gym. auXiv:arXiv1606601...
Alberto Camacho, Jacob Varley, Andy Zeng, Deepali Jain, Atil Iseen, and Dmitry Kalashnikov. 2021. Reward ma- chines for vision-based robotic manipulation. ICRA. 14284-14290.
Impact Statement
Maxime Dowvalie-BBoiveet,, Bolun Dai, Mark Towers, Ro- drigo de Lazcano, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry. 2023, Mini- grid & Miniworld: Modular & Customizable Reinforce- ment Learning Environments for Goal-Oriented Tasks.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work. none which we feel must be specifically highlighted here.
CoRR abs/2306. 13831 (2023).
Aurelio Cortese, Asuka Yamamoto, Maryam Hashemzadeh, Pradyumna Sepulveda, Mitsuo Kawato, and Benedetto De Martino. 2021. Value signals guide abstraction during learning. Elife 10 (2021), e68943..
Acknowledgement
This work was supported by the National Natural Science Foundation of China (NSFC, No. 62231019, 62406270, 72394361, 62106213), the Shanghai Science and Technol- ogy Committee (STCSM, No. 24YF2748800), and an ex- tended support project from the Shenzhen Science and Tech- nology Program.
David DeFazio and Shiqi Zhang. 2021. Leveraging Human Knowledge Learn Quadruped Locomotion Policies. arXiv preprint arX (2021).
Arnaud Fickinger, Samuel Cohen, Stuart Russell, and Bran- don Amos. 2021. Cross-Domain Imitation Learning via Optimal Transport. arXiv preprint arXiv:21 10.03684 (2021).
References
David Abel. 2022. A theory of abstraction in reinforcement learning. arXiv preprint arXiv:2203.003397 (2022).
Abhishek Gupta, Coline Devin, Yuxuan Liu, Pieter Abbeel, and Levine Sergey. 2017. Learning Invariant Feature Spaces to Transfer Skills with Reinforcement Learning. In ICLR.
David Abel, Dilip Arumugam, Kavosh Asadi, Yuu Jinnai, Michael I. Littman, and Lawson L.S Wong. 2019. State abstraction as compression in apprenticeship learning. In Proceedings of the AAAI Conference on Artificial Intelli- gence, Vol. 33. 3134-3142.
Eddy Hudson, Garrett Warnell, Faraz Torabi, and Peter Stone, 2022. Skeletal Feature Compensation for Imitation Learning with Embodiment Mismatch. ICRA. 2482- 2488.
David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman. 2020. Value preserving state-action abstractions. In Interna- tional Conference on Artificial Intelligence and Statisties.
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. 2018. Using reward machines for high-level task specification and decomposition in rein- forcement learning. In ICML. 2107-21
PMLR. 1639-1650.
Haitham Bou Ammar, Eric Eaton, Paul Ruvolo, and Matthew Taylor. 2015. Unsupervised cross-domain transfer in policy gradient reinforcement learning via manifold alignment. In AAAI.
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, Margarita P Castro, Ethan Waldie, and Sheila McIlraith. 2023. Learning reward machines: A study in partially
9

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
observable reinforcement learning. Artificial Intelligence 323 (2023), 103989.
Marlos C Machado, Marc G Bellemare, and Michael Bowl- ing. 2017. A laplacian framework for option discovery in reinforcement learning. In International Conference Machine Learning. PMLR, 2295-2295020
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A McIlraith. 2022. Reward machines: Exploit- ing reward function structure in reinforcement learning. Journal of Artificial Intelligence Research 73 (2022). 173- 208.
Volodymyr Mnih, Koray Kavukcuoglu. David Silver, An- drei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. 2015. Human-level control through deep reinforcement learning. Nature 518, 7540 (2015), 529- 533.
Chong Jiang, Zongzhang Zhang, Zixuan Chen, Jiacheng Zhu, and Junpeng Jiang. 2020. Third-person imitation learning via image difference and variational discrimina- tor bottleneck. In AAAI. 13819-13820.
Cyrus Neary, Zhe Xu, Bo Wu, and Ufuk Topcu. 2021. Re- ward Machines for Cooperative Multi-Agent Reinforee- ment Learning. In AAMAS.
Parameswaran Kamalaruban, Rati Devidze, Volkan Cevher, and Adish Singla. 2020. Environment Shaping in Re- inforcement Learning using State Abstraction. arXiv preprint arXiv:2006. 13160 (2020).
Dripta S Raychaudhuri, Sujoy Paul, Jeroen van Baar, and Amit Roy- Noy-Chowdhury. 2021. Cross-domain Imitation from Observations. In ICML. 8902-8912.
Kuno Kim, Yihong Gu, Jiaming Song, Shengjia Zhao, and Stefano Ermon. 2020. Domain adaptive imitation learn- ing. In ICML. 5286-5295.
Giacomo Rizzolatti and Laila Craighero. 2004. The mirror- neuron system. Annual Review of Neurosciince 27 (2004), 169-192.
Jens Kober, Andrew Bagnell, and Jan Peters. 2013. Re- inforcement learning in roboties: A survey. The Inter- national Journal of Robotics Research 32, 11 (2013),
Pierre Sermanet, Corey Lynch, Yevgen Chebotar, Jasmine Hsu, Eric Jang. Stefan Schaal, Sergey Levine, and Google Brain. 2018. Time-contrastive networks: Sulf-super learning from video. In /CRA. 1134-1141.
1274.
Cevahir Koprulu and Ufuk Topcu. 2023. Reward-Machine- Guided, Self-Paced Reinforcement Learning. In UAI.
Ankit Shah, Shen Li, and Julie Shah. 2020. Planning with uncertain specifications (puns). IEEE Robotics and Au- tomation Letters 5, 2 (2020), 3414-3421.
Guillaume Lample and Devendra Singh Chaplot. 2017. Play- ing FPS games with deep reinforcement learning. In AAAI.
Özgür Şimşek, Alicia P Wolfe, and Andrew G Barto. 2005. Identifying useful subgoals in reinforcement learning by local graph partitioning. In Proceedings of the 22nd inter- national conference on Machine learning. 816-823
Wenhao Li, Xiangfeng Wang, Bo Jin, Dijun Luo, and Hongyuan Zha. 2021. Structured cooperative reinforce- ment learning with time-vary time-varying composite action space. IEEE Transactions on Pattern Analysis and Machine In- telligence 44, 11 (2021), 8618-8634.
Bradly C Stadie, Pieter Abbeel, and Ilya Sutskever. imitation learning. arXiv preprint arXiv: 070.0000300033 (2017).
2017.
Fangchen Liu, Zhan Ling, Tongzhou Mu, and Hao Su. 2019. State Alignment-basee Imitation Learning. In ICLR.
Haoyuan Sun and Feng Wu. 2023. Less Is More: Refining Datasets for Offline Reinforcement Learning with Reward Machines. In AAMAS.
YuXuan Liu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. 2018. Imitation from observation: Learning to imitate behaviors from raw video via context translation. In ICRA. 1118-1125.
Matthew E Taylor and Peter Stone. 2009. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research 10, 7 (2009).
Zhihao Ma, Yuzheng Zhuang, Paul Weng, Hankz Han- kui Zhuo, Dong Li, Wulong Liu, and Jianye Hao. 2021. Learning symbolic rules for interpretable deep reinforce- ment learning. arXiv preprint arXiv:2103.086 00.80222888888 (2021).
Yichen Yang, Jeevana Priya Inala, Osbert Bastani, Yewen Pu, Armando Solar-Lezama, and Martin Rinard. 2021. Program synthesis guided reinforcement learning for par- tially observed environments. Advances in neural infor- mation processing systems 34 (2021), 29669-29683.
James MacGlashan, Mark K Ho, Robert Loftin, Bei Peng, Guan Wang, David L Roberts, Matthew E Taylor, and Michael L Littman. 2017. Interactive learning from policy-dependent human feedback. /CML. 2285-2294.
Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. 2020. Learning Invariant
10

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
Representations for Reinforcement Learning without Re- construction. In International Conference Learning Representations.
Xuejing Zheng. Chao Yu, and Minjie Zhang. 2022. Lifelong reinforcement learning with temporal logic formulas and reward machines. Knowledge Bealed Based Systems 257 (2022), 109650.
Meixin Zhu, Xuesong Wang, and Yinhai Wang. 2018. Human-like autonomous car-following model with deep reinforcement learning. Transportation research part C: Emerging technologies 97 (2018), 348-368.
Zhuangdi Zhu, Kaixiang Lin, Anil K. Jain, and Jiayu Zhou. 2023, Transfer Learning in Deep Reinforcement Learn- ing: A Survey, IEEE Transactions on Pattern Analysis and Machine Intelligence 45, 11 (2023), 13344-13362.

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
A. Appendix
A.1. Proof
Theorem.3.5 Given a reward machine PS for an environment 2, it is posited that a "goal" space B, and a "skill" space Wa exist. Furthermore, injective mappings O₂ U2 + Bg and T Ps - W. are also postulated exist. Under these stipulations, the ensuing relationships emerge:
1) For any "goal" b9g E Bz there exists unique reward machine state ulg E Up or Fa such that Ox(ut)) by
O₂ (u() fiz
2) For any "skill" we E Wa, there exists a unique propositional symbol Ph E Pg such that Ta (P(p)) = wa-
Proof. To prove the theorem, need to show that the reward machine state space U₂ is a valid "goal" space Bz. Given the definitions of "gaa"" by, "skill" wy, and reward machine, we observe that goals and skills are embedded in state-action pairs as: (6 w = en (82 az);
with w being the difference between b9 and b-- Since the labeling function L : S. x Ag x S. - 2r represents the transition of Ugz, we have:
u (s s 1
1 TT(s' an);
so we can get:
u Lo(s'a
By viewing reward machine state us as "goal" by and the reward state difference as defined "skills", the labeling function Ia becomes an embedding for environment æ. Hence, we demonstrate that reward machine state space U, is valid "goal" space Br.
Theorem. 4.2 If two MDPs M, and My M2 2 My and My ž Mn then their tasks have isomorphic reward machine RPsA and Ryp
Proof. Theorem 4.2 can be proven by showing both necessity and sufficiency.
1. Proof of necessity: If M. ž My and My ž Mz, then their tasks have isomorphic reward machines.
Let there exist semi-reductions Tr-vy = (Øz-zy wrrr from M3 to My and ry-t = (0z 4y-zz) from M, to M According to Definition 3.1, these semi-reductions satisfy the π optttiimlliy and y-dynamic conditions for all beliefs and strld-states.
We now construct bijections h: Ps +y and g Us My follows:
h(pp)) r (0.-y r. (w p'y g(u = - (V (b:) = - = uiy
Since dr-oy and thz+yy are functions, so are their inverses. Besides, and I and θ are bijections. According to the transitivity of bijections. These bijections also satisfy the conditions of the isomorphic reward machines in Theorem 4.1, as both semi-reductions preserve π " oo-optimality and y-dynamic properties.
Proof of sufficiency: the tasks have isomorphic reward machines, then M, = My and My 2 Mg.
Given the isomorphic reward machines RísA and Ry with established bijections h : Pa - P,, and Ur - My we will prove that M, ž M, and M, M,-
Define mapping functions بي (w = r, (h(p))) and (b)) = (,(((u))). Since the task structures are isomorphic, these mappings can be used to construct the semi-reduction (dv-gy (2-+y) from M, to My that satisfies the Th ootttiiill and y-dynamic conditions in Definition 3. thus showing that M,, 2 My.
12

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
Similarly, the inverse of given bijections for the semi-reduction ry-+ (Py-zz Vy-z)) That is, set 0y-z((1))) Tx (x(h) = (p')' = w and (b,)) = (x,)) = ( = byg Since and are bijections, their inverses exist and are also bijections. By using these mappings, we can construct semirreduction from My Ma that satisfies the conditions in Definition 3.1, showing that M, M
Having proven both necessity and sufficiency, we conclude the proof of Theorem 4.2.
Theorem. 4.4 If two two MDPs My and My My to2 Me M2 My. then their tasks have homomorphic reward machine RiPAA and RysA
Proof. To prove Theorem 4.4, we need to show both necessity and sufficiency:
1. Proof of necessity: If My Ž M2 or M, ž My. then their tasks have homomorphic reward machines.
Assume 22 - My. Let there exist a semi-reduction ræ-vy = (dx-wy dy from My to My. According to Definition 3.1, these remi-reductions satisfy the nh optimality and B-dynamic conditions for all beliefs and world-states.
We now construct injection h P2 + Py and g U1 - Uy follows:
h(p')) 1 0 (w)))(())))) I,y (w))) (1y((n)))) = pyy
g(u²) = 0, (,) (b))) -,y (b;) = u.y
Since dn-oy and dz are functions, so are their inverses. Besides, and I' and θ are bijections. According to the transitivity of bijections. These bijections also satisfy the conditions the homomorphic reward machines in Theorem 4.3 because semi-reductions preserve the " opttimaalyty and B-dynamic properties.
2. Proof of sufficiency: If the tasks have homomorphic reward machines, then M, M₂ M2 My-
Given the homomorphic reward machines RpSA and Ry that satisfy the established injections h p + py and Ug + My. we will prove that either My M, or Mg ž My.
Assume without loss of generality that |pyl S [P&| and 141 S [4g]- Then we can define mapping functions ( (h((()) = ,,, (pt)) = w for every element the domain of h. Similarly, define (b, θ (g(w()) = (ugg) By for all elements in the domain of
These mappings can be used to construct a semi-reduction (dn-ays va- from M2 to My that satisfies the n" -pttimmllity and B-dynamic conditions in Definition 3.1. Thus, M 2 My.
Having proven both necessity and sufficiency, we conclude that if two MDPs M2 and My. My 2 M2 Ma My. then their tasks have homomorphic reward machine RESA and Ry This completes the proof of Theorem 4.4.
13

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
A.2. Experiments
A.2.1. FRAMEWORK
In this section, we present comprehensive methodology for generating reward machines using large language model (LLM), in case, GPT-4, informed by domain-specific knowledge such task manuals. As illustrated in Figure we employ few-shot learning strategy to familiarize the language model with reward machine design principles. This process involves defining the sets of propositional symbols P and reward machine states U1 creating an event extraction function that integrates the reward machine with the environment, and developing the transition function ö, as well as the state reward function 6,
Next, we equip the L.M with domain knowledge, which comprises both reward machine definitions and environmental descriptions sourced from the task manual. The LLM then answers user-generated queries using its acquired knowledge assist in the creation of the reward machine. Due to the complex nature of reward machine development, implement chain of thought framework to bolster the LLM's s reasoning capabilities.
A.2.2.
RM FOR NCHAIN GAME
# initial state
[5]
# terminal state
(0, 0, lald', ConstattRevarFFuuctonnn--
(0, 1,' a', Constar/levacdduuutttt(---02))))
(0, d' [CostannRevvrrduucctttt---2222
(1, 1, Iblg', ( 0.75)
(1, 2, b',', Coontaan/Reevr///unciioon
(1,0,' g', ConstanRewwar/Funettnn -1.44)
(2, 2, !algrab',
ConstanRoovvrdFuucttonn-----
(2, 5, grab', COnstaal/eeerrr/iucctitt----99
(2, 1,' a', [
(3, 3, Idlg', ConstantReeaddduucctnnn -0.61)
(3, 4,' d', Constratteewrr/Fnnnniooo---- -1.03)
(3, 0,' g', CCnstaattRewwrr//uuctttoon (0.01))
(4, 4, Ic', ConstantBRevacdFFucttton-- -0.56)
(4,3,' d', C
A.2.3. EXAMPLE LEARNING RM BY LLM
Reward Machine Description:
You are familiar with automata theory. A reward machine is defined as following:
Given set of propositional symbols P, a set of (enviromment) states S, and a set of actions A, reward machine (RM) is tuple RYSA =< U, uo, F, du, 6, >, where U is a finite set of states, up E U is an initial state, F is finite set of terminal states (where U n = Ø, terminal states are not existed in U), 5, is the state-transition function, U x 2" -UUF, 8, is the reward-transition function, > U
+ R]
reward machine RPSA starts in state ug. and each subsequent time is some state u, E UUF.. At every step t, the machine receives as input truth assignment de, which is set that contains exactly those propositions in P that currently true in the environment. For example, in open door and get the key game, a = {e) if the agent opens the door while o, = {k} if the agent gets the key k. Then the machine moves to the next state u,+1 = 6,,4,,,7, according to the state-trant transition function, and outputs a reward function r, = 8, (u;) according to the state-reward function. This process repeats until the machine reaches a terminal state. Note that reward machines can model never-ending tasks by defining F Ø3
14

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
A.3. Learning RM by LLM
Few shot Examples
RM Deseriation
Eilw Desci plin
Question
Language Model
Answer
User
COT
Thought
Thought
Figure 8. An overview of the framework to learn reward machine by large language model through domain knowledge.
HalfCheetah
Environment Description: HalfCheetah part Mujoco environments. This environment based on the work by P. Wawzzyúski in "A Cat-Like Robot Real-Time Learning Run". The HalfCheetah a 2-dimensional robot consisting of body parts and 8 joints connecting them (including two paws). The goal is to apply a torque on the joints make the cheetah run forward (right) fast possible, with positive reward allocated based on the distance moved forward and negative reward allocated for moving backward. The torso and head of the cheetah are fixed, and the torque can only be applied to the other joints over the front and back thighs (connecting to the torso), shins (connecting to the thighs), and feet (connecting to the shins). The robot needs to go through 5 checkpoints c(x position=2), e(x (xx_position=4) f(x. (x_ppostion=6), 8. and a(x posttiiooon.. The agent gets a reward 1000 when it reaches a and the control penalization (CP) otherwise. Agent can get its current location by calling self.info['x position"].
Question: Design the of propositional symbols P for HalfCheetah environment.
Think: To design the set of propositional symbols P, first need to find the key events in the environment. The robot need to through 6 checkpoints c(x, (o--posttion-), e(x p-soptioooo))) f(x- (o=-position=6,, e(x-positio==8) and a(x (xxpposttion-O) can use them as the propositional symbols, the agent reach some checkpoint, will reach a new reward machine state. Besides, need to consider situations when agent don't reach the checkpoints.
Answer: The set of propositional symbols can be set including checkpoints in HalfCheetah- v3 and situations not reaching the next checkpoints, P {c, le, e, Je, V/, 9, Ig a, l.
Question: Design the get event function for the HalfCheetah with reward machine.
Think: Here events is depended on the propositional symbols, so the events including reach the checkpoints, and call self.info''x position') can get the agent's current x position. Compare it with checkpoints x position, we can get the events.
Answer:
def (self)) events "
if self. inliinifoo'iiii x -10: events 'b' if self. hnlf.infollx_oosittiei events +- 'a'
> 10:
if self.
] < -2:
events += 'd'
if self.infol" [''_poxxxoioon] > 2:
15

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
events 'e' if daff.infol"_ppositiie events += 'e' if self. Xia_ffflx_psittiiin > 6:
4:
events += 'f' if self.infol. xinonooi__psstttoo > 8: events += 'g'
return events
Question: Design the reward machine for the HalfCheetah environment.
To design the reward machine. I need verify the reward machine states first. As {c, lc, e, S. 9, !g, a, laj. The reward machine including 5 states. As the agent reach checkpoint the game is finished. So these is one terminal state. Thus the reward machine state is {0, 2, 3, 4, 5) based on P. Besides, as the agent gets a reward of 1000 when it reaches and the control penalization (CP) otherwise. The 8, can be designed based on it.
Think:
Answer:
# initial state terminal state
[5]
(0,0, Ie', RewardControl()
10, c', RewardControl()
(1, !e', RewardControl())
(1, e', RewardConntol())
(2,2, !f", RewardConntrl(()
(2,3,' f", Reward(Control()
(3, 3,' !g/, Reeard(Contro(()
(3,4, g RewardControl()
(4,4,' la!, RewardControl()
(4, 5, a',
16

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
A.4. Additional Experiment
In order to present our experimental results more clearly and completely, we provide all the results of our experiments in this section of the appendix. In addition to the two sets of experiments given in the main text, we also provide set of toy examples to show the migration between nchain tasks of different scales. In addition, we provide the results of the reward translation task under three different Mujoco tasks, including the Hopper-V3, V3,, HalfCheetah--V and Ant-V3.
1. NCHAIN EXPERIMENT
In the NChain game, an agent navigates through a linear sequence of states (where N denotes the number of states), aiming to reach the flag's location and grab The agent receives reward:
Used Steps
(r
(11)
Max_Steps
The agent will receive the reward only upon grabbing the flag, At each state, the agent has three possible actions:
{move forward, move backward, grab the flag).
In this experiment, the NRT Framework attempts to transfer rewards from NChain(n=5) to NChain(n=9) (illustrated in Figure 9a)). This experimental setup intends to verify the NRT model's capacity for accurately extracting abstract alignments from semi aemi-alignable MDPs; despite differing in observation space size, NChian(n=5) and NChain(n=9) share an isomorphic reward machine based on correspondingly aligned checkpoints, which can be treated as propositional symbols. Figure (a)
(-0,-020)
[-D-a (--8)
(-4 Goah, 0.80)
(5,84G
GRAPTI
A
( -URI
(0.-3.4
(Sink 7.R)
Dig-Re
INRT
D
C
A
B
E
Start
A
B
Start
(a) Nchain(n=S) to NChain(n=9)
(b) Learning curve for the NChain(u=9)
Figure Experiment for NChain game. (a) environment setting and the isomorphic reward machine for NChain game, and the reward transition function is learned from NChain(n=5); (b) The learning curve for NChain game.
also demonstrates the shared isomorphic reward machine, with reward transitions learned from the source task NChain(n=5), This reward machine effectively guides the agent in completing the NChain(n=9) tasks, providing clear preference for utilized the DQN as baseline, and the training results
the correct path to reach the target. For this experiment, illustrated in Figure 9()). Our findings indicate that the NRT Framework can successfully extract abstract alignments from semi-alio remi-alignable MDPs, while the transferred rewards from the isomorphic reward machine facilitate and promote training.
A.4.2. 3D VISUAL NAVIGATION
In the 3D visual navigation environment, we selected the Sign task in the Miniworld Schevalier-ooiveeee et al., 2023) as the target task, with the Text-Sign task serving as the original task. Figures. depict the original and target tasks, respectively. In the Miniworld-Sign environment, the agent receive sparse reward only if it reaches all the targets including the red key, the blue box and the red box. The sparse reward is formulated as:
Max_Steps Uteps
1000 x
(12)
Max_Steps
At each step, the agent's observation is restricted to the information perceived in the direction of its movement, and must
17

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
select from limited action space consisting of four actions:
[turn left, turn right, move forward, move back).
Due to the partial observability and sparse reward problem, solving Miniworld-Sign with conventional reinforcement learning methods proves challenging. By contrast, the Text-Sign task is simpler, the agent can observe the entire map and directly choose actions to move up, down, left, or right, making task completion significantly easier. The goal of the experiment is transfer knowledge from the trained agent in the Text-Sign environment to the Miniworld-Sign environment within isomorphic reward machines.
We also implemented a naive reward approach on the Sign task (shown in Figure 11, where each time the agent take one thing, will get a reward +10), where the agent receives supplementary rewards when making progress toward the goal. The results show that while naive reward shaping does improve performance compared sparse rewards, there remains a substantial performance gap when compared to NRT method with transferred reward machines. This comparison highlights that while simple reward shaping can help, the structured knowledge transfer facilitated by NRT provides more substantial benefits for learning efficiency. The transferred reward structure itself inherently contains this shaping information but in more principled way that captures the logical dependencies between subtasks, which explains the superior performance of our approach.
Chmmahetive
-10
(a) Sign-with- wrrp-----Trappp Environment Diagram
(b) Learning curve for Sign With Trap
Reward Machine For Sign-With-Trap
fi
f
fz
f1
(-C,
0)
GG. 10)
(G, 10
(G. -10
skg
M
(4,7) 7)
(1,, ?)
(C, 7)
(D, 1000)
A
Transder
57.97)
(B, (6.05)
0.45))
YD, 840.79)
A2
Mg
fo
(-4,0)
(-1,,0)
(-C,00 0)
(-D,0)
Reward Machine For Text-Sign
Transferred reward machine from Text-Sign Sign-with-Trap Environ- ment
Figure 10. Experiment for Sign-with-Traas Trap. (a) Sign-with- Environment Diagram; (b) Transferred reward machine from Text-Sign to Sign-with- Environment: (c) Learning curve for Sign-Wing Senn-Wih-Trrap
Furthermore, we have expanded our evaluation by modifying the Text-Sign task to incorporate more complex disjunctions. In this enhanced environment, we added "trap" mechanism where the agent receives a -10 reward and terminates the episode if it falls into the trap at any point. From reward machine perspective, this modification adds branch from each
18

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
Zomestiie
Tou Mesitrillaaaeen
Figure 11. Learning curve for Miniworld-Sign-Add Naive Reward Basline
state (U0, UI, U2, U3) to terminal failure state, creating multiple disjunctive paths through the task. The environment diagram and transferred reward machine is shown in Figure 10(a) and Figure 10(c) in the additional experiment. The results (shown in Figure 10(b)) demonstrate that NRT continues to show significant performance improvements when transferring the reward machine and corresponding rewards from the original Text-Sign task, even with these more complex logical structures.
A.4.3. MUJOCO
In the Mujoco experiment, selected HalfCheetah, Hopper, and Ant the target tasks, with simple NChain game serving as the source task. Figure. 12 depicts the environment used in this experiment. All target tasks employ the same settings as
G
Hoppers3
HallCheeta-r33
Figure 12. The environment for Mujoco environments. The source task is NChain game where the agent need to reach the point F and get reward. And Hopper-v3, HalfCheetah-v3 and Ant-v3 are the source tasks while their target point F.
PRO
19D
FROJEM
Cammbaate Moro Reward
Combbatte Move Perward
14
(a) NChain -> Hopper
(b) NChain HalfCheetah
(c) NChain - Ant
for mujoco experiment. To intuitively precept the learning process of the agent, provided by OpenAl-Gym which consists forward reward and control reward to show the learning curve.
Figure 13. The leamning
the original reward
their respective OpmnAl-Gym versions (Brockman et al., 2016); however, we adjusted the rewards to be sparse, receiving r = 1000 only upon achieving specific goals. The agent in the source task navigates through a linear sequence of states to reach point F, carning a sparse reward equivalent to Equation. 12. At each state, the agent has four possible actions: move left, move right, move up, and move down. The generated reward machine and the cross-domain reward transfer process
19

---

Reward Translation via Reward Machine in Semi-Alignable MDPs
SAC
Cunshhitve Mese
6.0 0.50
125
6.55
Stego
Figure 14, Learning curve for Mujoco-Ant on SAC method
from NChain to Mujoco are depicted in Figure. 7(b). The source task's s reward machine and target tasks' reward machines are homomorphic reward machines. Our analysis suggests that the reward signal from the souree task also provides guidance for the target tasks, similar to the NChain game experiment. Besides, compare the generated reward machine based on LLM and the hand-designed reward machine shown in Figure. 2(b), the reward machine generated by LLM maintains a same structure of the desinne reward machine, which shows the effectiveness of the reward machine generator based on LLM. The learning results are shown in Figure. 13. We still chose PPO the baseline. PPO-RM, PPO-NRT(Reward) and PPO-NRT(RM--Reaal to perform ablation study exclude potential influences due reward machine utilization. Our results demonstrate that in extremely sparse reward tasks, merely extending observation with reward machine information proves insufficient; in contrast, using transferred rewards significantly alleviates the sparse reward issue, enhancing learning performance. In Hopper-v3 and Ant-v3 tasks, (Rewar)(R)ewrr)) achieves the best results, while HalfCheetah-v3 tasks, (RO-NRTTRRwarddRRM) and (Rewar)())earr) attains similar performance.
To further show the versatility of NRT, we have expanded our experiments include SAC (Soft Actor-Critic) as additional baseline for the Mujoco tasks. The result is shown in Figure 14.
20


Reviews:
[{"review_id": "k1ZwRM616X", "reviewer": "Reviewer_H5bA", "summary": "The paper introduces the Neural Reward Translation (NRT) framework, a novel methodology designed to transfer knowledge from completing a task in one environment to quickly learning to solve a (sufficiently similar) task in another environment. For example, NRT can transfer knowledge gained from completing a task in a grid with discrete actions to learning how to solve a similar task in a 3D environment with continuous actions. To achieve this, NRT utilizes the optimal value function of the original task (e.g., the grid world) to shape the reward for the target task (e.g., the 3D environment). Furthermore, the paper formally defines the concept of semi-alignable MDPs. Based on this definition, the authors demonstrate the conditions under which NRT can be used to transfer knowledge from one MDP to another.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your thoughtful review and constructive feedback on our NRT paper. We have updated the additional experiment in:\nhttps://drive.google.com/file/d/1_U1d13bM4kG1reHUdx2wkLNb9zfn4otS/view?usp=sharing\n(Due to time constraints, many supplementary experiments could not be run with multiple groups to account for variance effects.）\nYour suggestions will certainly strengthen our work, and we address each point below: \n## 1. Regarding testing NRT beyond sequential tasks\nThank you for this valuable suggestion. While the NChain to Mujoco task does contain a basic disjunction (at point C, the agent can choose to go to point G or point D), we acknowledge this implementation is relatively simple.\nWe have now expanded our evaluation by modifying the Text-Sign task to incorporate more complex disjunctions. In this enhanced environment, we added a \"trap\" mechanism where the agent receives a -10 reward and terminates the episode if it falls into the trap at any point. From a reward machine perspective, this modification adds a branch from each state (U0, U1, U2, U3) to a terminal failure state, creating multiple disjunctive paths through the task. The environment diagram and transferred reward machine is shown in Figure 1 and Figure 2 in the additional experiment.\nOur results (shown in Figure 3 in the additional experiment) demonstrate that NRT continues to show significant performance improvements when transferring the reward machine and corresponding rewards from the original Text-Sign task, even with these more complex logical structures.\n## 2. Additional baselines (naive reward)\nWe agree that additional baselines strengthen our evaluation. We implemented a naive reward approach on the Sign task (shown in Figure 5 in the additional experiment, where each time the agent take one thing, it will get a reward +10), where the agent receives supplementary rewards when making progress toward the goal. The results (available in our supplementary materials) show that while naive reward shaping does improve performance compared to sparse rewards, there remains a substantial performance gap when compared to our NRT method with transferred reward machines.\nThis comparison highlights that while simple reward shaping can help, the structured knowledge transfer facilitated by NRT provides more substantial benefits for learning efficiency. The transferred reward structure itself inherently contains this shaping information but in a more principled way that captures the logical dependencies between subtasks, which explains the superior performance of our approach.\n## 3. On automated reward machine generation\nThank you for highlighting this concern. We want to clarify that our primary contribution is the reward translation framework (cross-domain reward transfer), with reward machines serving as the bridge for this translation process.\nIcarte et al.'s work on automated reward machines is indeed excellent, formulating a combinatorial optimization problem for reward machine construction. However, solving this requires substantial data and computational resources. Our LLM-based approach to generating reward machines is admittedly more similar to human specification but offers practical automation benefits.\nWe agree that combining Icarte's automated reward machine learning with our reward translation framework represents a promising direction for end-to-end learning. This integration would need to address challenges like limited trajectory data in target tasks and modeling complexities in continuous action spaces like Mujoco. But it is far from what this paper aims to discuss.\n## 4. Clarification on propositional symbols (P) and definition 3.1\nWe apologize for any confusion regarding our notation. P represents the set of propositional symbols, expressed as textual predicates (e.g., \"c\" or \"!c\" indicating whether the agent has or hasn't reached point c). The notation 2^P refers to the power set of these symbols, representing all possible truth assignments. We should have used 2^|P| for clarity, and we will correct this in the camera-ready version if accepted. The function Pr in Definition 3.1 is a deterministic function that indicates which new abstract state (equivalently, which reward machine state) the agent will transition to when selecting a particular skill from its current abstract state.\n\nWe sincerely thank you for your thoughtful review and hope our responses address your concerns.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Overall, I believe the experimental evaluation is solid. However, I have two concerns regarding the experiments.\n\n1) I find it somewhat disappointing that NRT was tested only on sequential tasks. It would have been great to see tasks that include disjunctions, conjunctions, or cycles (beyond self-loops). That said, I don’t believe there’s any reason the proposed method wouldn’t perform well in those cases as well.\n\n2) I find it challenging to assess the merits of the proposed method without additional baselines. For example, we could shape the reward function by providing extra rewards whenever the agent makes progress in the task (i.e., moves closer to the terminal state in the RM). I believe that such a baseline could be competitive with the proposed method, and it is straightforward to implement.", "theoretical_claims": "The definitions and theorems appear correct to me. However, I have a couple of comments, which are discussed below.", "experimental_designs_or_analyses": "Yes, the experimental design and analysis are sound.", "relation_to_broader_scientific_literature": "The paper explains that previous attempts to transfer rewards would not be effective with incompatible MDPs (which are non-pairable and non-time-alignable). However, it does not connect to the literature on automated reward shaping or the literature on intrinsic motivation. I believe that any method altering the reward function could serve as a valid alternative for using NRT.", "essential_references_not_discussed": "I think all the important works are being discussed.", "other_strengths_and_weaknesses": "Overall, I think this is a solid paper. It explores an important issue: how to transfer knowledge from one domain to another. To do so, it formally defines semi-alignable MDPs and then uses RMs to develop a practical algorithm. The results, although limited to sequential tasks, show that this novel method can work well in practice.\n\nI only have two minor concerns about this work:\n\n1. The paper discusses the potential use of LLMs to automatically generate an RM. However, I wouldn’t consider this a major contribution of the work because the method itself is not well explained, and it is unclear whether it would be effective in a different domain.\n\n2. I suspect that a simple reward shaping technique could perform just as well as the proposed method for the sequential tasks tested in the paper. As such, the experimental section would be more compelling if it assessed other types of tasks, particularly those involving cycles or disjunctions. Additionally, I believe that incorporating a naive reward shaping method as a baseline would enhance the paper. Even a straightforward approach, such as giving a reward of +100 every time the agent makes progress on the task, would help better evaluate the effectiveness of the proposed method.", "other_comments_or_suggestions": "I suggest better explaining $\\Pr^B$ in Section 3.2. Currently, it just states that it “_denotes the transition on goal._” However, if I understand correctly, it represents a probability from $B \\times W$ to $\\Pr(B)$. If that is the case, please make that explicit. Also, I find it strange that in Definition 3.1 the paper states that $\\Pr^B_y(b_y,w_y) = \\phi(\\Pr^B_x(b_x,w_x))$ because that implies that $\\Pr^B_x(b_x,w_x)$ is actually a deterministic function (not a probability distribution) that returns one state $b \\in B_x$ (since $\\phi$ was defined as a function from $B_x$ to $B_y$). \n\nIn Sections 3.3 and 4, I am confused by the meanings of $P$, $\\mathcal{P}$ and $2^{\\mathcal{P}}$. Usually, $\\mathcal{P}$ refers to the set of propositional symbols and $2^{\\mathcal{P}}$ is a truth value assignment to each of those symbols. So, for instance, in one transition, symbols $a$ and $b$ could hold at the same time. Thus, the definition of $\\delta_u$ in an RM goes from $U \\times 2^{\\mathcal{P}} \\mapsto U$. But the paper defines them in terms of $U \\times P \\mapsto U$. So, I don’t know if that is a typo, or if $P$ is used as shorthand notation for $2^{\\mathcal{P}}$. Then in Theorem 3.5, I think $\\Gamma_x$ should go from $2^{\\mathcal{P}_x}$ to $W_x$ because in every RM transition, multiple propositions might hold at once.", "questions_for_authors": "1. If we use a naive reward shaping technique, such as always providing an extra reward for making progress on the task—or something similar to the automated reward shaping method proposed by Icarte et al. (2022)—would that work similarly to the proposed method? Or would NRT work better? Why?\n\n2. In what way is the proposed method superior to the automated reward shaping suggested by Icarte et al. (2022)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kLRMGR0Z7h", "reviewer": "Reviewer_i3La", "summary": "This paper proposes a way to derive reward functions for cross domain transfer learning. This is achieved via reward machines for obtaining a transferable reward in semi-align MDPs. Experiments conducted on 3D visual navigation and a few Mujoco tasks demonstrate the benefits when agents are learned with PPO.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our paper. We appreciate your careful reading and questions, which help us improve the clarity and rigor of our work. We have updated the additional experiment in: https://drive.google.com/file/d/1_U1d13bM4kG1reHUdx2wkLNb9zfn4otS/view?usp=sharing\n(Due to time constraints, many supplementary experiments could not be run with multiple groups to account for variance effects.）\n## 1. Regarding the HalfCheetah example in Fig 1\nWe apologize for any confusion in our presentation. To clarify, we have modified the standard Mujoco environments to create goal-oriented tasks that better demonstrate our cross-domain transfer approach. For the HalfCheetah environment, we defined checkpoints along the x-axis, with point F specifically representing when the robot's position exceeds x=8. This task definition follows similar approaches in Icarte et al.'s work Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning (which we have cited).\nThe key difference from the standard HalfCheetah environment is that we use a sparse reward structure where the agent receives a reward only upon task completion (reaching point F), with the reward magnitude depending on the number of steps taken. This contrasts with the original dense reward setting that provides control and forward rewards at each step. This sparse reward formulation makes the task more challenging to learn but better demonstrates the value of our approach.\n## 2. Regarding condition (b-dynamic) in Definition 3.1\nThank you for requesting clarification on this point. The essence of this definition relates to our abstraction of environments into subgoals and skills, creating a coarser granularity than the standard RL state-action level.\nTo elaborate: in environments like our Text-Sign task, the agent must collect specific items in sequence to complete the task. Each item collection represents a subgoal, and the process of achieving that subgoal constitutes a skill. This abstraction doesn't consider the specific actions or states involved in executing the skill (which would be fine-grained), focusing instead on the higher-level completion of subgoals.\nThe mappings φ and η represent these coarse-grained alignments of subgoals and skills between source domain X and target domain Y. Our \"semi-alignment\" concept acknowledges that fine-grained alignment between domains is often infeasible, but partial reward reuse through these higher-level mappings remains valuable. In our implementation, this is achieved through reward machine states and propositional symbols mappings. The function Pr in Definition 3.1 is a deterministic function that indicates which new abstract state (equivalently, which reward machine state) the agent will transition to when selecting a particular skill from its current abstract state.\n## 3. Regarding Definition 3.3 and domain notation\nWe sincerely apologize for this notational error. You are correct that in Definition 3.3, \"x\" should be \"A\" (representing the action space), not the source domain. This is indeed a typographical error that we will correct in the final version.\n## 4. Regarding experimental concerns\nThe core contribution of our work is enabling reward translation for cross-domain transfer, with reward machines as the bridging mechanism. Our experiments focus on transferring knowledge from simpler tasks (e.g., NChain) to more complex target domains, demonstrating how fundamental task structures can inform learning in challenging environments.\n\nWe carefully selected tasks to highlight our approach’s effectiveness in both isomorphic and homomorphic reward machine settings, specifically addressing semi-alignable MDPs—an area insufficiently explored in prior work. Beyond Mujoco, we also validated our method in a significantly different domain: transferring from Text-Sign to 3D-Sign, where first-person navigation with sparse rewards poses a unique challenge.\n\nRegarding Mujoco transfers (e.g., HalfCheetah to Ant), our method is applicable but unnecessary from a motivation standpoint. These environments share the same reward machines, and existing work (e.g., Raychaudhuri et al. Cross-domain Imitation from Observations) has already demonstrated effective cross-domain transfer for alignable MDPs (They also transfer HalfCheetah to Ant). Since our approach abstracts reward structures rather than leveraging shared state-action similarities, it does not offer additional benefits in such cases. That said, due to their inherent similarity, even with our method, performance would be better than in NChain.\n\nWe believe these clarifications address your concerns and hope they provide a clearer understanding of our approach and its contributions. We thank you for your valuable feedback, which will help us improve the presentation of our work.", "claims_and_evidence": "The claims of this paper are around developing the foundations for reward translations and semi-alignable MDPs which are defined in the Section 3 and 4.", "methods_and_evaluation_criteria": "The paper evaluates on 3 tasks from Mujoco (HalfCheetah, Ant and Hopper) and on 3D visual navigation based on Mini`world.", "theoretical_claims": "The 2) condition in Definition 3.1 seems off. As the $\\phi$ is applied over the transition function $Pr$. The theorem 3.5 looked fine. I did not check Theorem 4.5 closely.", "experimental_designs_or_analyses": "The experiments on Mujoco tasks are not convincing enough. The source domain is a NChain environment where the agent needs to reach a point F and is used to define a reward for target domain where the Ant / HalfCheetah needs to reach point F. This is a relatively simple task. What if the source task is more harder? Given that the paper uses LLMs (as described in Sec 4), will the method work when the source domain in HalfCheetah and the target domain is Ant.", "relation_to_broader_scientific_literature": "The idea of recovering a reward function that can be transferred across domains is challenging. However, the experiments are not convincing enough.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. The example in Fig 1 is not convincing. In the Half-Cheetah environment, the is run / walk with a certain speed and not to reach a point F as in NChain. How are these two tasks related and how is Point F defined in HalfCheetah environment?\n\n2. The second condition (b-dynamic) in Def 3.1 is not clear to me. How does the function $\\phi$ applies to $Pr^B$ as this is a transition function and should return probabilities?\n\n3. In Definition 3.3, how the action domain x is used in defining the Reward Machine? It is mentioned, but not used anywhere. Why x is a action domain, in Sec 3.1 X is defined as a source domain?\n\n4. What if instead of NChain, a cheetah task where the agent has to reach the point F is used for transfer such that the Ant reaches a point F?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rqr0yTj4SJ", "reviewer": "Reviewer_18Bw", "summary": "This paper considers a setup where we want to transfer the reward from source domain to the target domain so that we can train RL agents in target domain where the reward design is tedious or difficult. But this will be difficult for many source-target domains because many domains don't share the same structure. So the paper introduces the idea of using the concept of semi-alignable MDP -- by designing a method that first generates reward machine and transferring the reward machine. Experiments are conducted on some simple 3D visual navigation tasks and OpenAI Gym tasks.\n\n## update after rebuttal\n\nMy score is updated from 2 to 3 to reflect that authors provided additional experiments in the rebuttal. I recommended authors to provide further diverse experiments if the paper is accepted.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our paper. We appreciate your feedback and the opportunity to address your concerns regarding our approach and experimental results. We have updated the additional experiment in: \nhttps://drive.google.com/file/d/1_U1d13bM4kG1reHUdx2wkLNb9zfn4otS/view?usp=sharing\n(Due to time constraints, many supplementary experiments could not be run with multiple groups to account for variance effects.）\n## 1. Regarding baseline and experiment design.\nWe appreciate this concern about our algorithmic choices. We must emphasize that our paper's primary contribution is not proposing a superior RL algorithm, but rather enabling cross-domain reward reuse - the RL method simply serves to validate our reward transfer effectiveness and should avoid excessive additional techniques. From this perspective, we selected PPO for several reasons:\n1.\tPPO is a widely-used, reliable algorithm that doesn't introduce additional techniques that might confound our results.\n2.\tUsing a consistent algorithm across most environments allowed for standardized experimentation.\n3.\tPPO's compatibility with both discrete and continuous action spaces facilitated unified testing methodology.\nWe should clarify that our baselines aren't limited to PPO alone - our Nchain2Nchain experiments utilized DQN. Additionally, to address your concern, we have expanded our experiments to include SAC (Soft Actor-Critic) as an additional baseline for the Mujoco tasks.The result is shown in Figure 4 in the additional experiment. These new results, included in our supplementary materials, demonstrate that our method's benefits are consistent across different RL algorithms, strengthening the generality of our approach.\nOur experimental design deliberately demonstrates knowledge transfer from simpler source tasks to more complex target domains, showing how fundamental task structures can inform learning in challenging environments. We carefully selected tasks to demonstrate effectiveness with both isomorphic and homomorphic reward machines, specifically addressing semi-alignable MDPs - a challenge inadequately addressed in previous research.\n\nBeyond MuJoCo, our Text-Sign to 3D-Sign transfer experiments validate our approach in first-person navigation with sparse rewards. To address concerns about reward structure, we ran additional experiments with naive reward shaping (Figure 5 in additional experiment). While simple shaping improves performance, our NRT method still outperforms by capturing logical dependencies between subtasks, providing more principled guidance.\n\n## 2. Regarding reward visualization and transfer\nOur reward machine diagrams already indicate transferred reward values directly, showing how values map between domains - a more intuitive representation than alternatives like heat maps. We provide a visualization example of the reward machine heatmap from NChain to MuJoCo, as given in the link below, for your reference and comparison.\nhttps://drive.google.com/file/d/1wPJJbeZjK6_6ZTib4JEaBnueIoMja6nU/view?usp=sharing\n\n## 3. Regarding performance in Mujoco environments\nYou correctly noted that PPO policies seem to struggle in our modified Gym tasks. This is by design - we modified the standard Mujoco environments to use sparse rewards, where agents only receive feedback upon reaching specific checkpoints (e.g., point F when x-position exceeds 8), rather than the dense rewards in the original environments that provide immediate feedback at every step.\nWe should emphasize that this checkpoint-based task setting for Mujoco environments has precedent in classical reward machine literature, specifically in Icarte et al.'s \"Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning.\" However, while Icarte et al. retained the control reward component from the original environments, we implemented a fully sparse reward setting to create a more challenging scenario that better highlights the benefits of our approach.\nThis sparse reward setting intentionally creates a challenging learning scenario that better demonstrates the value of our approach. Standard PPO struggles because most sampled trajectories contain no reward signal. Our NRT method, while still operating in a relatively sparse reward regime, provides more informative guidance through the transferred reward structure, helping overcome this exploration challenge.\n## 4. Regarding reward machine generation without LLMs\nWhile we used LLMs, alternatives include manual definition and Icarte et al.'s combinatorial optimization approach. We focused on the reward translation framework itself rather than reward machine generation, which could be explored in future work.\n\nThank you again for your valuable feedback, which has helped us strengthen both our presentation and experimental validation.", "claims_and_evidence": "Experimental results are very weak for supporing the claims made in the paper. Actually results are quite noisy and not significant so that it's difficult to see the trend.", "methods_and_evaluation_criteria": "For OpenAI Gym experiments, experiments are conducted on a bit of contrived setup where the reward is artificially made sparse. \n\nOne additional note is that PPO is not 'state-of-the-art' -- this is method from 2017! - and it is not clear why the proposed idea is evaluated only on PPO --  maybe having more experiments based on other backbone RL algorithms can make the results be more convincing.", "theoretical_claims": "I don't have an enough background / knowledge to thoroughly go through the proof.", "experimental_designs_or_analyses": "Again, the setup is a bit contrived and the paper should consider more backbone RL algorithms. Using the source domain of NChain is interesting but the paper can be made more stronger by considering more realistic scenarios of considering more 'relevant yet different' domains other than NChain domain.", "relation_to_broader_scientific_literature": "Reward translation is an interesting idea that can be useful for many scenarios, but the current method is a bit too complex and does not have promising results yet.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Other strengths\n- Related work was very useful in understanding relevant works\n\nOther weaknesses\n- The paper is a bit weak in providing a motivation. It could be nice to provide a trivial example where it is easy to transfer rewards and it is hugely beneficial.", "other_comments_or_suggestions": "The authors may want to check how they should write double quote in latex", "questions_for_authors": "- Would it be possible to provide experimental results on a more 'natural' setup where the reward is not artificially removed from the task? Removing the reward at all, thus making PPO baseline entirely fail, and then showing that the proposed idea can work may not be an ideal way of showing the promise of reward transition.\n- It seems to me that PPO policies are all stuck in local minima for OpenAI Gym tasks -- is there a particular reason for this?\n- Regarding the above point, is there any qualitative analysis that shows which reward is transferred?\n- Would there be a way to generate reward machines without using LLMs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The submission focuses on an important problem of how to transfer knowledge from one domain to another. The authors focus on this by formally defining semi-alignable MDPs and then uses reward machines to develop a practical algorithm. The results, although limited to sequential tasks, show that this novel method can work well in practice.

There were reviewer concerns about a lack of comparison to other reward shaping baselines and the environments being too simplistic. However, it does appear as though the environments were designed to test the assumptions posed in the work, and I believe the contribution of transfer in a theoretically motivated semi-alignable MDP setting is significant.
Decision: Accept (poster)