Luke Ong

AAAI Conference 2026 Conference Paper

Conformal Prediction Meets Long-tail Classification

• Shuqi LIU
• Jianguo Huang
• Luke Ong

Conformal Prediction (CP) is a popular method for uncertainty quantification that converts a pretrained model's point prediction into a prediction set, with the set size reflecting the model's confidence. Although existing CP methods are guaranteed to achieve marginal coverage, they often exhibit imbalanced coverage across classes under long-tailed label distributions, tending to over cover the head classes at the expense of under covering the remaining tail classes. This under coverage is particularly concerning, as it undermines the reliability of the prediction sets for minority classes, even with coverage ensured on average. In this paper, we propose the Tail-Aware Conformal Prediction (TACP) method to mitigate the under coverage of the tail classes by utilizing the long-tailed structure and narrowing the head-tail coverage gap. Theoretical analysis shows that it consistently achieves a smaller head-tail coverage gap than standard methods. To further improve coverage balance across all classes, we introduce an extension of TACP: soft TACP (sTACP) via a reweighting mechanism. The proposed framework can be combined with various non-conformity scores, and experiments on multiple long-tailed benchmark datasets demonstrate the effectiveness of our methods.

NeurIPS Conference 2024 Conference Paper

Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards

• Xuan-Bach Le
• Dominik Wagner
• Leon Witzman
• Alexander Rabinovich
• Luke Ong

Linear temporal logic (LTL) and, more generally, $\omega$-regular objectives are alternatives to the traditional discount sum and average reward objectives in reinforcement learning (RL), offering the advantage of greater comprehensibility and hence explainability. In this work, we study the relationship between these objectives. Our main result is that each RL problem for $\omega$-regular objectives can be reduced to a limit-average reward problem in an optimality-preserving fashion, via (finite-memory) reward machines. Furthermore, we demonstrate the efficacy of this approach by showing that optimal policies for limit-average problems can be found asymptotically by solving a sequence of discount-sum problems approximately. Consequently, we resolve an open problem: optimal policies for LTL and $\omega$-regular objectives can be learned asymptotically.

NeurIPS Conference 2022 Conference Paper

Rethinking Variational Inference for Probabilistic Programs with Stochastic Support

• Tim Reichelt
• Luke Ong
• Thomas Rainforth

We introduce Support Decomposition Variational Inference (SDVI), a new variational inference (VI) approach for probabilistic programs with stochastic support. Existing approaches to this problem rely on designing a single global variational guide on a variable-by-variable basis, while maintaining the stochastic control flow of the original program. SDVI instead breaks the program down into sub-programs with static support, before automatically building separate sub-guides for each. This decomposition significantly aids in the construction of suitable variational families, enabling, in turn, substantial improvements in inference performance.

I&C Journal 2018 Journal Article

Simulating cardinal preferences in Boolean games: A proof technique

• Egor Ianovski
• Luke Ong

Boolean games are a succinct representation of strategic games with a logical flavour. While they have proved to be a popular formalism in the multiagent community, a commonly cited shortcoming is their inability to express richer utilities than success or failure. In addition to being a modelling limitation, this parsimony of preference has made proving complexity bounds difficult. We address the second of these issues by demonstrating how cardinal utilities can be simulated via expected utility. This allows us to prove that RationalNash and IrrationalNash are NEXP-hard, and to translate hardness results for IsNash and DValue into the Boolean games framework.

AIJ Journal 2018 Journal Article

The complexity of decision problems about equilibria in two-player Boolean games

• Egor Ianovski
• Luke Ong

Boolean games allow us to succinctly represent strategic games with binary payoffs in the case where the players' preferences have a structure readily expressible in propositional logic. Since their introduction, the computational aspects of Boolean games have been of interest to the multiagent community, but so far the focus has been exclusively on pure strategy equilibria. In this paper we consider the complexity of problems involving mixed strategy equilibria, such as the existence of an equilibrium satisfying a given payoff constraint. The results are obtained by the observation that a mixed strategy can hold enough information to encode the computation history of an exponential time Turing machine.

Highlights Conference 2017 Conference Abstract

ML and Extended Branching VASS

• Conrad Cotton-Barratt
• Andrzej Murawski
• Luke Ong

Abstract available in PDF.

TCS Journal 2015 Journal Article

Logic, Language, Information and Computation (WoLLIC 2012)

• Luke Ong
• Ruy J.G.B. de Queiroz

KR Conference 2014 Conference Paper

∃GUARANTEENASH for Boolean Games Is NEXP-Hard

• Egor Ianovski
• Luke Ong

While many questions have been answered, the issue of Boolean games are an expressive and natural formalism through which to investigate problems of strategic interaction in multiagent systems. Although they have been widely studied, almost all previous work on Nash equilibria in Boolean games has focused on the restricted setting of pure strategies. This is a shortcoming as finite games are guaranteed to have at least one equilibrium in mixed strategies, but many simple games fail to have pure strategy equilibria at all. We address this by showing that a natural decision problem about mixed equilibria: determining whether a Boolean game has a mixed strategy equilibrium that guarantees every player a given payoff, is NEXP-hard. Accordingly, the variety of the problem is NEXP-complete. The proof can be adapted to show coNEXP-hardness of a similar question: whether all Nash equilibria of a Boolean game guarantee every player at least the given payoff.