Author name cluster

Toryn Q. Klassen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers

2 author rows

AAAI Conference 2026 Conference Paper

Satisficing and Optimal Generalised Planning via Goal Regression

Dillon Z. Chen
Till Hofmann
Toryn Q. Klassen
Sheila A. McIlraith

Generalised planning (GP) refers to the task of synthesising programs that solve families of related planning problems. We introduce a novel, yet simple method for GP: given a set of training problems, for each problem, compute an optimal plan for each goal atom in some order, perform goal regression on the resulting plans, and lift the corresponding outputs to obtain a set of first-order Condition → Actions rules. The rules collectively constitute a generalised plan that can be executed as is or alternatively be used to prune the planning search space. We formalise and prove the conditions under which our method is guaranteed to learn valid generalised plans and state space pruning axioms for search. Experiments demonstrate significant improvements over state-of-the-art (generalised) planners with respect to the 3 metrics of synthesis cost, planning coverage, and solution quality on various classical and numeric planning domains.

PDF Details DOI

PRL Workshop 2025 Workshop Paper

MOOSE: Satisficing and Optimal Generalised Planning via Goal Regression

Dillon Ze Chen
Till Hofmann
Toryn Q. Klassen
Sheila A. McIlraith

Generalised planning (GP) refers to the task of synthesising programs that solve families of related problems. We introduce a novel, yet simple method for GP: given a set of training problems, compute a plan for each single goal atom optimally in some order for each problem, perform goal regression on the resulting plans, and lift the corresponding partial-state, macro-action pairs to obtain a set of first-order rules. The lifted rules can be executed as is, or encoded as planning axioms for state space pruning during search. We formalise and prove the conditions under which this method is guaranteed to learn sound and complete generalised plans, and state space pruning axioms returns optimal plans when used in search. Experiments demonstrate significant improvements over state-of-the-art (generalised) planners with respect to the 3 metrics of synthesis cost, planning coverage, and solution quality on various classical and numeric planning domains.

Details

KR Conference 2025 Conference Paper

Pushdown Reward Machines for Reinforcement Learning

Giovanni Varricchione
Toryn Q. Klassen
Natasha Alechina
Mehdi Dastani
Brian Logan
Sheila A. McIlraith

Reward machines (RMs) are automata structures that encode (non-Markovian) reward functions for reinforcement learning (RL). RMs can reward any behaviour representable in regular languages and, when paired with RL algorithms that exploit RM structure, have been shown to significantly improve sample efficiency in many domains. In this work, we present pushdown reward machines (pdRMs), an extension of reward machines based on deterministic pushdown automata. pdRMs can recognise and reward temporally extended behaviours representable in deterministic context-free languages, making them more expressive than reward machines. We introduce two variants of pdRM-based policies, one which has access to the entire stack of the pdRM, and one which can only access the top k symbols (for a given constant k) of the stack. We propose a procedure to check when the two kinds of policies (for a given environment, pdRM, and constant k) achieve the same optimal state values. We then provide theoretical results establishing the expressive power of pdRMs, and space complexity results for the proposed learning problems. Lastly, we propose an approach for off-policy RL algorithms that exploits counterfactual experiences with pdRMs. We conclude by providing experimental results showing how agents can be trained to perform tasks representable in deterministic context-free languages using pdRMs.

PDF Details DOI

ICML Conference 2024 Conference Paper

Remembering to Be Fair: Non-Markovian Fairness in Sequential Decision Making

Parand A. Alamdari
Toryn Q. Klassen
Elliot Creager
Sheila A. McIlraith

Fair decision making has largely been studied with respect to a single decision. Here we investigate the notion of fairness in the context of sequential decision making where multiple stakeholders can be affected by the outcomes of decisions. We observe that fairness often depends on the history of the sequential decision-making process, and in this sense that it is inherently non-Markovian. We further observe that fairness often needs to be assessed at time points within the process, not just at the end of the process. To advance our understanding of this class of fairness problems, we explore the notion of non-Markovian fairness in the context of sequential decision making. We identify properties of non-Markovian fairness, including notions of long-term, anytime, periodic, and bounded fairness. We explore the interplay between non-Markovian fairness and memory and how memory can support construction of fair policies. Finally, we introduce the FairQCM algorithm, which can automatically augment its training data to improve sample efficiency in the synthesis of fair policies via reinforcement learning.

Details

NeurIPS Conference 2024 Conference Paper

Reward Machines for Deep RL in Noisy and Uncertain Environments

Andrew C. Li
Zizhao Chen
Toryn Q. Klassen
Pashootan Vaezipoor
Rodrigo T. Icarte
Sheila A. McIlraith

Reward Machines provide an automaton-inspired structure for specifying instructions, safety constraints, and other temporally extended reward-worthy behaviour. By exposing the underlying structure of a reward function, they enable the decomposition of an RL task, leading to impressive gains in sample efficiency. Although Reward Machines and similar formal specifications have a rich history of application towards sequential decision-making problems, prior frameworks have traditionally ignored ambiguity and uncertainty when interpreting the domain-specific vocabulary forming the building blocks of the reward function. Such uncertainty critically arises in many real-world settings due to factors like partial observability or noisy sensors. In this work, we explore the use of Reward Machines for Deep RL in noisy and uncertain environments. We characterize this problem as a POMDP and propose a suite of RL algorithms that exploit task structure under uncertain interpretation of the domain-specific vocabulary. Through theory and experiments, we expose pitfalls in naive approaches to this problem while simultaneously demonstrating how task structure can be successfully leveraged under noisy interpretations of the vocabulary.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Epistemic Side Effects: An AI Safety Problem

Toryn Q. Klassen
Parand Alizadeh Alamdari
Sheila A. McIlraith

AI safety research has investigated the problem of negative side effects – undesirable changes made by AI systems in pursuit of an underspecified objective. However, the focus has been on physical side effects, such as a robot breaking a vase while moving (when the objective makes no mention of the vase). In this paper we introduce the notion of epistemic side effects, which are side effects on the knowledge or beliefs of agents. Epistemic side effects are most pertinent in a (partially observable) multiagent setting. We show that we can extend an existing approach to avoiding (physical) side effects in reinforcement learning to also avoid some epistemic side effects in certain cases. Nonetheless, avoiding negative epistemic side effects remains an important challenge, and we identify some key research problems.

PDF

ICML Conference 2023 Conference Paper

Learning Belief Representations for Partially Observable Deep RL

Andrew Wang
Andrew C. Li
Toryn Q. Klassen
Rodrigo Toro Icarte
Sheila A. McIlraith

Many important real-world Reinforcement Learning (RL) problems involve partial observability and require policies with memory. Unfortunately, standard deep RL algorithms for partially observable settings typically condition on the full history of interactions and are notoriously difficult to train. We propose a novel deep, partially observable RL algorithm based on modelling belief states — a technique typically used when solving tabular POMDPs, but that has traditionally been difficult to apply to more complex environments. Our approach simplifies policy learning by leveraging state information at training time, that may not be available at deployment time. We do so in two ways: first, we decouple belief state modelling (via unsupervised learning) from policy optimization (via RL); and second, we propose a representation learning approach to capture a compact set of reward-relevant features of the state. Experiments demonstrate the efficacy of our approach on partially observable domains requiring information seeking and long-term memory.

Details

AIJ Journal 2023 Journal Article

Learning reward machines: A study in partially observable reinforcement learning

Rodrigo Toro Icarte
Toryn Q. Klassen
Richard Valenzano
Margarita P. Castro
Ethan Waldie
Sheila A. McIlraith

Reinforcement Learning (RL) is a machine learning paradigm wherein an artificial agent interacts with an environment with the purpose of learning behaviour that maximizes the expected cumulative reward it receives from the environment. Reward machines (RMs) provide a structured, automata-based representation of a reward function that enables an RL agent to decompose an RL problem into structured subproblems that can be efficiently learned via off-policy learning. Here we show that RMs can be learned from experience, instead of being specified by the user, and that the resulting problem decomposition can be used to effectively solve partially observable RL problems. We pose the task of learning RMs as a discrete optimization problem where the objective is to find an RM that decomposes the problem into a set of subproblems such that the combination of their optimal memoryless policies is an optimal policy for the original problem. We show the effectiveness of this approach on three partially observable domains, where it significantly outperforms A3C, PPO, and ACER, and discuss its advantages, limitations, and broader potential. 1

Details DOI

KR Conference 2023 Conference Paper

Planning with Epistemic Preferences

Toryn Q. Klassen
Christian Muise
Sheila A. McIlraith

Within the field of automated planning, two areas of study are planning with preferences and epistemic planning. Planning with preferences involves generating plans that optimize for properties of the plan instead of, or in addition to, trying to reach a fixed goal. Epistemic planning allows for planning over the knowledge or belief states of one or more agents for the purpose of achieving epistemic goals (where agents have particular states of knowledge or belief). In this paper we motivate and explore the task of planning with epistemic preferences, proposing a method by which existing automated planning techniques can be combined for this purpose.

PDF Details DOI

HAXP Workshop 2023 Workshop Paper

Towards Human-Aware AI via Planning with Epistemic Preferences

Toryn Q. Klassen
Christian Muise
Sheila A. McIlraith

Details

AAMAS Conference 2022 Conference Paper

Be Considerate: Avoiding Negative Side Effects in Reinforcement Learning

Parand Alizadeh Alamdari
Toryn Q. Klassen
Rodrigo Toro Icarte
Sheila A. McIlraith

In sequential decision making – whether it’s realized with or without the benefit of a model – objectives are often underspecified or incomplete. This gives discretion to the acting agent to realize the stated objective in ways that may result in undesirable outcomes, including inadvertently creating an unsafe environment or indirectly impacting the agency of humans or other agents that typically operate in the environment. In this paper, we explore how to build a reinforcement learning (RL) agent that contemplates the impact of its actions on the wellbeing and agency of others in the environment, most notably humans. We endow RL agents with the ability to contemplate such impact by augmenting their reward based on expectation of future return by others in the environment, providing different criteria for characterizing impact. We further endow these agents with the ability to differentially factor this impact into their decision making, manifesting behaviour that ranges from self-centred to self-less, as demonstrated by experiments in gridworld environments.

PDF

AAAI Conference 2022 Conference Paper

Planning to Avoid Side Effects

Toryn Q. Klassen
Sheila A. McIlraith
Christian Muise
Jarvis Xu

In sequential decision making, objective specifications are often underspecified or incomplete, neglecting to take into account potential (negative) side effects. Executing plans without consideration of their side effects can lead to catastrophic outcomes – a concern recently raised in relation to the safety of AI. In this paper we investigate how to avoid side effects in a symbolic planning setting. We study the notion of minimizing side effects in the context of a planning environment where multiple independent agents co-exist. We define (classes of) negative side effects in terms of their effect on the agency of those other agents. Finally, we show how plans which minimize side effects of different types can be computed via compilations to cost-optimizing symbolic planning, and investigate experimentally.

PDF Details

ICAPS Conference 2022 Conference Paper

Resolving Misconceptions about the Plans of Agents via Theory of Mind

Maayan Shvo
Toryn Q. Klassen
Sheila A. McIlraith

For a plan to achieve some goal -- to be valid -- a set of sufficient and necessary conditions must hold. In dynamic settings, agents (including humans) may come to hold false beliefs about these conditions and, by extension, about the validity of their plans or the plans of other agents. Since different agents often believe different things about the world and about the beliefs of other agents, discrepancies may occur between agents' beliefs about the validity of plans. In this work, we explore how agents can use their Theory of Mind to resolve such discrepancies by communicating and/or acting in the environment. We appeal to an epistemic logic framework to allow agents to reason over other agents' nested beliefs, and demonstrate how epistemic planning tools can be used to resolve discrepancies regarding plan validity in a number of domains. Our work shows promise for human decision support as demonstrated by a user study that showcases the ability of our approach to resolve misconceptions held by humans.

Details

JAIR Journal 2022 Journal Article

Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning

Rodrigo Toro Icarte
Toryn Q. Klassen
Richard Valenzano
Sheila A. McIlraith

Reinforcement learning (RL) methods usually treat reward functions as black boxes. As such, these methods must extensively interact with the environment in order to discover rewards and optimal policies. In most RL applications, however, users have to program the reward function and, hence, there is the opportunity to make the reward function visible – to show the reward function’s code to the RL agent so it can exploit the function’s internal structure to learn optimal policies in a more sample efficient manner. In this paper, we show how to accomplish this idea in two steps. First, we propose reward machines, a type of finite state machine that supports the specification of reward functions while exposing reward function structure. We then describe different methodologies to exploit this structure to support learning, including automated reward shaping, task decomposition, and counterfactual reasoning with off-policy learning. Experiments on tabular and continuous domains, across different tasks and RL agents, show the benefits of exploiting reward structure with respect to sample efficiency and the quality of resultant policies. Finally, by virtue of being a form of finite state machine, reward machines have the expressive power of a regular language and as such support loops, sequences and conditionals, as well as the expression of temporally extended properties typical of linear temporal logic and non-Markovian reward specification.

PDF Details DOI

KR Conference 2020 Conference Paper

Changing Beliefs about Domain Dynamics in the Situation Calculus

Toryn Q. Klassen
Sheila A. McIlraith
Hector J. Levesque

Agents change their beliefs about the plausibility of various aspects of domain dynamics -- effects of physical actions, results of sensing, and action preconditions -- as a consequence of their interactions with the world. In this paper we propose a way to conveniently represent domain dynamics in the situation calculus to support such belief change. Furthermore, we suggest patterns to follow when writing the axioms that describe the effects of actions, and prove how these patterns can control the extent to which observations change the agent's beliefs about action effects. We also discuss the relation of our work to the AGM postulates for belief revision. Finally, we show how beliefs about domain dynamics can be incorporated into a form of regression rewriting to support reasoning.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

LTL and Beyond: Formal Languages for Reward Function Specification in Reinforcement Learning

Alberto Camacho
Rodrigo Toro Icarte
Toryn Q. Klassen
Richard Valenzano
Sheila A. McIlraith

In Reinforcement Learning (RL), an agent is guided by the rewards it receives from the reward function. Unfortunately, it may take many interactions with the environment to learn from sparse rewards, and it can be challenging to specify reward functions that reflect complex reward-worthy behavior. We propose using reward machines (RMs), which are automata-based representations that expose reward function structure, as a normal form representation for reward functions. We show how specifications of reward in various formal languages, including LTL and other regular languages, can be automatically translated into RMs, easing the burden of complex reward function specification. We then show how the exposed structure of the reward function can be exploited by tailored q-learning algorithms and automated reward shaping techniques in order to improve the sample efficiency of reinforcement learning methods. Experiments show that these RM-tailored techniques significantly outperform state-of-the-art (deep) RL algorithms, solving problems that otherwise cannot reasonably be solved by existing approaches.

PDF Details

KR Conference 2018 Conference Paper

Specifying Plausibility Levels for Iterated Belief Change in the Situation Calculus

Toryn Q. Klassen
Sheila A. McIlraith
Hector J. Levesque

We investigate augmenting a theory of belief and actions with qualitative plausibility levels. Shapiro et al. created a framework for modeling iterated belief revision and update which integrated those features with the well-developed theory of action in the situation calculus. However, applying their technique requires associating plausibility levels with initial situations, for which no very convenient mechanism had been proposed. Schwering and Lakemeyer proposed deriving these initial plausibility levels from a set of conditionals, similarly to how models are ranked in Pearl’s System Z. However, their approach inherits some limitations of System Z. We consider alternatives, and argue that a perspicuous approach is to measure plausibility by counting the abnormalities in a situation (similarly to cardinality-based circumscription). By allowing abnormalities to change over time, we can also model changing plausibility levels in a natural and simple way, which gives us a flexible approach for handling belief change about predicted and unpredicted exogenous actions.

AAMAS Conference 2018 Conference Paper

Teaching Multiple Tasks to an RL Agent using LTL

Rodrigo Toro Icarte
Toryn Q. Klassen
Richard Valenzano
Sheila A. McIlraith

This paper examines the problem of how to teach multiple tasks to a Reinforcement Learning (RL) agent. To this end, we use Linear Temporal Logic (LTL) as a language for specifying multiple tasks in a manner that supports the composition of learned skills. We also propose a novel algorithm that exploits LTL progression and offpolicy RL to speed up learning without compromising convergence guarantees, and show that our method outperforms the state-ofthe-art approach on randomly generated Minecraft-like grids.

PDF

ICML Conference 2018 Conference Paper

Using Reward Machines for High-Level Task Specification and Decomposition in Reinforcement Learning

Rodrigo Toro Icarte
Toryn Q. Klassen
Richard Valenzano
Sheila A. McIlraith

In this paper we propose Reward Machines {—} a type of finite state machine that supports the specification of reward functions while exposing reward function structure to the learner and supporting decomposition. We then present Q-Learning for Reward Machines (QRM), an algorithm which appropriately decomposes the reward machine and uses off-policy q-learning to simultaneously learn subpolicies for the different components. QRM is guaranteed to converge to an optimal policy in the tabular case, in contrast to Hierarchical Reinforcement Learning methods which might converge to suboptimal policies. We demonstrate this behavior experimentally in two discrete domains. We also show how function approximation methods like neural networks can be incorporated into QRM, and that doing so can find better policies more quickly than hierarchical methods in a domain with a continuous state space.

Details