Smart Choices and the Selection Monad
From MaRDI portal
Publication:6135751
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.
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
- scientific article; zbMATH DE number 1705158 (Why is no real title available?)
- scientific article; zbMATH DE number 6712178 (Why is no real title available?)
- scientific article; zbMATH DE number 4179333 (Why is no real title available?)
- scientific article; zbMATH DE number 3126094 (Why is no real title available?)
- scientific article; zbMATH DE number 3322506 (Why is no real title available?)
- 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)
