Solving Decision Theory Problems with Probabilistic Answer Set Programming

• URL: http://arxiv.org/abs/2408.11371v1
• Date: Wed, 21 Aug 2024 06:44:16 GMT
• Title: Solving Decision Theory Problems with Probabilistic Answer Set Programming
• Authors: Damiano Azzolini, Elena Bellodi, Rafael Kiesel, Fabrizio Riguzzi,
• Abstract summary: We introduce the possibility to encode decision theory problems with Probabilistic Answer Set Programming. Our algorithm can manage non trivial instances of programs in a reasonable amount of time.
• Score: 1.4999444543328293
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving a decision theory problem usually involves finding the actions, among a set of possible ones, which optimize the expected reward, possibly accounting for the uncertainty of the environment. In this paper, we introduce the possibility to encode decision theory problems with Probabilistic Answer Set Programming under the credal semantics via decision atoms and utility attributes. To solve the task we propose an algorithm based on three layers of Algebraic Model Counting, that we test on several synthetic datasets against an algorithm that adopts answer set enumeration. Empirical results show that our algorithm can manage non trivial instances of programs in a reasonable amount of time. Under consideration in Theory and Practice of Logic Programming (TPLP).

Related papers

• Probabilistic Answer Set Programming with Discrete and Continuous Random Variables [0.18416014644193066]
  Probabilistic Answer Set Programming (PASP) extends Answer Set Programming with probabilistic facts that represent uncertain information. We propose Hybrid Probabilistic Answer Set Programming (HPASP) We discuss, implement, and assess the performance of two exact algorithms based on projected answer set enumeration and knowledge compilation.
  arXiv  Detail & Related papers  (2024-09-30T13:24:42Z)
• Symbolic Parameter Learning in Probabilistic Answer Set Programming [0.16385815610837165]
  We propose two algorithms to solve the formalism of Proabilistic Set Programming. The first solves the task using an off-the-shelf constrained optimization solver. The second is based on an implementation of the Expectation Maximization algorithm.
  arXiv  Detail & Related papers  (2024-08-16T13:32:47Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  We provide the first provable guarantees for portfolio-based algorithm selection. We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
  arXiv  Detail & Related papers  (2020-12-24T16:33:17Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• MAP Inference for Probabilistic Logic Programming [0.30586855806896046]
  We consider the Maximum-A-Posteriori (MAP) inference task and the Most Probable Explanation (MPE) task. We present a novel algorithm, included in the PITA reasoner, which tackles these tasks by representing each problem as a Binary Decision Diagram. We compare our algorithm with the version of ProbLog that admits annotated disjunctions and can perform MAP and MPE inference.
  arXiv  Detail & Related papers  (2020-08-04T08:10:51Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  We study oracle complexity of gradient based methods for approximation problems. We focus on instance-dependent complexity instead of worst case complexity. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
  arXiv  Detail & Related papers  (2020-06-08T09:25:47Z)
• Generating Random Logic Programs Using Constraint Programming [12.47276164048813]
  We present a novel approach to generating random logic programs using constraint programming. We show how the model scales with parameter values, and use the model to compare probabilistic inference algorithms across a range of synthetic problems.
  arXiv  Detail & Related papers  (2020-06-02T19:12:53Z)
• Information-Theoretic Abstractions for Planning in Agents with Computational Constraints [16.565205172451662]
  We show how a path-planning problem in an environment can be systematically approximated by solving a sequence of easier to solve problems on abstractions of the original space. A numerical example is presented to show the utility of the approach and to corroborate the theoretical findings.
  arXiv  Detail & Related papers  (2020-05-19T17:32:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.