Pith. sign in

REVIEW 3 major objections 6 minor 22 references

"What are my options?": Explaining RL Agents with Diverse Near-Optimal Alternatives (Extended)

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Pith's one-line read DNA explains RL agents by returning provably near-optimal, corridor-safe alternative policies.

desk verdict The DNA algorithm was already at L4DC 2025; this arXiv version adds full proofs and a QD comparison, but the guarantees assume an exact V* while the paper implies DQNs can be used without error analysis. read the letter →

arxiv 2506.09901 v1 pith:AZKDA4ZE submitted 2025-06-11 cs.LG

classification cs.LG
keywords ExplainablereinforcementlearningDiversenear-optimalalternativesCorridorsearchRewardshapingQ-learningEpsilon-optimalityQualitydiversityStochastictrajectoryplanning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper extends a proposal called Diverse Near-Optimal Alternatives (DNA), a way to explain a reinforcement-learning agent by returning a set of distinct, near-optimal policies instead of a single optimal one. The central claim is that by partitioning the state space into corridors and solving a modified local Q-learning problem on each corridor, one can produce alternative policies that are provably $\epsilon$-optimal with respect to a benchmark and carry a guaranteed lower bound on the probability of staying inside the corridor until a terminal region is reached. If the method works as claimed, a human user can ask what options exist from a starting state and receive a menu of trajectory shapes with performance and safety-style guarantees, which also gives a stochastic-setting alternative to quality-diversity search.

What carries the argument

The load-bearing object is the local Q-learning problem built on a corridor: reward shaping that gives $(1-\gamma)V^*(s)$ at the terminal edge, zero reward plus absorption outside the corridor, and original rewards inside. The proof machinery for the guarantees is the chain of MDP comparisons in the appendix—the augmented MDP $M^\lambda$, the absorbing variant $\tilde{M}^\lambda$, and the zero-reward-sink variant $\tilde{M}^{R_0}$—which shows the alternative policy's value dominates the local value, together with a trajectory-grouping argument that separates successful from failing trajectories to obtain the success-probability bound.

What would settle it

Run DNA on an MDP where $V^*$ is known exactly, collect the returned corridors, and roll out each alternative policy many times: if any corridor passes the local $\epsilon$-optimality filter but the simulated value from the start falls below $\epsilon V^*(s_i)$, or if the measured frequency of reaching the terminal region falls below the right-hand side of Theorem 15, the paper's guarantees are contradicted. A more targeted test of the stated application domain is the same experiment with an approximate $V^*$ from a Deep Q-Network, checking whether the $\epsilon$-optimality and success-probability bounds still hold.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is a construction plus two guarantees. For any corridor (a connected chain of cells leading from a start state to a terminal edge), DNA defines a local MDP whose reward shaping pays the 'happily-ever-after' reward $(1-\gamma)V^*(s)$ upon reaching the terminal region, gives zero reward and absorption when the agent leaves the corridor, and keeps the original rewards inside. Solving the local problem yields a local policy $\pi_L$, and the final alternative policy $\hat{\pi}$ follows $\pi_L$ until it exits the corridor or reaches the terminal edge, then switches to the benchmark optimal policy $\pi^*$. Theorem 14 shows the local optimal value $V_L^*(s)$ is no greater than the value of the constructed alternative policy from the same start, so a corridor whose local value meets the $\epsilon$-optimality bar yields a genuinely $\epsilon$-optimal option. Theorem 15 lower-bounds the probability $P_{\text{success}}$ of reaching the terminal edge before leaving the corridor, using $V_L^*$, the maximum interior reward, the discount factor, and any lower bound $\tau$ on travel time to the terminal region. Together the two theorems make corridor search a prunable search over local Q-learning problems with per-option performance and safety guarantees.

Load-bearing premise

The guarantees assume exact access to the benchmark optimal value function $V^*$, which serves both as the target for $\epsilon$-optimality and as the terminal reward in the local problem; with only an approximate value function, such as a Deep Q-Network provides, the stated bounds are not guaranteed to hold.

Editorial extensions

If this is right

  • A user can query an agent from a starting state and receive several distinct trajectory shapes, each certified to be within $\epsilon$ of the optimal expected value.
  • The search over corridors can be pruned: if a corridor's local policy fails the $\epsilon$-optimality test, no extension of that corridor can pass, so complexity scales with the number of genuinely reasonable options.
  • Because the construction uses only value functions, it transfers to any value-based RL method, including Deep Q-Networks, subject to the exactness of the value estimate.
  • Theorems 14 and 15 turn corridor search into a way to generate not just explanations but also exploration subtasks: each corridor is a candidate abstract option for hierarchical or adaptive planning.
  • Compared with quality-diversity baselines in the paper's Frozen Lake experiment, DNA achieves high measured corridor-completion probability while QD baselines often fail to recover corridors, suggesting DNA handles stochastic trajectory families better.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exact-$V^*$ assumption means a practical DNA implementation should come with error bounds for approximate value functions; otherwise the options shown to a user could in principle violate the advertised $\epsilon$-optimality or safety bounds.
  • The corridor abstraction looks reusable beyond explanation: corridors could serve as abstract subtasks in hierarchical RL, turning the diversity guarantee into an exploration mechanism.
  • The success-probability bound, if combined with a certified value function, points toward a lightweight safety certificate for stochastic planners: a lower bound on the chance of completing a corridor before failing.
  • The comparison suggests a hybrid: use QD's behavior-space search to propose corridors and DNA's local Q-learning to certify and optimize each one, which could fix QD's stochastic-trajectory weakness while keeping its open-ended diversity.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. This paper proposes DNA, a post-hoc explanation method for value-based RL agents that generates a set of near-optimal alternative policies by searching over spatial corridors. The method defines local MDPs in which the agent is rewarded for staying inside a corridor and receives a happily-ever-after terminal reward (1-gamma)V*(s) upon reaching a terminal edge; solving these local problems yields policies that are claimed to be epsilon-optimal (Theorem 14) and to satisfy a lower bound on the probability of successful corridor traversal (Theorem 15). The paper includes proofs of these theorems, a complexity discussion, and a Frozen Lake proof-of-concept comparing DNA with Quality-Diversity baselines.

Significance. The idea of explaining an RL agent by presenting diverse near-optimal alternatives is timely, and the construction of local MDPs with the happily-ever-after reward is an elegant device that converts a terminal value into an equivalent continuing reward. If the guarantees hold, they provide useful, falsifiable bounds for an explainability method, and the comparison with QD is a valuable positioning. The proofs are largely self-contained and the paper is honest about its proof-of-concept status. However, the central guarantees are proven only for exact V*, while the stated application domain includes approximate DQN value functions, and the corridor-search algorithm contains a pruning step that is not valid for general MDPs. These issues need to be resolved before the claims can be accepted.

major comments (3)
  1. [Section 3, Section 5, Definitions 11-12, Theorems 14-15] The epsilon-optimality and success-probability guarantees assume exact access to the benchmark value function V*, which enters both the epsilon-optimality criterion (Definition 11) and the terminal reward of the local MDP (Definition 12). Section 3 states that in the intended application value functions are estimated with DQNs, and Section 5 repeats that any value estimator may be used, but the paper provides no error analysis for approximate V*. If the estimate overestimates V* on the terminal edge while the estimate at s0 is accurate, the local value V*_L(s0) can exceed the true value of the returned alternative policy, so the acceptance test in Algorithm 1 line 19 can admit a policy that is not epsilon-optimal with respect to the true V*; similarly, the denominator and numerator of Theorem 15's bound both depend on V*, so approximation error can invalidate the stated safety guarantee. The experiments use tabular Q-learning, which can converge to exact V*, so the guarantees are only demonstrated in the exact-value regime. The authors should either supply an error-propagation analysis (for example in terms of the sup-norm error of the estimated value function) or explicitly restrict the guarantees to exact V* and describe the approximate-value setting as heuristic.
  2. [Algorithm 1, line 8 (Section 4.4)] The pruning condition 'if max{V*(s) | s in terminal edge} < epsilon V*(s0) then continue' is not justified by the optimality-principle argument given in the text, which concerns the failure of the line-19 test for shorter corridors. A corridor can be epsilon-optimal even if all terminal-edge values are far below epsilon V*(s0), because the agent collects rewards in S_in before reaching the terminal edge. Concretely, take a two-state MDP with states s0 and sOmega, action a leading deterministically to sOmega with reward 100, all other rewards 0, gamma=0.9, V*(s0)=100, V*(sOmega)=0; with epsilon=0.5 the corridor whose terminal edge is {sOmega} has max terminal V*=0 < 50, so line 8 rejects it, while the local policy that takes action a has value 100 and is epsilon-optimal. The proof-of-concept environment has zero interior rewards, so the issue does not appear there, but the algorithm is presented for general R>=0. Line 8 should be replaced by a valid bound that accounts for interior rewards (for example, skip only if max_{S_Omega} V* + max(r_in)/(1-gamma) < epsilon V*(s0)), or removed.
  3. [Appendix A, equation (56)] In the proof of Lemma 17, the transition from equation (55) to equation (56) drops the factor p_pre and leaves a summation over i of V^pi_lambda(rho_i[t_Delta]) where the grouped trajectories share a common lambda_{t_Delta}; the correct expression should be p_pre R_pre + gamma^{t_Delta} p_pre V^pi_lambda(lambda_{t_Delta}). The intended equality is recoverable from equation (53) and from the grouping argument, but as printed the proof step is incorrect. In addition, the appendix never explicitly states which policy pi is used to conclude Theorem 14: the inequality V*_L(s) <= V^hatpi((s,0)^T) follows by applying the lemma to pi = hatpi and using V*_L = Vtilde^hatpi_R0, and this step should be spelled out.
minor comments (6)
  1. [Section 4.4, equation (10)] The text says that for k=2 the number of corridors is n = sum_{b=0}^B 4^b, but equation (10) gives n = sum_{b=0}^B (2k)^{b+1} = sum_{b=0}^B 4^{b+1}; please make the indexing consistent.
  2. [Theorem 15] The bound is undefined when max_{s in S_Omega} V*(s) = 0 and vacuous when V*_L(s_t) <= max(r_in)/(1-gamma); the authors should state the non-degeneracy conditions under which the bound is meaningful.
  3. [Definition 11] The epsilon-optimality ratio V^pi(s_i)/V*(s_i) requires V*(s_i) > 0; the paper should state this assumption explicitly.
  4. [Section 3] The remark that trajectories are Lipschitz continuous with respect to the Manhattan norm is not used anywhere in the paper; either use it or remove it.
  5. [Algorithm 1, lines 11-18] The Q-learning loop does not specify the exploration policy, learning rate, or convergence criterion; for reproducibility, please provide these details.
  6. [Section 5, Table 1] The experimental results report a single run without repeated seeds or error bars; since the environment is stochastic, please report variance across seeds or state explicitly that the results are illustrative.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorems 14 and 15 are proven derivations from the local-MDP construction, not restatements of the algorithm's acceptance thresholds.

full rationale

Walking the claimed derivation chain, the load-bearing guarantees are Theorem 14 (the epsilon-optimality bound V*_L(s) <= V^{hat pi}((s,0)^T)) and Theorem 15 (the lower bound on the success probability P_success). Neither reduces to its own inputs. Algorithm 1 accepts a corridor only when the local value satisfies V(s_0) >= epsilon V*(s_0) (lines 8 and 19), but the paper's claimed guarantee concerns the actual value of the returned alternative policy V^{hat pi}; the gap is bridged by Theorem 14, which is a proven inequality (Appendix A, Lemmas 16-18) comparing the local problem's value with the true value of the policy, relying on R >= 0 and on the 'happily-ever-after' reward (1-gamma)V*(s) in Definition 12. This is a derived result rather than a definitional identity: V^{hat pi} is not defined in terms of V*_L, and the inequality is strict in general because exits at non-terminal states earn 0 in the local problem but a nonnegative continuation under pi*. Theorem 15 follows by bounding the rewards of success and failure trajectories and rearranging (Appendix B), and Table 1 tests the bound against an independently measured success rate (n=500), so it is not fitted. Using V* both as the Definition 11 benchmark and as the Definition 12 terminal reward is an input to a post-hoc explanation method, not a fitted parameter renamed as a prediction. The self-citation of the authors' L4DC version (Brindise et al. 2025) is present but not load-bearing, because all key theorems and proofs appear in this paper's appendix. The genuine caveats are correctness and scope limitations, not circularity: the guarantees assume an exact optimal value function V*, while Section 3 ('In our application, value functions are estimated using Deep Q networks (DQN)') and Section 5 ('any method may be used which estimates a value function, such as a Deep Q-Network') assert compatibility with approximate estimators without an error analysis, and Section 6 concedes the work 'is conceptual in nature.' If the value estimate overestimates V* on the terminal edge, the epsilon-optimality and success-probability bounds may fail to transfer; this is a robustness risk, not a circular reduction.

Assumptions & free parameters 3 free parameters · 4 assumptions · 2 invented entities

The paper introduces no new physical entities or fitted parameters that would make the result circular. The free parameters are user choices for the algorithm. The key input is the benchmark V*, which is standard for post-hoc explanation methods.

free parameters (3)
  • epsilon = 0.99 and 0.90 in experiments
    User-defined suboptimality threshold that determines which corridors are returned. It is chosen by hand and directly controls the set of options.
  • corridor length B and cell size d = B=4, d not specified numerically in the text
    These define the corridor geometry and are set by the user. They are not fitted to data but affect the search space and the resulting options.
  • discount factor gamma = not reported in the experiments
    Used in all value functions and in the success probability bound. It is a standard RL hyperparameter, not fitted in this paper.
assumptions (4)
  • domain assumption The MDP has a finite state space and nonnegative rewards R >= 0.
    Stated after Definition 1 and used in the geometric series bounds in the proof of Theorem 15.
  • domain assumption The optimal value function V* and optimal Q function Q* are known exactly.
    Definition 12 uses V* as terminal reward, and Algorithm 1 requires Q* as input. The guarantees in Theorems 14 and 15 assume exact V*.
  • standard math Q-learning converges to the optimal value function for the local problem.
    The algorithm relies on tabular Q-learning convergence to compute V*_L; this is standard but not proven in the paper.
  • ad hoc to paper Corridors are finite sequences of adjacent square cells, and transitions on the grid only move to neighboring states.
    Definitions 8 and 9 specify the corridor structure used in the proof and experiments. This is a modeling choice specific to this work.
invented entities (2)
  • Corridor
    purpose: A spatial region constraining trajectories to produce distinct policy options.
    The corridor is a methodological construct introduced by the paper. It is not independently observable but is defined directly in the algorithm.
  • Local MDP with happily-ever-after reward
    purpose: A modified reinforcement learning problem that rewards reaching the terminal edge and penalizes leaving the corridor.
    This is a designed construct, not an empirical entity. It is the mechanism behind the guarantees.

how reviews work

0 comments
Cite this review

Pith. "Pith review of "What are my options?": Explaining RL Agents with Diverse Near-Optimal Alternatives (Extended)." pith.science (2026). https://pith.science/paper/AZKDA4ZE

@misc{pith2026250609901,
  author       = {Pith},
  title        = {Pith review of: "What are my options?": Explaining RL Agents with Diverse Near-Optimal Alternatives (Extended)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AZKDA4ZE}},
  note         = {Machine review of arXiv:2506.09901}
}
read the original abstract

In this work, we provide an extended discussion of a new approach to explainable Reinforcement Learning called Diverse Near-Optimal Alternatives (DNA), first proposed at L4DC 2025. DNA seeks a set of reasonable "options" for trajectory-planning agents, optimizing policies to produce qualitatively diverse trajectories in Euclidean space. In the spirit of explainability, these distinct policies are used to "explain" an agent's options in terms of available trajectory shapes from which a human user may choose. In particular, DNA applies to value function-based policies on Markov decision processes where agents are limited to continuous trajectories. Here, we describe DNA, which uses reward shaping in local, modified Q-learning problems to solve for distinct policies with guaranteed epsilon-optimality. We show that it successfully returns qualitatively different policies that constitute meaningfully different "options" in simulation, including a brief comparison to related approaches in the stochastic optimization field of Quality Diversity. Beyond the explanatory motivation, this work opens new possibilities for exploration and adaptive planning in RL.

Figures

Figures reproduced from arXiv: 2506.09901 by the authors.

Figure 1
Figure 1. (Local Q-Learning Illustrated) Simulated corridor |C| = 3 with local MDP reward shaping applied. Theorem 14, informally: Our method will train a local policy πL on a local problem in order to construct the final policy option πˆ. Theorem 14 considers the expected reward V ∗ L found from optimizing πL on the local problem and compares it with the (unknown) expected reward V πˆ for the final policy. In particular, the… view at source ↗
Figure 2
Figure 2. (Corridor 1 with ϵ = 0.99 sub￾optimality.) Arrows indicate the local policy actions [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

22 extracted references · 18 canonical work pages

  1. [1]

    Towards explainable road navigation systems

    Khalid Alsheeb and Martim Brand \ a o. Towards explainable road navigation systems. In 2023 IEEE 26th International Conference on Intelligent Transportation Systems (ITSC), pages 16--22. IEEE, 2023

  2. [2]

    Lipschitz continuity in model-based reinforcement learning

    Kavosh Asadi, Dipendra Misra, and Michael Littman. Lipschitz continuity in model-based reinforcement learning. In International Conference on Machine Learning, pages 264--273. PMLR, 2018

  3. [3]

    Aldo Faisal

    Benjamin Beyret, Ali Shafti, and A. Aldo Faisal. Dot-to-dot: Explainable hierarchical reinforcement learning for robotic manipulation. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5014--5019, 2019. doi:10.1109/IROS40897.2019.8968488

  4. [4]

    'why not this mapf plan instead?'contrastive map-based explanations for optimal mapf

    Martim Brand \ a o and Yonathan Setiawan. 'why not this mapf plan instead?'contrastive map-based explanations for optimal mapf. In ICAPS 2022 Workshop on Explainable AI Planning, 2022

  5. [5]

    Pointwise-in-Time Explanation for Linear Temporal Logic Rules

    Noel Brindise and Cedric Langbort. Pointwise-in-time explanation for linear temporal logic rules. arXiv preprint arXiv:2306.13956, 2023

  6. [6]

    what are my options?

    Noel Brindise, Vijeth Hebbar, Riya Shah, and Cedric Langbort. “what are my options?": Explaining rl agents with diverse near-optimal alternatives. In Necmiye Ozay, Laura Balzano, Dimitra Panagou, and Alessandro Abate, editors, Proceedings of the 7th Annual Learning for Dynamics &amp; Control Conference, volume 283 of Proceedings of Machine Learning Resear...

  7. [7]

    The emerging landscape of explainable automated planning and decision making

    Tathagata Chakraborti, Sarath Sreedharan, and Subbarao Kambhampati. The emerging landscape of explainable automated planning and decision making. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20 , pages 4803--4811. International Joint Conferences on Artificial Intelligence O...

  8. [8]

    Quality-diversity optimization: a novel branch of stochastic optimization

    Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, and Jean-Baptiste Mouret. Quality-diversity optimization: a novel branch of stochastic optimization. In Black Box Optimization, Machine Learning, and No-Free Lunch Theorems, pages 109--135. Springer, 2021

Show all 22 references
  1. [9]

    Memory-based explainable reinforcement learning

    Francisco Cruz, Richard Dazeley, and Peter Vamplew. Memory-based explainable reinforcement learning. In AI 2019: Advances in Artificial Intelligence: 32nd Australasian Joint Conference, Adelaide, SA, Australia, December 2--5, 2019, Proceedings 32, pages 66--77. Springer, 2019

  2. [10]

    Trajectory-based explainability framework for offline rl

    Shripad Vilasrao Deshmukh, Arpan Dasgupta, Chirag Agarwal, Nan Jiang, Balaji Krishnamurthy, Georgios Theocharous, and Jayakumar Subramanian. Trajectory-based explainability framework for offline rl. In 3rd Offline RL Workshop: Offline RL as a''Launchpad'', 2022

  3. [11]

    Explainable reinforcement learning via model transforms

    Mira Finkelstein, Nitsan levy, Lucy Liu, Yoav Kolumbus, David C Parkes, Jeffrey S Rosenschein, and Sarah Keren. Explainable reinforcement learning via model transforms. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Informatio...

  4. [12]

    Uncertain quality-diversity: Evaluation methodology and new methods for quality-diversity in uncertain domains, 2023

    Manon Flageat and Antoine Cully. Uncertain quality-diversity: Evaluation methodology and new methods for quality-diversity in uncertain domains, 2023. URL https://arxiv.org/abs/2302.00463

  5. [13]

    Establishing appropriate trust via critical states

    Sandy H Huang, Kush Bhatia, Pieter Abbeel, and Anca D Dragan. Establishing appropriate trust via critical states. In 2018 IEEE/RSJ international conference on intelligent robots and systems (IROS), pages 3929--3936. IEEE, 2018

  6. [14]

    Explainable reinforcement learning through a causal lens

    Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. Explainable reinforcement learning through a causal lens. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 2493--2500, 2020

  7. [15]

    A survey of explainable reinforcement learning

    Stephanie Milani, Nicholay Topin, Manuela Veloso, and Fei Fang. A survey of explainable reinforcement learning. arXiv preprint arXiv:2202.08434, 2022

  8. [16]

    Illuminating search spaces by mapping elites

    Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909, 2015

  9. [17]

    Explaining black box reinforcement learning agents through counterfactual policies

    Maria Movin, Guilherme Dinis Junior, Jaakko Hollm \'e n, and Panagiotis Papapetrou. Explaining black box reinforcement learning agents through counterfactual policies. In International Symposium on Intelligent Data Analysis, pages 314--326. Springer, 2023

  10. [18]

    Comparing explanations in rl

    Britt Davis Pierson, Dustin Arendt, John Miller, and Matthew E Taylor. Comparing explanations in rl. Neural Computing and Applications, pages 1--12, 2023

  11. [19]

    Pugh, Lisa B

    Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, 3, 2016. ISSN 2296-9144. doi:10.3389/frobt.2016.00040. URL https://www.frontiersin.org/articles/10.3389/frobt.2016.00040

  12. [20]

    Fontaine, David H

    Bryon Tjanaka, Matthew C. Fontaine, David H. Lee, Aniruddha Kalkar, and Stefanos Nikolaidis. Training diverse high-dimensional controllers by scaling covariance matrix adaptation map-annealing, 2023 a

  13. [21]

    pyribs: A bare-bones python library for quality diversity optimization

    Bryon Tjanaka, Matthew C Fontaine, David H Lee, Yulun Zhang, Nivedit Reddy Balam, Nathaniel Dennler, Sujay S Garlanka, Nikitas Dimitri Klapsis, and Stefanos Nikolaidis. pyribs: A bare-bones python library for quality diversity optimization. In Proceedings of the Genetic and Ev...

  14. [22]

    Explainable deep reinforcement learning: state of the art and challenges

    George A Vouros. Explainable deep reinforcement learning: state of the art and challenges. ACM Computing Surveys, 55 0 (5): 0 1--39, 2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.