Smart Choices and the Selection Monad
From MaRDI portal
Publication:6135751
DOI10.46298/LMCS-19(2:3)2023OpenAlexW3042976617MaRDI QIDQ6135751FDOQ6135751
Authors: Martín Abadi, Gordon D. Plotkin 
Publication date: 26 August 2023
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Abstract: Describing systems in terms of choices and their resulting costs and rewards offers the promise of freeing algorithm designers and programmers from specifying how those choices should be made; in implementations, the choices can be realized by optimization techniques and, increasingly, by machine-learning methods. We study this approach from a programming-language perspective. We define two small languages that support decision-making abstractions: one with choices and rewards, and the other additionally with probabilities. We give both operational and denotational semantics. In the case of the second language we consider three denotational semantics, with varying degrees of correlation between possible program values and expected rewards. The operational semantics combine the usual semantics of standard constructs with optimization over spaces of possible execution strategies. The denotational semantics, which are compositional, rely on the selection monad, to handle choice, augmented with an auxiliary monad to handle other effects, such as rewards or probability. We establish adequacy theorems that the two semantics coincide in all cases. We also prove full abstraction at base types, with varying notions of observation in the probabilistic case corresponding to the various degrees of correlation. We present axioms for choice combined with rewards and probability, establishing completeness at base types for the case of rewards without probability.
Full work available at URL: https://arxiv.org/abs/2007.08926
Recommendations
- Algorithm design with the selection monad
- Monads and theories
- Monads, partial evaluations, and rewriting
- Monads in action
- The constrained-monad problem
- scientific article; zbMATH DE number 4189993
- The marriage of effects and monads
- The marriage of effects and monads
- The marriage of effects and monads
- Selection over classes of ordinals expanded by monadic predicates
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A monad for probabilistic point processes
- A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on
- Adjunctions whose counits are coequalizers, and presentations of finitary enriched monads
- Algebraic operations and generic effects
- Basic Operational Preorders for Algebraic Effects in General, and for Combined Probability and Nondeterminism in Particular
- Combining algebraic effects with continuations
- Combining effects: sum and tensor
- Congruences of convex algebras.
- Constructive decidability of classical continuity
- Convexity theories. IV: Klein-Hilbert parts in convex modules
- Correctness of automatic differentiation via diffeologies and categorical gluing
- Distributing probability over non-determinism
- Full abstraction for PCF
- Kan extensions in enriched category theory
- Layer by layer -- combining monads
- Modelling environments in call-by-value programming languages.
- On full abstraction for PCF: I, II and III
- On the versatility of open logical relations. Continuity, automatic differentiation, and a containment theorem
- Postulates for the barycentric calculus
- Selection functions, bar recursion and backward induction
- Sequential games and optimal strategies
- Smart Choices and the Selection Monad
- Strong functors and monoidal monads
- System T and the product of selection functions
- The Herbrand functional interpretation of the double negation shift
- The Peirce translation
Cited In (3)
This page was built for publication: Smart Choices and the Selection Monad
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135751)
