Smart Choices and the Selection Monad
From MaRDI portal
Publication:6135751
DOI10.46298/LMCS-19(2:3)2023arXiv2007.08926OpenAlexW3042976617MaRDI 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?)
- Modelling environments in call-by-value programming languages.
- Algebraic operations and generic effects
- On full abstraction for PCF: I, II and III
- Full abstraction for PCF
- Combining effects: sum and tensor
- Title not available (Why is that?)
- Title not available (Why is that?)
- Combining algebraic effects with continuations
- Congruences of convex algebras.
- Distributing probability over non-determinism
- Strong functors and monoidal monads
- Title not available (Why is that?)
- Kan extensions in enriched category theory
- A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on
- Sequential games and optimal strategies
- Selection functions, bar recursion and backward induction
- The Peirce translation
- Adjunctions whose counits are coequalizers, and presentations of finitary enriched monads
- Postulates for the barycentric calculus
- Convexity theories. IV: Klein-Hilbert parts in convex modules
- Layer by layer -- combining monads
- Title not available (Why is that?)
- THE HERBRAND FUNCTIONAL INTERPRETATION OF THE DOUBLE NEGATION SHIFT
- Basic Operational Preorders for Algebraic Effects in General, and for Combined Probability and Nondeterminism in Particular
- Correctness of automatic differentiation via diffeologies and categorical gluing
- On the Versatility of Open Logical Relations
- System T and the product of selection functions
- Constructive decidability of classical continuity
- Title not available (Why is that?)
- Smart Choices and the Selection Monad
Cited In (2)
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)
