Author name cluster

Junkyu Lee

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

1 author row

ISIPTA Conference 2025 Conference Paper

Dealing with cycles in graph-based probabilistic models: the case of Logical Credal Networks

Fabio G. Cozman
Radu Marinescu
Junkyu Lee
Alexander Gray
Denis D. Mau\'a

We examine the consequences of directed cycles in graph-based representations of joint distributions, investigating the effect of cycles on Markov conditions and on Gibbs factorizations. We focus on Logical Credal Networks, a flexible and general formalism, showing that Koster’s theory of Directed-Undirected Mixed Graphs (DUMGs) leads to an interesting Gibbs factorization. We show that inferences with DUMGs lead to multilinear programs. We also study the failure of global Markov conditions in cyclic structural equation models, connecting that failure to probabilistic imprecision under interventions.

PDF Details

NeurIPS Conference 2025 Conference Paper

Meta-D2AG: Causal Graph Learning with Interventional Dynamic Data

Tian Gao
Songtao Lu
Junkyu Lee
Elliot Nelson
Debarun Bhattacharjya
Yue Yu
Miao Liu

Causal discovery in the form of a directed acyclic graph (DAG) for dynamic time series data has been widely studied in various applications. Much of the existing work has focused on observational, offline, and/or stationary settings. In this work, we propose a dynamic DAG discovery algorithm, Meta-D$^2$AG, based on online meta-learning. Meta-D$^2$AG is designed to learn dynamic DAG structures from potentially nonlinear and non-stationary times series datasets, accounting for changes in both parameters and graph structures. Notably, Meta-D$^2$AG explicitly treats data collected at different time points with distribution shifts as distinct domains, which is assumed to occur as a result of external interventions. Moreover, Meta-D$^2$AG contains a new online meta-learning framework to take advantage of the temporal transition among existing domains such that it can quickly adapt to new domains with few measurements. A first-order optimization approach is utilized to efficiently solve the meta-learning framework, and theoretical analysis establishes the identifiability conditions and the convergence of the learning process. We demonstrate the promising performance of our method through better accuracy and sample efficiency on benchmark datasets against state-of-the-art baselines.

PDF Details

NeurIPS Conference 2024 Conference Paper

Abductive Reasoning in Logical Credal Networks

Radu Marinescu
Junkyu Lee
Debarun Bhattacharjya
Fabio Cozman
Alexander Gray

Logical Credal Networks or LCNs were recently introduced as a powerful probabilistic logic framework for representing and reasoning with imprecise knowledge. Unlike many existing formalisms, LCNs have the ability to represent cycles and allow specifying marginal and conditional probability bounds on logic formulae which may be important in many realistic scenarios. Previous work on LCNs has focused exclusively on marginal inference, namely computing posterior lower and upper probability bounds on a query formula. In this paper, we explore abductive reasoning tasks such as solving MAP and Marginal MAP queries in LCNs given some evidence. We first formally define the MAP and Marginal MAP tasks for LCNs and subsequently show how to solve these tasks exactly using search-based approaches. We then propose several approximate schemes that allow us to scale MAP and Marginal MAP inference to larger problem instances. An extensive empirical evaluation demonstrates the effectiveness of our algorithms on both random LCN instances as well as LCNs derived from more realistic use-cases.

PDF Details DOI

PRL Workshop 2024 Workshop Paper

Guiding Hiearchical Reinforcement Learning in Partially Observable Environments with AI Planning

Brandon Rozek
Junkyu Lee
Harsha Kokel
Michael Katz
Shirin Sohrabi

Partially observable Markov decision processes challenge reinforcement learning agents since observations provide an limited view of the environment. This often requires an agent to explore collecting observations to form the necessary state information to complete the task. Even assuming knowledge is monotonic, it is difficult to know when to stop exploration. We integrate AI planning within hierarchical reinforcement learning to aide in the exploration of partially observable environments. Given a set of unknown state variables, their potential valuations, along with which abstract operators may discover them, we create an abstract fully-observable nondeterministic planning problem which captures the agent’s abstract belief state. This decomposes the POMDP into a tree of semi-POMDPs based on sensing outcomes. We evaluate our agent’s performance on a MiniGrid domain and show how guided exploration may improve agent performance.

PDF Details

AAAI Conference 2024 Short Paper

Large Language Models as Planning Domain Generators (Student Abstract)

James Oswald
Kavitha Srinivas
Harsha Kokel
Junkyu Lee
Michael Katz
Shirin Sohrabi

The creation of planning models, and in particular domain models, is among the last bastions of tasks that require exten- sive manual labor in AI planning; it is desirable to simplify this process for the sake of making planning more accessi- ble. To this end, we investigate whether large language mod- els (LLMs) can be used to generate planning domain models from textual descriptions. We propose a novel task for this as well as a means of automated evaluation for generated do- mains by comparing the sets of plans for domain instances. Finally, we perform an empirical analysis of 7 large language models, including coding and chat models across 9 different planning domains. Our results show that LLMs, particularly larger ones, exhibit some level of proficiency in generating correct planning domains from natural language descriptions

PDF Details DOI

AAAI Conference 2024 Short Paper

Partially Observable Hierarchical Reinforcement Learning with AI Planning (Student Abstract)

Brandon Rozek
Junkyu Lee
Harsha Kokel
Michael Katz
Shirin Sohrabi

Partially observable Markov decision processes (POMDPs) challenge reinforcement learning agents due to incomplete knowledge of the environment. Even assuming monotonicity in uncertainty, it is difficult for an agent to know how and when to stop exploring for a given task. In this abstract, we discuss how to use hierarchical reinforcement learning (HRL) and AI Planning (AIP) to improve exploration when the agent knows possible valuations of unknown predicates and how to discover them. By encoding the uncertainty in an abstract planning model, the agent can derive a high-level plan which is then used to decompose the overall POMDP into a tree of semi-POMDPs for training. We evaluate our agent's performance on the MiniGrid domain and show how guided exploration may improve agent performance.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Action Space Reduction for Planning Domains

Harsha Kokel
Junkyu Lee
Michael Katz
Kavitha Srinivas
Shirin Sohrabi

Planning tasks succinctly represent labeled transition systems, with each ground action corresponding to a label. This granularity, however, is not necessary for solving planning tasks and can be harmful, especially for model-free methods. In order to apply such methods, the label sets are often manually reduced. In this work, we propose automating this manual process. We characterize a valid label reduction for classical planning tasks and propose an automated way of obtaining such valid reductions by leveraging lifted mutex groups. Our experiments show a significant reduction in the action label space size across a wide collection of planning domains. We demonstrate the benefit of our automated label reduction in two separate use cases: improved sample complexity of model-free reinforcement learning algorithms and speeding up successor generation in lifted planning. The code and supplementary material are available at https: //github. com/IBM/Parameter-Seed-Set.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

Credal Marginal MAP

Radu Marinescu
Debarun Bhattacharjya
Junkyu Lee
Fabio Cozman
Alexander Gray

Credal networks extend Bayesian networks to allow for imprecision in probability values. Marginal MAP is a widely applicable mixed inference task that identifies the most likely assignment for a subset of variables (called MAP variables). However, the task is extremely difficult to solve in credal networks particularly because the evaluation of each complete MAP assignment involves exact likelihood computations (combinatorial sums) over the vertices of a complex joint credal set representing the space of all possible marginal distributions of the MAP variables. In this paper, we explore Credal Marginal MAP inference and develop new exact methods based on variable elimination and depth-first search as well as several approximation schemes based on the mini-bucket partitioning and stochastic local search. An extensive empirical evaluation demonstrates the effectiveness of our new methods on random as well as real-world benchmark problems.

PDF Details

IJCAI Conference 2023 Conference Paper

K∗ Search over Orbit Space for Top-k Planning

Michael Katz
Junkyu Lee

Top-k planning, the task of finding k top-cost plans, is a key formalism for many planning applications and K* search is a well-established approach to top-k planning. The algorithm iteratively runs A* search and Eppstein’s algorithm until a sufficient number of plans is found. The performance of K* algorithm is therefore inherently limited by the performance of A*, and in order to improve K* performance, that of A* must be improved. In cost-optimal planning, orbit space search improves A* performance by exploiting symmetry pruning, essentially performing A* in the orbit space instead of state space. In this work, we take a similar approach to top-k planning. We show theoretical equivalence between the goal paths in the state space and in the orbit space, allowing to perform K* search in the orbit space instead, reconstructing plans from the found paths in the orbit space. We prove that our algorithm is sound and complete for top-k planning and empirically show it to achieve state-of-the-art performance, overtaking all existing to date top-k planners. The code is available at https: //github. com/IBM/kstar.

PDF Details DOI

PRL Workshop 2023 Workshop Paper

Learning Parameterized Policies for Planning Annotated RL

Harsha Kokel
Junkyu Lee
Michael Katz
Shirin Sohrabi

Recently, several approaches have utilized AI planning in the context of hierarchical reinforcement learning. These methods employ planning operator descriptions to establish options for acquiring primitive or low-level skills. By employing hierarchical decomposition through operators, these approaches offer notable benefits during training, such as enhanced sample efficiency, as well as during evaluation, with improved generalization across different yet related tasks. In this study, we introduce a novel approach for defining parameterized options using operator descriptions. Our empirical evaluations conducted on the mini-grid domain demonstrate that the proposed approach not only enhances sample efficiency but also overcomes certain limitations associated with generalization capabilities.

PDF Details

AAAI Conference 2022 Short Paper

How to Reduce Action Space for Planning Domains? (Student Abstract)

Harsha Kokel
Junkyu Lee
Michael Katz
Shirin Sohrabi
Kavitha Srinivas

While AI planning and Reinforcement Learning (RL) solve sequential decision-making problems, they are based on different formalisms, which leads to a significant difference in their action spaces. When solving planning problems using RL algorithms, we have observed that a naive translation of the planning action space incurs severe degradation in sample complexity. In practice, those action spaces are often engineered manually in a domain-specific manner. In this abstract, we present a method that reduces the parameters of operators in AI planning domains by introducing a parameter seed set problem and casting it as a classical planning task. Our experiment shows that our proposed method significantly reduces the number of actions in the RL environments originating from AI planning domains.

PDF Details

AAAI Conference 2021 Conference Paper

A New Bounding Scheme for Influence Diagrams

Radu Marinescu
Junkyu Lee
Rina Dechter

Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. Computing the maximum expected utility (MEU) and the optimizing policy is exponential in the constrained induced width and therefore is notoriously difficult for larger models. In this paper, we develop a new bounding scheme for MEU that applies partitioning based approximations on top of the decomposition scheme called a multi-operator cluster DAG for influence diagrams that is more sensitive to the underlying structure of the model than the classical join-tree decomposition of influence diagrams. Our bounding scheme utilizes a cost-shifting mechanism to tighten the bound further. We demonstrate the effectiveness of the proposed scheme on various hard benchmarks.

PDF Details

PRL Workshop 2021 Workshop Paper

AI Planning Annotation in Reinforcement Learning: Options and Beyond

Junkyu Lee
Michael Katz
Don Joven Agravante
Miao Liu
Tim Klinger
Murray Campbell
Shirin Sohrabi
Gerald Tesauro

AI planning and reinforcement learning (RL) both solve sequential decision-making problems, taking fundamentally different approaches. In this work, we aim to bring AI planning and RL closer by investigating the relationship between abstractions in AI planning and the options framework in RL. To this end, we propose annotating RL tasks with AI planning models, allowing us to define options based purely on the planning model. Our experimental investigation shows that these options can be quickly trained offline and can improve the sample efficiency of a reinforcement learning algorithm.

PDF Details

AAAI Conference 2021 Conference Paper

Submodel Decomposition Bounds for Influence Diagrams

Junkyu Lee
Radu Marinescu
Rina Dechter

Influence diagrams (IDs) are graphical models for representing and reasoning with sequential decision-making problems under uncertainty. Limited memory influence diagrams (LIMIDs) model a decision-maker (DM) who forgets the history in the course of making a sequence of decisions. The standard inference task in IDs and LIMIDs is to compute the maximum expected utility (MEU), which is one of the most challenging tasks in graphical models. We present a model decomposition framework in both IDs and LIMIDs, which we call submodel decomposition that generates a tree of single-stage decision problems through a tree clustering scheme. We also develop a valuation algebra over the submodels that leads to a hierarchical message passing algorithm that propagates conditional expected utility functions over a submodel-tree as external messages. We show that the overall complexity is bounded by the maximum tree-width over the submodels, common in graphical model algorithms. Finally, we present a new method for computing upper bounds over a submodel-tree by first exponentiating the utility functions yielding a standard probabilistic graphical model as an upper bound and then applying standard variational upper bounds for the marginal MAP inference, yielding tighter upper bounds compared with state-of-the-art bounding schemes for the MEU task.

PDF Details

AAAI Conference 2020 Short Paper

Submodel Decomposition for Solving Limited Memory Influence Diagrams (Student Abstract)

Junkyu Lee

This paper presents a systematic way of decomposing a limited memory inﬂuence diagram (LIMID) to a tree of single-stage decision problems, or submodels and solving it by message passing. The relevance in LIMIDs is formalized by the notion of the partial evaluation of the maximum expected utility, and the graph separation criteria for identifying submodels follow. The submodel decomposition provides a graphical model approach for updating the beliefs and propagating the conditional expected utilities for solving LIMIDs with the worst-case complexity bounded by the maximum treewidth of the individual submodels.

PDF Details

JAIR Journal 2018 Journal Article

AND/OR Search for Marginal MAP

Radu Marinescu
Junkyu Lee
Rina Dechter
Alexander Ihler

Mixed inference such as the marginal MAP query (some variables marginalized by summation and others by maximization) is key to many prediction and decision models. It is known to be extremely hard; the problem is NP PP -complete while the decision problem for MAP is only NP-complete and the summation problem is #P-complete. Consequently, approximation anytime schemes are essential. In this paper, we show that the framework of heuristic AND/OR search, which exploits conditional independence in the graphical model, coupled with variational-based mini-bucket heuristics can be extended to this task and yield powerful state-of-the-art schemes. Specifically, we explore the complementary properties of best-first search for reducing the number of conditional sums and providing time-improving upper bounds, with depth-first search for rapidly generating and improving solutions and lower bounds. We show empirically that a class of solvers that interleaves depth-first with best-first schemes emerges as the most competitive anytime scheme.

PDF Details DOI

AAAI Conference 2018 Short Paper

Probabilistic Planning With Influence Diagrams

Junkyu Lee

Graphical models provide a powerful framework for reasoning under uncertainty, and an influence diagram (ID) is a graphical model of a sequential decision problem that maximizes the total expected utility of a non-forgetting agent. Relaxing the regular modeling assumptions, an ID can be flexibly extended to general decision scenarios involving a limited memory agent or multi-agents. The approach of probabilistic planning with IDs is expected to gain computational leverage by exploiting the local structure as well as representation flexibility of influence diagram frameworks. My research focuses on graphical model inference for IDs and its application to probabilistic planning, targeting online MDP/POMDP planning as testbeds in the evaluation.

PDF Details

AAAI Conference 2017 Conference Paper

Anytime Best+Depth-First Search for Bounding Marginal MAP

Radu Marinescu
Junkyu Lee
Alexander Ihler
Rina Dechter

We introduce new anytime search algorithms that combine best-ﬁrst with depth-ﬁrst search into hybrid schemes for Marginal MAP inference in graphical models. The main goal is to facilitate the generation of upper bounds (via the best- ﬁrst part) alongside the lower bounds of solutions (via the depth-ﬁrst part) in an anytime fashion. We compare against two of the best current state-of-the-art schemes and show that our best+depth search scheme produces higher quality solutions faster while also producing a bound on their accuracy, which can be used to measure solution quality during search. An extensive empirical evaluation demonstrates the effectiveness of our new methods which enjoy the strength of best-ﬁrst (optimality of search) and of depth-ﬁrst (memory robustness), leading to solutions for difﬁcult instances where previous solvers were unable to ﬁnd even a single solution.

PDF Details

AAAI Conference 2016 Conference Paper

From Exact to Anytime Solutions for Marginal MAP

Junkyu Lee
Radu Marinescu
Rina Dechter
Alexander Ihler

This paper explores the anytime performance of search-based algorithms for solving the Marginal MAP task over graphical models. The current state-of-the-art for solving this challenging task is based on best-ﬁrst search exploring the AND/OR graph with the guidance of heuristics based on mini-bucket and variational cost-shifting principles. Yet, those schemes are uncompromising in that they solve the problem exactly, or not at all, and often suffer from memory problems. In this work, we explore the well known principle of weighted search for converting best-ﬁrst search solvers into anytime schemes. The weighted best-ﬁrst search schemes report a solution early in the process by using inadmissible heuristics, and subsequently improve the solution. While it was demonstrated recently that weighted schemes can yield effective anytime behavior for pure MAP tasks, Marginal MAP is far more challenging (e. g. , a conditional sum must be evaluated for every solution). Yet, in an extensive empirical analysis we show that weighted schemes are indeed highly effective anytime solvers for Marginal MAP yielding the most competitive schemes to date for this task.

PDF Details