Provably Efficient Reward Transfer in Reinforcement Learning with Discrete Markov Decision Processes

Kevin Vora [email protected], Yu Zhang [email protected] · 2025

Read Provably Efficient Reward Transfer in Reinforcement Learning with Discrete Markov Decision Processes by Kevin Vora [email protected], Yu Zhang [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-13414.txt.

Introduction

Kevin Vora and Yu Zhang present a method for reusing learned behavior in a 2025 paper. In reinforcement learning, an agent learns by trial and error under a reward rule. When the reward rule changes, retraining from scratch wastes what the agent already knows. Their method adapts old behavior to a new reward rule that is a known mix of the old ones.

The method, called Q-Manipulation, works directly on the agent's value table. It first builds upper and lower bounds for the new values, then tightens them with repeated passes that mimic standard value updates. Those bounds let the agent prune bad actions before learning even starts. Proofs show the method keeps the best final policy and uses samples well. Tests in toy and simulated worlds show the adapted agent learns faster than one starting cold.

Catalog record

CREATORKevin Vora [email protected], Yu Zhang [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-13414

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Provably Efficient Reward Transfer in Reinforcement Learning with Discrete Markov Decision Processes Kevin Vora [email protected], Yu Zhang [email protected] Abstract In this paper, we propose a new solution to reward adaptation (RA) in reinforcement learning, where the agent adapts to a target reward function based on one or more existing source behaviors learned a priori under the same domain dynamics but different reward functions. While learning the target behavior from scratch is possible, it is often inefficient given the available source behaviors. Our work introduces a new approach to RA through the manipulation of Q-functions. Assuming the target reward function is a known function of the source reward functions, we compute bounds on the Q-function and present an iterative process (akin to value iteration) to tighten these bounds. Such bounds enable action pruning in the target domain before learning even starts. We refer to this method as “ Q-Manipulation ” (Q-M). The iteration process assumes access to a lite-model, which is easy to provide or learn. We formally prove that Q-M, under discrete domains, does not affect the optimality of the returned policy and show that it is provably efficient in terms of sample complexity in a probabilistic sense. Q-M is evaluated in a variety of synthetic and simulation domains to demonstrate its effectiveness, generalizability, and practicality. 1 Introduction Reinforcement Learning (RL) as described by Watkins (1989) ; Sutton & Barto (2018) represents a class of learning methods that allow agents to learn from interacting with the environment. RL has demonstrated great successes in various domains such as games like Chess in Campbell et al. (2002) , Go in Silver et al. (2016) , and Atari games in Mnih et al. (2015) , logistics in Yan et al. (2022) , biology in Angermueller et al. (2019) , and robotics in Kober et al. (2013) . However, applying RL to many real-world problems still suffers from the issue of high sample complexity. Prior approaches have been proposed to alleviate the issue from different perspectives, such as learning optimization, transfer learning, modular and hierarchical RL, and offline RL. However, few methods provably improve sample complexity. Figure 1 : Dollar-Euro domain. The problem of reward adaptation (RA) was first introduced and addressed by Barreto et al. (2017) ; Barreto et al. (2020) , where the learning agent adapts to a target reward function given one or multiple existing behaviors learned a priori (referred to as the source behaviors) under the same actions and transition dynamics but different reward functions. RA has many useful applications, such as enabling a vehicle’s driving behavior from two known behaviors (comfortable driving with passengers and fast driving for goods delivery) to a new target behavior that combines comfort and speed, accommodating both passengers and goods. Featuring such a special type of transfer learning, RA methods can benefit from an ever-growing repertoire of source behaviors to create new and potentially more complex target behaviors. Learning the target behavior from scratch via model-free methods is possible but often inefficient given the available source behaviors, while model-based methods are prone to model error, e.g., due to uneven exploration of the state space when learning the source behaviors. In this paper, we present a new approach that takes the advantage of both sides while avoiding their limitations to bridge the gap for RA. This lite-model offers complimentary benefits with respect to the previous work. To better conceptualize the RA problem, consider a grid-world as shown in Fig. 1 , which is an expansion of the Dollar-Euro domain described by Russell & Zimdars (2003) . In this domain, the agent can move to any of its adjacent locations at any step. The agent’s initial location is colored in yellow, and the terminal locations are colored pink or green, which correspond to the source reward functions (i.e., collecting dollars and euros), respectively. Visiting the terminal location with a single color returns a reward of 1.0 under the corresponding reward function, and visiting the terminal location with split colors returns a reward of 0.6 under both reward functions. A target domain may correspond to a reward function that awards both dollars and euros. RA is most efficient when the source and target domains feature reward functions that are correlated. For example, an assumption was made in Successor Feature Q-Learning (SFQL) Barreto et al. (2017) ; Barreto et al. (2020) where the reward functions are expressed as feature weights. An advantage of this assumption is that the source behaviors can be evaluated easily under the target domain. SFQL can be viewed as combining the best parts of the source behaviors to initialize learning. Consequently, SFQL may not work well for situations where the target behavior differs substantially from the source behaviors, such as in the Dollar-Euro domain. Our proposed approach, on the other hand, represents a more general knowledge transfer method whose efficacy does not rely on the similarity between the source and target behaviors. Soft Q Bounding (SQB) Adamczyk et al. (2024) establishes double sided bounds of the Q function to speed up learning by clipping overly optimistic or pessimistic updates. When viewed as a method for RA, it relies on a given Q function computed from source behaviors. Even though the idea of computing the bounds bears some similarity to our work, SQB does not exploit the source behaviors during target learning, resulting in unpredictable performance due to reliance on samples. Our approach to RA is referred to as “ Q-Manipulation ” (Q-M). In this paper, we focus on discrete Markov Decision Processes (MDPs) for a theoretical treatment. Challenges in addressing continuous MDPs are discussed in Section 5 , with directions outlined for future work. Similar to prior work on RA, we assume the relationship between the source reward functions and the target reward function is known, and in our case, via what is referred to as a combination function . The intuition here is that we often have a good idea about the functional relationship (potentially noisy) between the source and target reward functions, e.g., linear in the Dollar-Euro domain. Based on such a relationship, Q-M computes an upper and lower bound of the Q-function in the target domain via an iterative process similar to value iteration. This process operates on a lite-model of the transition function that is easier to provide or estimate while learning the source behaviors. The output bounds enable us to prune actions before learning the target behavior, without affecting its optimality. In our evaluation, we empirically show that the effectiveness of Q-M across simulated and randomly generated domains, and also analyze its limitations. In general, Q-M operates under additional computation and space requirements that are reasonable to implement in practice, with its benefits to sample complexity outweighing these costs. For a comprehensive comparison between Q-M and competing transfer learning approaches, refer to table 1 . Our core contributions are: We address the problem of reward adaptation (RA) via Q-Manipulation (Q-M) in domains with discrete state and action spaces, and demonstrate that Q-M is provably efficient to sample complexity due to action pruning, and represents a new approach to RA that supports more general knowledge transfer than the previous work. We introduce two methods that both leverage a lite-model for

Read the complete text