IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v50y2025i2p1277-1304.html
   My bibliography  Save this article

Corruption-Robust Exploration in Episodic Reinforcement Learning

Author

Listed:
  • Thodoris Lykouris

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Max Simchowitz

    (Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Aleksandrs Slivkins

    (Microsoft Research Lab, New York, New York 10012)

  • Wen Sun

    (Department of Computer Science, Cornell University, Ithaca, New York 14850)

Abstract

We initiate the study of episodic reinforcement learning (RL) under adversarial corruptions in both the rewards and the transition probabilities of the underlying system, extending recent results for the special case of multiarmed bandits. We provide a framework that modifies the aggressive exploration enjoyed by existing reinforcement learning approaches based on optimism in the face of uncertainty by complementing them with principles from action elimination. Importantly, our framework circumvents the major challenges posed by naively applying action elimination in the RL setting, as formalized by a lower bound we demonstrate. Our framework yields efficient algorithms that (a) attain near-optimal regret in the absence of corruptions and (b) adapt to unknown levels of corruption, enjoying regret guarantees that degrade gracefully in the total corruption encountered. To showcase the generality of our approach, we derive results for both tabular settings (where states and actions are finite) and linear Markov decision process settings (where the dynamics and rewards admit a linear underlying representation). Notably, our work provides the first sublinear regret guarantee that accommodates any deviation from purely independent and identically distributed transitions in the bandit-feedback model for episodic reinforcement learning.

Suggested Citation

  • Thodoris Lykouris & Max Simchowitz & Aleksandrs Slivkins & Wen Sun, 2025. "Corruption-Robust Exploration in Episodic Reinforcement Learning," Mathematics of Operations Research, INFORMS, vol. 50(2), pages 1277-1304, May.
  • Handle: RePEc:inm:ormoor:v:50:y:2025:i:2:p:1277-1304
    DOI: 10.1287/moor.2021.0202
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.0202
    Download Restriction: no

    File URL: https://libkey.io/10.1287/moor.2021.0202?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:50:y:2025:i:2:p:1277-1304. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.