Roni Khardon

NeurIPS Conference 2025 Conference Paper

Improving planning and MBRL with temporally-extended actions

• Palash Chatterjee
• Roni Khardon

Continuous time systems are often modeled using discrete time dynamics but this requires a small simulation step to maintain accuracy. In turn, this requires a large planning horizon which leads to computationally demanding planning problems and reduced performance. Previous work in model-free reinforcement learning has partially addressed this issue using action repeats where a policy is learned to determine a discrete action duration. Instead we propose to control the continuous decision timescale directly by using temporally-extended actions and letting the planner treat the duration of the action as an additional optimization variable along with the standard action variables. This additional structure has multiple advantages. It speeds up simulation time of trajectories and, importantly, it allows for deep horizon search in terms of primitive actions while using a shallow search depth in the planner. In addition, in the model-based reinforcement learning (MBRL) setting, it reduces compounding errors from model learning and improves training time for models. We show that this idea is effective and that the range for action durations can be automatically selected using a multi-armed bandit formulation and integrated into the MBRL framework. An extensive experimental evaluation both in planning and in MBRL, shows that our approach yields faster planning, better solutions, and that it enables solutions to problems that are not solved in the standard formulation.

PRL Workshop 2025 Workshop Paper

Planning with temporally-extended actions

• Palash Chatterjee
• Roni Khardon

Continuous time systems are often modeled using discrete time dynamics but this requires a small simulation step to maintain accuracy. In turn, this requires a large planning horizon which leads to computationally demanding planning problems and reduced performance. Previous work, using action repeats, has partially addressed this issue in the context of model free reinforcement learning where a policy is learned to determine a discrete action duration. Instead we propose to control the continuous decision timescale directly by letting the planner treat the duration of the action as an additional optimization variable along with the standard action variables. This additional structure has multiple advantages. It speeds up simulation time of trajectories and, importantly, it allows for deep horizon search in terms of primitive steps while using a shallow search depth in the planner. In addition, in the model based reinforcement learning (MBRL) setting, it reduces compounding errors from model learning and improves training time for models. We provide an experimental evaluation both in planning and in MBRL, showing that our approach yields faster planning, better solutions, and that it enables solutions to problems that are not solved in the standard formulation.

TMLR Journal 2024 Journal Article

Variational Inference on the Final-Layer Output of Neural Networks

• Yadi Wei
• Roni Khardon

Traditional neural networks are simple to train but they typically produce overconfident predictions. In contrast, Bayesian neural networks provide good uncertainty quantification but optimizing them is time consuming due to the large parameter space. This paper proposes to combine the advantages of both approaches by performing Variational Inference in the Final layer Output space (VIFO), because the output space is much smaller than the parameter space. We use neural networks to learn the mean and the variance of the probabilistic output. Using the Bayesian formulation we incorporate collapsed variational inference with VIFO which significantly improves the performance in practice. On the other hand, like standard, non-Bayesian models, VIFO enjoys simple training and one can use Rademacher complexity to provide risk bounds for the model. Experiments show that VIFO provides a good tradeoff in terms of run time and uncertainty quantification, especially for out of distribution data.

IJCAI Conference 2023 Conference Paper

DiSProD: Differentiable Symbolic Propagation of Distributions for Planning

• Palash Chatterjee
• Ashutosh Chapagain
• Weizhe Chen
• Roni Khardon

The paper introduces DiSProD, an online planner developed for environments with probabilistic transitions in continuous state and action spaces. DiSProD builds a symbolic graph that captures the distribution of future trajectories, conditioned on a given policy, using independence assumptions and approximate propagation of distributions. The symbolic graph provides a differentiable representation of the policy's value, enabling efficient gradient-based optimization for long-horizon search. The propagation of approximate distributions can be seen as an aggregation of many trajectories, making it well-suited for dealing with sparse rewards and stochastic environments. An extensive experimental evaluation compares DiSProD to state-of-the-art planners in discrete-time planning and real-time control of robotic systems. The proposed method improves over existing planners in handling stochastic environments, sensitivity to search depth, sparsity of rewards, and large action spaces. Additional real-world experiments demonstrate that DiSProD can control ground vehicles and surface vessels to successfully navigate around obstacles.

NeurIPS Conference 2019 Conference Paper

Sampling Networks and Aggregate Simulation for Online POMDP Planning

• Hao(Jackson) Cui
• Roni Khardon

The paper introduces a new algorithm for planning in partially observable Markov decision processes (POMDP) based on the idea of aggregate simulation. The algorithm uses product distributions to approximate the belief state and shows how to build a representation graph of an approximate action-value function over belief space. The graph captures the result of simulating the model in aggregate under independence assumptions, giving a symbolic representation of the value function. The algorithm supports large observation spaces using sampling networks, a representation of the process of sampling values of observations, which is integrated into the graph representation. Following previous work in MDPs this approach enables action selection in POMDPs through gradient optimization over the graph representation. This approach complements recent algorithms for POMDPs which are based on particle representations of belief states and an explicit search for action selection. Our approach enables scaling to large factored action spaces in addition to large state spaces and observation spaces. An experimental evaluation demonstrates that the algorithm provides excellent performance relative to state of the art in large POMDP problems.

ICAPS Conference 2019 Conference Paper

Stochastic Planning with Lifted Symbolic Trajectory Optimization

• Hao Cui 0003
• Thomas Keller 0001
• Roni Khardon

This paper investigates online stochastic planning for problems with large factored state and action spaces. One promising approach in recent work estimates the quality of applicable actions in the current state through aggregate simulation from the states they reach. This leads to significant speedup, compared to search over concrete states and actions, and suffices to guide decision making in cases where the performance of a random policy is informative of the quality of a state. The paper makes two significant improvements to this approach. The first, taking inspiration from lifted belief propagation, exploits the structure of the problem to derive a more compact computation graph for aggregate simulation. The second improvement replaces the random policy embedded in the computation graph with symbolic variables that are optimized simultaneously with the search for high quality actions. This expands the scope of the approach to problems that require deep search and where information is lost quickly with random steps. An empirical evaluation shows that these ideas significantly improve performance, leading to state of the art performance on hard planning problems.

NeurIPS Conference 2018 Conference Paper

From Stochastic Planning to Marginal MAP

• Hao(Jackson) Cui
• Radu Marinescu
• Roni Khardon

It is well known that the problems of stochastic planning and probabilistic inference are closely related. This paper makes two contributions in this context. The first is to provide an analysis of the recently developed SOGBOFA heuristic planning algorithm that was shown to be effective for problems with large factored state and action spaces. It is shown that SOGBOFA can be seen as a specialized inference algorithm that computes its solutions through a combination of a symbolic variant of belief propagation and gradient ascent. The second contribution is a new solver for Marginal MAP (MMAP) inference. We introduce a new reduction from MMAP to maximum expected utility problems which are suitable for the symbolic computation in SOGBOFA. This yields a novel algebraic gradient-based solver (AGS) for MMAP. An experimental evaluation illustrates the potential of AGS in solving difficult MMAP problems.

NeurIPS Conference 2017 Conference Paper

Excess Risk Bounds for the Bayes Risk using Variational Inference in Latent Gaussian Models

• Rishit Sheth
• Roni Khardon

Bayesian models are established as one of the main successful paradigms for complex problems in machine learning. To handle intractable inference, research in this area has developed new approximation methods that are fast and effective. However, theoretical analysis of the performance of such approximations is not well developed. The paper furthers such analysis by providing bounds on the excess risk of variational inference algorithms and related regularized loss minimization algorithms for a large class of latent variable models with Gaussian latent variables. We strengthen previous results for variational algorithms by showing they are competitive with any point-estimate predictor. Unlike previous work, we also provide bounds on the risk of the \emph{Bayesian} predictor and not just the risk of the Gibbs predictor for the same approximate posterior. The bounds are applied in complex models including sparse Gaussian processes and correlated topic models. Theoretical results are complemented by identifying novel approximations to the Bayesian objective that attempt to minimize the risk directly. An empirical evaluation compares the variational and new algorithms shedding further light on their performance.

AAAI Conference 2017 Conference Paper

Hindsight Optimization for Hybrid State and Action MDPs

• Aswin Raghavan
• Scott Sanner
• Roni Khardon
• Prasad Tadepalli
• Alan Fern

Hybrid (mixed discrete and continuous) state and action Markov Decision Processes (HSA-MDPs) provide an expressive formalism for modeling stochastic and concurrent sequential decision-making problems. Existing solvers for HSA-MDPs are either limited to very restricted transition distributions, require knowledge of domain-specific basis functions to achieve good approximations, or do not scale. We explore a domain-independent approach based on the framework of hindsight optimization (HOP) for HSA-MDPs, which uses an upper bound on the finite-horizon action values for action selection. Our main contribution is a linear time reduction to a Mixed Integer Linear Program (MILP) that encodes the HOP objective, when the dynamics are specified as location-scale probability distributions parametrized by Piecewise Linear (PWL) functions of states and actions. In addition, we show how to use the same machinery to select actions based on a lower-bound generated by straight line plans. Our empirical results show that the HSA-HOP approach effectively scales to high-dimensional problems and outperforms baselines that are capable of scaling to such large hybrid MDPs.

IJCAI Conference 2016 Conference Paper

Online Symbolic Gradient-Based Optimization for Factored Action MDPs

• Hao Cui
• Roni Khardon

This paper investigates online stochastic planning for problems with large factored state and action spaces. We introduce a novel algorithm that builds a symbolic representation capturing an approximation of the action-value Q-function in terms of action variables, and then performs gradient based search to select an action for the current state. The algorithm can be seen as a symbolic extension of Monte-Carlo search, induced by independence assumptions on state and action variables, and augmented with gradients to speed up the search. This avoids the space explosion typically faced by symbolic methods, and the dearth of samples faced by Monte-Carlo methods when the action space is large. An experimental evaluation on benchmark problems shows that the algorithm is competitive with state of the art across problem sizes and that it provides significant improvements for large factored action spaces.

AAAI Conference 2015 Conference Paper

Factored MCTS for Large Scale Stochastic Planning

• Hao Cui
• Roni Khardon
• Alan Fern
• Prasad Tadepalli

This paper investigates stochastic planning problems with large factored state and action spaces. We show that even with moderate increase in the size of existing challenge problems, the performance of state of the art algorithms deteriorates rapidly, making them ineffective. To address this problem we propose a family of simple but scalable online planning algorithms that combine sampling, as in Monte Carlo tree search, with “aggregation”, where the aggregation approximates a distribution over random variables by the product of their marginals. The algorithms are correct under some rather strong technical conditions and can serve as an unsound but effective heuristic when the conditions do not hold. An extensive experimental evaluation demonstrates that the new algorithms provide significant improvement over the state of the art when solving large problems in a number of challenge benchmark domains.

ICAPS Conference 2015 Conference Paper

Hindsight Optimization for Probabilistic Planning with Factored Actions

• Murugeswari Issakkimuthu
• Alan Fern
• Roni Khardon
• Prasad Tadepalli
• Shan Xue

Inspired by the success of the satisfiability approach for deterministic planning, we propose a novel framework for on-line stochastic planning, by embedding the idea of hindsight optimization into a reduction to integer linear programming. In contrast to the previous work using reductions or hindsight optimization, our formulation is general purpose by working with domain specifications over factored state and action spaces, and by doing so is also scalable in principle to exponentially large action spaces. Our approach is competitive with state-of-the-art stochastic planners on challenging benchmark problems, and sometimes exceeds their performance especially in large action spaces.

UAI Conference 2015 Conference Paper

Memory-Effcient Symbolic Online Planning for Factored MDPs

• Aswin Raghavan
• Roni Khardon
• Prasad Tadepalli
• Alan Fern

Factored Markov Decision Processes (MDP) are a de facto standard for compactly modeling sequential decision making problems with uncertainty. Offline planning based on symbolic operators exploits the factored structure of MDPs, but is memory intensive. We present new memoryefficient symbolic operators for online planning, prove the soundness of the operators, and show convergence of the corresponding planning algorithms. An experimental evaluation demonstrates superior scalability on benchmark problems.

ICML Conference 2015 Conference Paper

Sparse Variational Inference for Generalized GP Models

• Rishit Sheth
• Yuyang Wang
• Roni Khardon

Gaussian processes (GP) provide an attractive machine learning model due to their non-parametric form, their flexibility to capture many types of observation data, and their generic inference procedures. Sparse GP inference algorithms address the cubic complexity of GPs by focusing on a small set of pseudo-samples. To date, such approaches have focused on the simple case of Gaussian observation likelihoods. This paper develops a variational sparse solution for GPs under general likelihoods by providing a new characterization of the gradients required for inference in terms of individual observation likelihood terms. In addition, we propose a simple new approach for optimizing the sparse variational approximation using a fixed point computation. We demonstrate experimentally that the fixed point operator acts as a contraction in many cases and therefore leads to fast convergence. An experimental evaluation for count regression, classification, and ordinal regression illustrates the generality and advantages of the new approach.

AIJ Journal 2015 Journal Article

The complexity of reasoning with FODD and GFODD

• Benjamin J. Hescott
• Roni Khardon

Recent work introduced Generalized First Order Decision Diagrams (GFODD) as a knowledge representation language that is useful in mechanizing decision theoretic planning in relational domains. GFODDs generalize function-free first order logic and include numerical values and numerical generalizations of existential and universal quantification. Previous work presented heuristic inference algorithms for GFODDs and implemented these heuristics in systems for decision theoretic planning. In this paper, we study the complexity of the computational problems addressed by such implementations. In particular, we study the evaluation problem, the satisfiability problem, and the equivalence problem for GFODDs under the assumption that the size of the intended model is given with the problem, a restriction that guarantees decidability. Our results provide a complete characterization placing these problems within the polynomial hierarchy. The same characterization applies to the corresponding restriction of problems in first order logic, giving an interesting new avenue for efficient inference when the number of objects is bounded. Our results show that for Σ k formulas, and for corresponding GFODDs, evaluation and satisfiability are Σ k P complete, and equivalence is Π k + 1 P complete. For Π k formulas evaluation is Π k P complete, satisfiability is one level higher and is Σ k + 1 P complete, and equivalence is Π k + 1 P complete.

AAAI Conference 2014 Conference Paper

The Complexity of Reasoning with FODD and GFODD

• Benjamin Hescott
• Roni Khardon

Recent work introduced Generalized First Order Decision Diagrams (GFODD) as a knowledge representation that is useful in mechanizing decision theoretic planning in relational domains. GFODDs generalize function-free first order logic and include numerical values and numerical generalizations of existential and universal quantification. Previous work presented heuristic inference algorithms for GFODDs. In this paper, we study the complexity of the evaluation problem, the satisfiability problem, and the equivalence problem for GFODDs under the assumption that the size of the intended model is given with the problem, a restriction that guarantees decidability. Our results provide a complete characterization. The same characterization applies to the corresponding restriction of problems in first order logic, giving an interesting new avenue for efficient inference when the number of objects is bounded. Our results show that for Σk formulas, and for corresponding GFODDs, evaluation and satisfiability are Σp k complete, and equivalence is Πp k+1 complete. For Πk formulas evaluation is Πp k complete, satisfiability is one level higher and is Σp k+1 complete, and equivalence is Πp k+1 complete.

NeurIPS Conference 2013 Conference Paper

Symbolic Opportunistic Policy Iteration for Factored-Action MDPs

• Aswin Raghavan
• Roni Khardon
• Alan Fern
• Prasad Tadepalli

We address the scalability of symbolic planning under uncertainty with factored states and actions. Prior work has focused almost exclusively on factored states but not factored actions, and on value iteration (VI) compared to policy iteration (PI). Our first contribution is a novel method for symbolic policy backups via the application of constraints, which is used to yield a new efficient symbolic imple- mentation of modified PI (MPI) for factored action spaces. While this approach improves scalability in some cases, naive handling of policy constraints comes with its own scalability issues. This leads to our second and main contribution, symbolic Opportunistic Policy Iteration (OPI), which is a novel convergent al- gorithm lying between VI and MPI. The core idea is a symbolic procedure that applies policy constraints only when they reduce the space and time complexity of the update, and otherwise performs full Bellman backups, thus automatically adjusting the backup per state. We also give a memory bounded version of this algorithm allowing a space-time tradeoff. Empirical results show significantly improved scalability over the state-of-the-art.

ICRA Conference 2012 Conference Paper

Abstract planning for reactive robots

• Saket Joshi
• Paul W. Schermerhorn
• Roni Khardon
• Matthias Scheutz

Hybrid reactive-deliberative architectures in robotics combine reactive sub-policies for fast action execution with goal sequencing and deliberation. The need for replanning, however, presents a challenge for reactivity and hinders the potential for guarantees about the plan quality. In this paper, we argue that one can integrate abstract planning provided by symbolic dynamic programming in first order logic into a reactive robotic architecture, and that such an integration is in fact natural and has advantages over traditional approaches. In particular, it allows the integrated system to spend off-line time planning for a policy, and then use the policy reactively in open worlds, in situations with unexpected outcomes, and even in new environments, all by simply reacting to a state change executing a new action proposed by the policy. We demonstrate the viability of the approach by integrating the FODD-Planner with the robotic DIARC architecture showing how an appropriate interface can be defined and that this integration can yield robust goal-based action execution on robots in open worlds.

AAAI Conference 2012 Conference Paper

Planning in Factored Action Spaces with Symbolic Dynamic Programming

• Aswin Raghavan
• Saket Joshi
• Alan Fern
• Prasad Tadepalli
• Roni Khardon

We consider symbolic dynamic programming (SDP) for solving Markov Decision Processes (MDP) with factored state and action spaces, where both states and actions are described by sets of discrete variables. Prior work on SDP has considered only the case of factored states and ignored structure in the action space, causing them to scale poorly in terms of the number of action variables. Our main contribution is to present the first SDP-based planning algorithm for leveraging both state and action space structure in order to compute compactly represented value functions and policies. Since our new algorithm can potentially require more space than when action structure is ignored, our second contribution is to describe an approach for smoothly trading-off space versus time via recursive conditioning. Finally, our third contribution is to introduce a novel SDP approximation that often significantly reduces planning time with little loss in quality by exploiting action structure in weakly coupled MDPs. We present empirical results in three domains with factored action spaces that show that our algorithms scale much better with the number of action variables as compared to state-of-the-art SDP algorithms.

AIJ Journal 2011 Journal Article

Decision-theoretic planning with generalized first-order decision diagrams

• Saket Joshi
• Kristian Kersting
• Roni Khardon

Many tasks in AI require representation and manipulation of complex functions. First-Order Decision Diagrams (FODD) are a compact knowledge representation expressing functions over relational structures. They represent numerical functions that, when constrained to the Boolean range, use only existential quantification. Previous work has developed a set of operations for composition and for removing redundancies in FODDs, thus keeping them compact, and showed how to successfully employ FODDs for solving large-scale stochastic planning problems through the formalism of relational Markov decision processes (RMDP). In this paper, we introduce several new ideas enhancing the applicability of FODDs. More specifically, we first introduce Generalized FODDs (GFODD) and composition operations for them, generalizing FODDs to arbitrary quantification. Second, we develop a novel approach for reducing (G)FODDs using model checking. This yields – for the first time – a reduction that maximally reduces the diagram for the FODD case and provides a sound reduction procedure for GFODDs. Finally we show how GFODDs can be used in principle to solve RMDPs with arbitrary quantification, and develop a complete solution for the case where the reward function is specified using an arbitrary number of existential quantifiers followed by an arbitrary number of universal quantifiers.

AAAI Conference 2010 Conference Paper

Relational Partially Observable MDPs

• Chenggang Wang
• Roni Khardon

Relational Markov Decision Processes (MDP) are a useful abstraction for stochastic planning problems since one can develop abstract solutions for them that are independent of domain size or instantiation. While there has been an increased interest in developing relational fully observable MDPs, there has been very little work on relational partially observable MDPs (POMDP), which deal with uncertainty in problem states in addition to stochastic action effects. This paper provides a concrete formalization of relational POMDPs making several technical contributions toward their solution. First, we show that to maintain correctness one must distinguish between quantification over states and quantification over belief states; this implies that solutions based on value iteration are inherently limited to the finite horizon case. Second, we provide a symbolic dynamic programing algorithm for finite horizon relational POMDPs, solving them at an abstract level, by lifting the propositional incremental pruning algorithm. Third, we show that this algorithm can be implemented using first order decision diagrams, a compact representation for functions over relational structures, that has been recently used to solve relational MDPs.

ICAPS Conference 2010 Conference Paper

Self-Taught Decision Theoretic Planning with First Order Decision Diagrams

• Saket Joshi
• Kristian Kersting
• Roni Khardon

We present a new paradigm for planning by learning, where the planner is given a model of the world and a small set of states of interest, but no indication of optimal actions in these states. The additional information can help focus the planner on regions of the state space that are of interest and lead to improved performance. We demonstrate this idea by introducing novel model-checking reduction operations for First Order Decision Diagrams (FODD), a representation that has been used to implement decision-theoretic planning with Relational Markov Decision Processes (RMDP). Intuitively, these reductions modify the construction of the value function by removing any complex specifications that are irrelevant to the set of training examples, thereby focusing on the region of interest. We show that such training examples can be constructed on the fly from a description of the planning problem thus we can bootstrap to get a self-taught planning system. Additionally, we provide a new heuristic to embed universal and conjunctive goals within the framework of RMDP planners, expanding the scope and applicability of such systems. We show that these ideas lead to significant improvements in performance in terms of both speed and coverage of the planner, yielding state of the art planning performance on problems from the International Planning Competition.

IJCAI Conference 2009 Conference Paper

• Saket Joshi
• Kristian Kersting
• Roni Khardon

First order decision diagrams (FODD) were recently introduced as a compact knowledge representation expressing functions over relational structures. FODDs represent numerical functions that, when constrained to the Boolean range, use only existential quantification. Previous work developed a set of operations over FODDs, showed how they can be used to solve relational Markov decision processes (RMDP) using dynamic programming algorithms, and demonstrated their success in solving stochastic planning problems from the International Planning Competition in the system FODD-Planner. A crucial ingredient of this scheme is a set of operations to remove redundancy in decision diagrams, thus keeping them compact. This paper makes three contributions. First, we introduce Generalized FODDs (GFODD) and combination algorithms for them, generalizing FODDs to arbitrary quantification. Second, we show how GFODDs can be used in principle to solve RMDPs with arbitrary quantification, and develop a particularly promising case where an arbitrary number of existential quantifiers is followed by an arbitrary number of universal quantifiers. Third, we develop a new approach to reduce FODDs and GFODDs using model checking. This yields a reduction that is complete for FODDs and provides a sound reduction procedure for GFODDs.

ICAPS Conference 2008 Conference Paper

Stochastic Planning with First Order Decision Diagrams

• Saket Joshi
• Roni Khardon

Dynamic programming algorithms have been successfully applied to propositional stochastic planning problems by using compact representations, in particular algebraic decision diagrams, to capture domain dynamics and value functions. Work on symbolic dynamic programming lifted these ideas to first order logic using several representation schemes. Recent work introduced a first order variant of decision diagrams (FODD) and developed a value iteration algorithm for this representation. This paper develops several improvements to the FODD algorithm that make the approach practical. These include, new reduction operators that decrease the size of the representation, several speedup techniques, and techniques for value approximation. Incorporating these, the paper presents a planning system, FODD-Planner, for solving relational stochastic planning problems. The system is evaluated on several domains, including problems from the recent international planning competition, and shows competitive performance with top ranking systems. This is the first demonstration of feasibility of this approach and it shows that abstraction through compact representation is a promising approach to stochastic planning.

IJCAI Conference 2007 Conference Paper

• Gemma C. Garriga
• Roni Khardon
• Luc De Raedt

We investigate the problem of mining closed sets in multi-relational databases. Previous work introduced different semantics and associated algorithms for mining closed sets in multi-relational databases. However, insight into the implications of semantic choices and the relationships among them was still lacking. Our investigation shows that the semantic choices are important because they imply different properties, which in turn affect the range of algorithms that can mine for such sets. Of particular interest is the question whether the seminal LCM algorithm by Uno et al. can be upgraded towards multi-relational problems. LCM is attractive since its run time is linear in the number of closed sets and it does not need to store outputs in order to avoid duplicates. We provide a positive answer to this question for some of the semantic choices, and report on experiments that evaluate the scalability and applicability of the upgraded algorithm on benchmark problems.

IJCAI Conference 2007 Conference Paper

• Chenggang Wang
• Saket Joshi
• Roni Khardon

Dynamic programming algorithms provide a basic tool identifying optimal solutions in Markov Decision Processes (MDP). The paper develops a representation for decision diagrams suitable for describing value functions, transition probabilities, and domain dynamics of First Order or Relational MDPs (FOMDP). By developing appropriate operations for such diagrams the paper shows how value iteration can be performed compactly for such problems. This improves on previous approaches since the representation combines compact form with efficient operations. The work also raises interesting issues on suitability of different representations to different FOMDPs tasks.

ICML Conference 2007 Conference Paper

Learning from interpretations: a rooted kernel for ordered hypergraphs

• Gabriel Wachman
• Roni Khardon

The paper presents a kernel for learning from ordered hypergraphs, a formalization that captures relational data as used in Inductive Logic Programming (ILP). The kernel generalizes previous approaches to graph kernels in calculating similarity based on walks in the hypergraph. Experiments on challenging chemical datasets demonstrate that the kernel outperforms existing ILP methods, and is competitive with state-of-the-art graph kernels. The experiments also demonstrate that the encoding of graph data can affect performance dramatically, a fact that can be useful beyond kernel methods.

JMLR Journal 2007 Journal Article

Learning Horn Expressions with LOGAN-H

• Marta Arias
• Roni Khardon
• Jérôme Maloberti

The paper introduces L OG A N -H — a system for learning first-order function-free Horn expressions from interpretations. The system is based on an algorithm that learns by asking questions and that was proved correct in previous work. The current paper shows how the algorithm can be implemented in a practical system, and introduces a new algorithm based on it that avoids interaction and learns from examples only. The L OG A N -H system implements these algorithms and adds several facilities and optimizations that allow efficient applications in a wide range of problems. As one of the important ingredients, the system includes several fast procedures for solving the subsumption problem, an NP-complete problem that needs to be solved many times during the learning process. We describe qualitative and quantitative experiments in several domains. The experiments demonstrate that the system can deal with varied problems, large amounts of data, and that it achieves good classification accuracy. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

JMLR Journal 2007 Journal Article

Noise Tolerant Variants of the Perceptron Algorithm

• Roni Khardon
• Gabriel Wachman

A large number of variants of the Perceptron algorithm have been proposed and partially evaluated in recent work. One type of algorithm aims for noise tolerance by replacing the last hypothesis of the perceptron with another hypothesis or a vote among hypotheses. Another type simply adds a margin term to the perceptron in order to increase robustness and accuracy, as done in support vector machines. A third type borrows further from support vector machines and constrains the update function of the perceptron in ways that mimic soft-margin techniques. The performance of these algorithms, and the potential for combining different techniques, has not been studied in depth. This paper provides such an experimental study and reveals some interesting facts about the algorithms. In particular the perceptron with margin is an effective method for tolerating noise and stabilizing the algorithm. This is surprising since the margin in itself is not designed or used for noise tolerance, and there are no known guarantees for such performance. In most cases, similar performance is obtained by the voted-perceptron which has the advantage that it does not require parameter selection. Techniques using soft margin ideas are run-time intensive and do not give additional performance benefits. The results also highlight the difficulty with automatic parameter selection which is required with some of these variants. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

UAI Conference 2007 Conference Paper

Policy Iteration for Relational MDPs

• Chenggang Wang
• Roni Khardon

I&C Journal 2006 Journal Article

Polynomial certificates for propositional classes

• Marta Arias
• Aaron Feigelson
• Roni Khardon
• Rocco A. Servedio

This paper studies the complexity of learning classes of expressions in propositional logic from equivalence queries and membership queries. In particular, we focus on bounding the number of queries that are required to learn the class ignoring computational complexity. This quantity is known to be captured by a combinatorial measure of concept classes known as the certificate complexity. The paper gives new constructions of polynomial size certificates for monotone expressions in conjunctive normal form (CNF), for unate CNF functions where each variable affects the function either positively or negatively but not both ways, and for Horn CNF functions. Lower bounds on certificate size for these classes are derived showing that for some parameter settings the new certificate constructions are optimal. Finally, the paper gives an exponential lower bound on the certificate size for a natural generalization of these classes known as renamable Horn CNF functions, thus implying that the class is not learnable from a polynomial number of queries.

JMLR Journal 2005 Journal Article

Maximum Margin Algorithms with Boolean Kernels

• Roni Khardon
• Rocco A. Servedio

Recent work has introduced Boolean kernels with which one can learn linear threshold functions over a feature space containing all conjunctions of length up to k (for any 1 ≤ k ≤ n ) over the original n Boolean features in the input space. This motivates the question of whether maximum margin algorithms such as Support Vector Machines can learn Disjunctive Normal Form expressions in the Probably Approximately Correct (PAC) learning model by using this kernel. We study this question, as well as a variant in which structural risk minimization (SRM) is performed where the class hierarchy is taken over the length of conjunctions. We show that maximum margin algorithms using the Boolean kernels do not PAC learn t ( n )-term DNF for any t ( n ) = ω(1), even when used with such a SRM scheme. We also consider PAC learning under the uniform distribution and show that if the kernel uses conjunctions of length ˜ω(√ n ) then the maximum margin hypothesis will fail on the uniform distribution as well. Our results concretely illustrate that margin based algorithms may overfit when learning simple target functions with natural kernels. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

I&C Journal 2002 Journal Article

Learning Closed Horn Expressions

• Marta Arias
• Roni Khardon

The paper studies the learnability of Horn expressions within the framework of learning from entailment, where the goal is to exactly identify some pre-fixed and unknown expression by making queries to membership and equivalence oracles. It is shown that a class that includes both range restricted Horn expressions (where terms in the conclusion also appear in the condition of a Horn clause) and constrained Horn expressions (where terms in the condition also appear in the conclusion of a Horn clause) is learnable. This extends previous results by showing that a larger class is learnable with better complexity bounds. A further improvement in the number of queries is obtained when considering the class of Horn expressions with inequalities on all syntactically distinct terms.

NeurIPS Conference 2001 Conference Paper

Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms

• Roni Khardon
• Dan Roth
• Rocco Servedio

We study online learning in Boolean domains using kernels which cap- ture feature expansions equivalent to using conjunctions over basic fea- tures. We demonstrate a tradeoff between the computational efficiency with which these kernels can be computed and the generalization abil- ity of the resulting classifier. We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Percep- tron algorithm over an exponential number of conjunctions; however we also prove that using such kernels the Perceptron algorithm can make an exponential number of mistakes even when learning simple func- tions. We also consider an analogous use of kernel functions to run the multiplicative-update Winnow algorithm over an expanded feature space of exponentially many conjunctions. While known upper bounds imply that Winnow can learn DNF formulae with a polynomial mistake bound in this setting, we prove that it is computationally hard to simulate Win- now’s behavior for learning DNF over such a feature set, and thus that such kernel functions for Winnow are not efficiently computable.

ICML Conference 2000 Conference Paper

Learning Horn Expressions with LogAn-H

• Roni Khardon

AIJ Journal 1999 Journal Article

Learning action strategies for planning domains

• Roni Khardon

This paper reports on experiments where techniques of supervised machine learning are applied to the problem of planning. The input to the learning algorithm is composed of a description of a planning domain, planning problems in this domain, and solutions for them. The output is an efficient algorithm—a strategy—for solving problems in that domain. We test the strategy on an independent set of planning problems from the same domain, so that success is measured by its ability to solve complete problems. A system, L2Act, has been developed in order to perform these experiments. We have experimented with the blocks world domain and the logistics transportation domain, using strategies in the form of a generalisation of decision lists. The condition of a rule in the decision list is an existentially quantified first order expression, and each such rule indicates which action to take when the condition is satisfied. The learning algorithm is a variant of Rivest's (1987) algorithm, improved with several techniques that reduce its time complexity. The experiments demonstrate that the approach is feasible, and generalisation is achieved so that unseen problems can be solved by the learned strategies. Moreover, the learned strategies are efficient, the solutions found by them are competitive with those of known heuristics for the domains, and transfer from small planning problems in the examples to larger ones in the test set is exhibited.

IJCAI Conference 1999 Conference Paper

Relational Learning for NLP using Linear Threshold Elements

• Roni Khardon
• Dan Roth
• Leslie G. Valiant___911

We describe a coherent view of learning and reasoning with relational representations in the context of natural language processing. In particular, we discuss the Neuroidal Architecture, Inductive Logic Programming and the SNoW system explaining the relationships among these, and thereby offer an explanation of the theoretical basis for the SNoW system. We suggest that extensions of this system along the lines suggested by the theory may provide new levels of scalability and functionality.

AIJ Journal 1997 Journal Article

Defaults and relevance in model-based reasoning

• Roni Khardon
• Dan Roth

Reasoning with model-based representations is an intuitive paradigm, which has been shown to be theoretically sound and to possess some computational advantages over reasoning with formula-based representations of knowledge. This paper studies these representations and further substantiates the claim regarding their advantages. In particular, model-based representations are shown to efficiently support reasoning in the presence of varying context information, handle efficiently fragments of Reiter's default logic and provide a useful way to integrate learning with reasoning. Furthermore, these results are closely related to the notion of relevance. The use of relevance information is best exemplified by the filtering process involved in the algorithm developed for reasoning within context. The relation of defaults to relevance is viewed through the notion of context, where the agent has to find plausible context information by using default rules. This view yields efficient algorithms for default reasoning. Finally, it is argued that these results support an incremental view of reasoning in a natural way, and the notion of relevance to the environment, captured by the Learning to Reason framework, is discussed.

AAAI Conference 1996 Conference Paper

Learning to Take Actions

• Roni Khardon

We formalize a model for supervised learning of action strategies in dynamic stochastic domains, and show that pat-learning results on Occam algorithms hold in this model as well. We then identify a particularly useful bias for action strategies based on production rule systems. We show that a subset of production rule systems, including rules in predicate calculus style, small hidden state, and unobserved support predicates, is properly learnable. The bias we introduce enables the learning algorithm to invent the recursive support predicates which are used in the action strategy, and to reconstruct the internal state of the strategy. It is also shown that hierarchical strategies are learnable if a helpful teacher is available, but that otherwise the problem is computationally hard.

AIJ Journal 1996 Journal Article

Reasoning with models

• Roni Khardon
• Dan Roth

We develop a model-based approach to reasoning, in which the knowledge base is represented as a set of models (satisfying assignments) rather than a logical formula, and the set of queries is restricted. We show that for every propositional knowledge base (KB) there exists a set of characteristic models with the property that a query is true in KB if and only if it is satisfied by the models in this set. We characterize a set of functions for which the model-based representation is compact and provides efficient reasoning. These include cases where the formula-based representation does not support efficient reasoning. In addition, we consider the model-based approach to abductive reasoning and show that for any propositional KB, reasoning with its model-based representation yields an abductive explanation in time that is polynomial in its size. Some of our technical results make use of the monotone theory, a new characterization of Boolean functions recently introduced. The notion of restricted queries is inherent in our approach. This is a wide class of queries for which reasoning is efficient and exact, even when the model-based representation KB provides only an approximate representation of the domain in question. Moreover, we show that the theory developed here generalizes the model-based approach to reasoning with Horn expressions and captures even the notion of reasoning with Horn approximations.

IJCAI Conference 1995 Conference Paper

Default-Reasoning with Models

• Roni Khardon
• Dan Roth

Reasoning with model-based representations is an intuitive paradigm, which has been shown to be theoretically sound and to possess some computational advantages over reasoning with formula-based representations of knowledge. In this paper we present more evidence to the util­ ity of such representations. In real life situations, one normally completes a lot of missing "context" information when answering queries. We model this situation by augmenting the available knowledge about the world with context-specific information; we show that reasoning with model-based repre­ sentations can be done efficiently in the pres­ ence of varying context information. We then consider the task of default reasoning. We show that default reasoning is a generalization of reasoning within context, in which the reasoner has many "context" rules, which may be conflicting. We characterize the cases in which model-based reasoning supports efficient default reasoning and develop algorithms that handle efficiently fragments of Reiter's default logic. In particular, this includes cases in which performing the default reasoning task with the traditional, formula-based, representation is in­ tractable. Further, we argue that these results support an incremental view of reasoning in a natural way.

AAAI Conference 1994 Conference Paper

Learning to Reason

• Roni Khardon

We introduce a new framework for the study of reasoning. The Learning (in order) to Reason approach developed here combines the interfaces to the world used by known learning models with the reasoning task and a performance criterion suitable for it. We show how previous results from learning theory and reasoning fit into this framework and illustrate the usefulness of the Learning to Reason approach by exhibiting new results that are not possible in the traditional setting. First, we give a Learning to Reason algorithm for a class of propositional languages for which there are no efficient reasoning algorithms, when represented as a traditional (formulabased) knowledge base. Second, we exhibit a Learning to Reason algorithm for a class of propositional languages that is not known to be learnable in the traditional sense.

AAAI Conference 1994 Conference Paper

Reasoning with Models

• Roni Khardon

We develop a model-based approach to reasoning, in which the knowledge base is represented as a set of models (satisfying assignments) rather then a logical formula, and the set of queries is restricted. We show that for every propositional knowledge base (KB) there exists a set of characteristic models with the property that a query is true in KB if and only if it is satisfied by the models in this set. We fully characterize a set of theories for which the model-based representation is compact and provides efficient reasoning. These include some cases where the formulabased representation does not support efficient reasoning. In addition, we consider the model-based approach to abductive reasoning and show that for any propositional KB, reasoning with its model-based representation yields an abductive explanation in time that is polynomial in its size.