Gheorghe Comanici

IJCAI Conference 2024 Conference Paper

Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search

• Abbas Mehrabian
• Ankit Anand
• Hyunjik Kim
• Nicolas Sonnerat
• Matej Balog
• Gheorghe Comanici
• Tudor Berariu
• Andrew Lee

This work proposes a new learning-to-search benchmark and uses AI to discover new mathematical knowledge related to an open conjecture of Erdos (1975) in extremal graph theory. The problem is to find graphs with a given size (number of nodes) that maximize the number of edges without having 3- or 4-cycles. We formulate this as a sequential decision-making problem and compare AlphaZero, a neural network-guided tree search, with tabu search, a heuristic local search method. Using either method, by introducing a curriculum---jump-starting the search for larger graphs using good graphs found at smaller sizes---we improve the state-of-the-art lower bounds for several sizes. We also propose a flexible graph-generation environment and a permutation-invariant network architecture for learning to search in the space of graphs.

NeurIPS Conference 2021 Conference Paper

Temporally Abstract Partial Models

• Khimya Khetarpal
• Zafarali Ahmed
• Gheorghe Comanici
• Doina Precup

Humans and animals have the ability to reason and make predictions about different courses of action at many time scales. In reinforcement learning, option models (Sutton, Precup & Singh, 1999; Precup, 2000) provide the framework for this kind of temporally abstract prediction and reasoning. Natural intelligent agents are also able to focus their attention on courses of action that are relevant or feasible in a given situation, sometimes termed affordable actions. In this paper, we define a notion of affordances for options, and develop temporally abstract partial option models, that take into account the fact that an option might be affordable only in certain situations. We analyze the trade-offs between estimation and approximation error in planning and learning when using such models, and identify some interesting special cases. Additionally, we empirically demonstrate the ability to learn both affordances and partial option models online resulting in improved sample efficiency and planning time in the Taxi domain.

ICML Conference 2020 Conference Paper

What can I do here? A Theory of Affordances in Reinforcement Learning

• Khimya Khetarpal
• Zafarali Ahmed
• Gheorghe Comanici
• David Abel
• Doina Precup

Reinforcement learning algorithms usually assume that all actions are always available to an agent. However, both people and animals understand the general link between the features of their environment and the actions that are feasible. Gibson (1977) coined the term "affordances" to describe the fact that certain states enable an agent to do certain actions, in the context of embodied agents. In this paper, we develop a theory of affordances for agents who learn and plan in Markov Decision Processes. Affordances play a dual role in this case. On one hand, they allow faster planning, by reducing the number of actions available in any given situation. On the other hand, they facilitate more efficient and precise learning of transition models from data, especially when such models require function approximation. We establish these properties through theoretical results as well as illustrative examples. We also propose an approach to learn affordances and use it to estimate transition models that are simpler and generalize better.

NeurIPS Conference 2019 Conference Paper

The Option Keyboard: Combining Skills in Reinforcement Learning

• Andre Barreto
• Diana Borsa
• Shaobo Hou
• Gheorghe Comanici
• Eser Aygün
• Philippe Hamel
• Daniel Toyama
• Jonathan hunt

The ability to combine known skills to create new ones may be crucial in the solution of complex reinforcement learning problems that unfold over extended periods. We argue that a robust way of combining skills is to define and manipulate them in the space of pseudo-rewards (or "cumulants"). Based on this premise, we propose a framework for combining skills using the formalism of options. We show that every deterministic option can be unambiguously represented as a cumulant defined in an extended domain. Building on this insight and on previous results on transfer learning, we show how to approximate options whose cumulants are linear combinations of the cumulants of known options. This means that, once we have learned options associated with a set of cumulants, we can instantaneously synthesise options induced by any linear combination of them, without any learning involved. We describe how this framework provides a hierarchical interface to the environment whose abstract actions correspond to combinations of basic skills. We demonstrate the practical benefits of our approach in a resource management problem and a navigation task involving a quadrupedal simulated robot.

NeurIPS Conference 2015 Conference Paper

Basis refinement strategies for linear value function approximation in MDPs

• Gheorghe Comanici
• Doina Precup
• Prakash Panangaden

We provide a theoretical framework for analyzing basis function construction for linear value function approximation in Markov Decision Processes (MDPs). We show that important existing methods, such as Krylov bases and Bellman-error-based methods are a special case of the general framework we develop. We provide a general algorithmic framework for computing basis function refinements which “respect” the dynamics of the environment, and we derive approximation error bounds that apply for any algorithm respecting this general framework. We also show how, using ideas related to bisimulation metrics, one can translate basis refinement into a process of finding “prototypes” that are diverse enough to represent the given MDP.

AAAI Conference 2015 Conference Paper

Representation Discovery for MDPs Using Bisimulation Metrics

• Sherry Ruan
• Gheorghe Comanici
• Prakash Panangaden
• Doina Precup

AAAI Conference 2015 Conference Paper

Representation Discovery for MDPs Using Bisimulation Metrics

• Sherry Ruan
• Gheorghe Comanici
• Prakash Panangaden
• Doina Precup

We provide a novel, flexible, iterative refinement algorithm to automatically construct an approximate statespace representation for Markov Decision Processes (MDPs). Our approach leverages bisimulation metrics, which have been used in prior work to generate features to represent the state space of MDPs. We address a drawback of this approach, which is the expensive computation of the bisimulation metrics. We propose an algorithm to generate an iteratively improving sequence of state space partitions. Partial metric computations guide the representation search and provide much lower space and computational complexity, while maintaining strong convergence properties. We provide theoretical results guaranteeing convergence as well as experimental illustrations of the accuracy and savings (in time and memory usage) of the new algorithm, compared to traditional bisimulation metric computation.

EWRL Workshop 2012 Conference Paper

An Empirical Analysis of Off-policy Learning in Discrete MDPs

• Cosmin Paduraru
• Doina Precup
• Joelle Pineau
• Gheorghe Comanici

Off-policy evaluation is the problem of evaluating a decision-making policy using data collected under a different behaviour policy. While several methods are available for addressing off-policy evaluation, little work has been done on identifying the best methods. In this paper, we conduct an in-depth comparative study of several off-policy evaluation methods in non-bandit, finite-horizon MDPs, using randomly generated MDPs, as well as a Mallard population dynamics model [Anderson, 1975]. We find that un-normalized importance sampling can exhibit prohibitively large variance in problems involving look-ahead longer than a few time steps, and that dynamic programming methods perform better than Monte-Carlo style methods.

AAMAS Conference 2011 Conference Paper

Basis Function Discovery using Spectral Clustering and Bisimulation Metrics

• Gheorghe Comanici
• Doina Precup

We study the problem of automatically generating features for function approximation in reinforcement learning. We build on the work of Mahadevan and his colleagues, who pioneered the use of spectral clustering methods for basis function construction. Their methods work on top of a graph that captures state adjacency. Instead, we use bisimulation metrics in order to provide state distances for spectral clustering. The advantage of these metrics is that they incorporate reward information in a natural way, in addition to the state transition information. We provide theoretical bounds on the quality of the obtained approximation, which justify the importance of incorporating reward information. We also demonstrate empirically that the approximation quality improves when bisimulation metrics are used instead of the state adjacency graph in the basis function construction process.

AAAI Conference 2011 Conference Paper

Basis Function Discovery Using Spectral Clustering and Bisimulation Metrics

• Gheorghe Comanici
• Doina Precup

We study the problem of automatically generating features for function approximation in reinforcement learning. We build on the work of Mahadevan and his colleagues, who pioneered the use of spectral clustering methods for basis function construction. Their methods work on top of a graph that captures state adjacency. Instead, we use bisimulation metrics in order to provide state distances for spectral clustering. The advantage of these metrics is that they incorporate reward information in a natural way, in addition to the state transition information. We provide theoretical bounds on the quality of the obtained approximation, which justify the importance of incorporating reward information. We also demonstrate empirically that the approximation quality improves when bisimulation metrics are used instead of the state adjacency graph in the basis function construction process.

AAMAS Conference 2010 Conference Paper

Optimal Policy Switching Algorithms for Reinforcement Learning

• Gheorghe Comanici
• Doina Precup

We address the problem of single-agent, autonomous sequentialdecision making. We assume that some controllers or behaviorpolicies are given as prior knowledge, and the task of the agentis to learn how to switch between these policies. We formulate theproblem using the framework of reinforcement learning and options (Sutton, Precup & Singh, 1999; Precup, 2000). We derivegradient-based algorithms for learning the termination conditionsof options, with the goal of optimizing the expected long-term return. We incorporate the proposed approach into policy-gradientmethods with linear function approximation.