Exact Reduction of Huge Action Spaces in General Reinforcement Learning

Sultan J. Majeed*, Marcus Hutter

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    4 Citations (Scopus)

    Abstract

    The reinforcement learning (RL) framework formalizes the notion of learning with interactions. Many real-world problems have large state-spaces and/or action-spaces such as in Go, StarCraft, protein folding, and robotics or are non-Markovian, which cause significant challenges to RL algorithms. In this work we address the large action-space problem by sequentializing actions, which can reduce the action-space size significantly, even down to two actions at the expense of an increased planning horizon. We provide explicit and exact constructions and equivalence proofs for all quantities of interest for arbitrary history-based processes. In the case of MDPs, this could help RL algorithms that bootstrap. In this work we show how action-binarization in the non-MDP case can significantly improve Extreme State Aggregation (ESA) bounds. ESA allows casting any (non-MDP, non-ergodic, history-based) RL problem into a fixed-sized non-Markovian state-space with the help of a surrogate Markovian process. On the upside, ESA enjoys similar optimality guarantees as Markovian models do. But a downside is that the size of the aggregated state-space becomes exponential in the size of the action-space. In this work, we patch this issue by binarizing the action-space. We provide an upper bound on the number of states of this binarized ESA that is logarithmic in the original action-space size, a double-exponential improvement.

    Original languageEnglish
    Title of host publication35th AAAI Conference on Artificial Intelligence, AAAI 2021
    PublisherAssociation for the Advancement of Artificial Intelligence
    Pages8874-8883
    Number of pages10
    ISBN (Electronic)9781713835974
    Publication statusPublished - 2021
    Event35th AAAI Conference on Artificial Intelligence, AAAI 2021 - Virtual, Online
    Duration: 2 Feb 20219 Feb 2021

    Publication series

    Name35th AAAI Conference on Artificial Intelligence, AAAI 2021
    Volume10B

    Conference

    Conference35th AAAI Conference on Artificial Intelligence, AAAI 2021
    CityVirtual, Online
    Period2/02/219/02/21

    Fingerprint

    Dive into the research topics of 'Exact Reduction of Huge Action Spaces in General Reinforcement Learning'. Together they form a unique fingerprint.

    Cite this