Source-linked AI summary
Mini-Batch Risk-Averse Deep Q-Learning: A Robot Navigation Case Study
Aayush Patel, Andrzej Ruszczyński
TL;DR
The paper addresses the difficulty of estimating nonlinear Markov risk mappings from single transitions by introducing mini-batch mappings and embedding them in a risk-averse double deep Q-network. In underwater robot navigation, the resulting policies transfer to larger unseen instances and perform better under simulator misspecification.
Problem
Nonlinear transition risk mappings cannot be estimated from a single observed transition, limiting risk-averse reinforcement learning for large-state MDPs.
Method
The method averages mini-batch transition risk mappings and embeds their unbiased estimators in a double deep Q-network with hierarchical navigation and invariant features.
Results
Under explicit destruction events away from the nominal model, the risk-averse policy dominates the risk-neutral policy in both mean and tail criteria.
Takeaways & Limitations
Mini-batch size provides an interpretable risk-aversion dial, while the hierarchical and invariant representation enables transfer to larger instances without retraining.
Takeaways & Limitations
For nonlinear risk mappings, absorbing destruction probability into a scalar discount factor is only an approximation, with error growing in ξ and N.
Abstract
from arXiv · showhide
We study the control of Markov decision processes in which the quality of a policy is evaluated by a dynamic, time-consistent Markov risk measure rather than by an expected discounted cost. The main obstacle to combining such measures with reinforcement learning is that a transition risk mapping depends on the transition kernel in a nonlinear way, and therefore cannot be estimated from a single observed transition. We remove this obstacle by employing mini-batch transition risk mappings: the mapping is applied to the empirical measure of $N$ independent next-state samples, and the result is averaged. The resulting mapping is again coherent. However, as an expected value of a function of $N$ next-state values, it admits an unbiased one-sample estimator. We embed this mapping into a double deep Q-network, analyze the two sources of estimation bias that arise, and obtain a risk-averse Q-learning method applicable to state spaces far beyond the reach of tabular schemes. The method is applied to an underwater robot navigation problem, in which a vehicle must visit collection points, gather stochastic information payloads, and deliver them at transmission points, while exposed at each step to the risk of destruction. A hierarchical decomposition delegates path execution to an exact graph search and confines learning to the high-level ``collect or transmit'' decision. A low-dimensional feature map, invariant under the symmetries of the problem, replaces the raw state--configuration encoding. In experiments on $300$ held-out environments, the resulting policies transfer to instance sizes never seen in training, and already $N=2$ reduces the upper semideviation of the outcome distribution while simultaneously improving its mean whenever the simulator is misspecified---an empirical counterpart of the duality between coherent risk measures and distributional robustness.
1 Introduction
The paper develops risk-averse reinforcement learning for large-state MDPs by replacing expected-cost evaluation with dynamic Markov risk measures and combining mini-batch mappings with deep Q-learning.
- The MDP has a potentially very large finite state space and a finite, enumerable action space.
- The objective evaluates policies with a dynamic risk-adjusted total cost rather than a standard expected discounted cost.
- Mini-batch Markov risk measures are combined with Q-factor approximations and deep Q-networks to learn risk-averse policies in large state spaces.
- The method addresses risk-aware reinforcement learning beyond prior methods designed for small state-action spaces.
- A hierarchical decomposition uses exact graph search for path execution and reserves learning for higher-level decisions.
2 Markov Risk Measures and Risk-Averse Dynamic Programming
The paper formulates time-consistent risk-averse dynamic programming through transition risk mappings, preserving contraction and coherent-risk structure while generalizing expected-value control.
- A transition risk mapping characterizes Markov risk measures and supports the policy-evaluation equation.
- Risk-averse dynamic programming selects policies through Q-factors and value functions defined analogously to the risk-neutral setting.
- The conditional expected-value mapping recovers standard expected-value dynamic programming.
- Coherent transition risk mappings satisfy convexity, monotonicity, translation, and positive homogeneity.
- The dual representation interprets coherent risk as a worst case over an ambiguity set of transition kernels.
- Nonexpansiveness makes the dynamic-programming operators contractions with modulus α, yielding unique solutions and convergence of value and policy iteration.
3 Mini-Batch Transition Risk Mappings
Mini-batch transition mappings make nonlinear transition risk estimable from sampled next states while preserving coherence and yielding an interpretable family indexed by batch size.
- Mini-batch mappings apply a risk mapping to an empirical measure formed from N independent next-state samples and average the result.
- Batch size N indexes a one-parameter family of distortion risk measures with a closed-form Kusuoka representation.
- The resulting mapping is coherent, law invariant, and comonotone additive, with a concave distortion representation.
- For N=2, mixing the mapping with conditional expectation produces the mean–Gini model.
- The family increases with N, converges to the worst-case mapping, and is consistent with increasing convex order.
- The expected-value construction provides unbiased estimators using one batch of N next states, avoiding double sampling and pointwise nonlinear-kernel estimation.
4 Risk-Averse Q-Learning with Double Deep Q-Networks
The risk-averse DDQN combines mini-batch risk targets with double-network action selection, separating two bias sources while enabling functional approximation beyond tabular Q-learning.
- Tabular Q-factors are infeasible for the application, so the method uses neural functional approximation.
- DDQN separates action selection from evaluation to remove the correlation driving single-network overestimation.
- The mini-batch Bellman target is consistent with the coherent risk mapping when expectations are taken over next-state samples.
- The batch maximum is unbiased for the mini-batch risk mapping at the current approximation, so it is not itself an estimation-bias source.
- Approximation noise propagated through the convex risk mapping creates a nonnegative pessimistic bias proportional to the worst-case weight.
- The parameters ξ and N jointly tune risk aversion, interpolating between risk-neutral and increasingly upper-tail-sensitive targets.
5 Risk-Aware Underwater Robot Navigation
The navigation problem combines stochastic information collection and destruction risk with spatial task planning. A hierarchical risk-averse DDQN learns high-level collect-or-transmit decisions while exact graph search executes paths, using a symmetry-invariant feature representation.
- Problem formulation: The robot visits collection points, gathers stochastic payloads, and delivers them at transmission points while facing destruction risk and obstacles.Collection yields high- or low-value information probabilistically, and transmission resets the carried payload.
- Risk-averse learning: The method uses a risk-averse DDQN with mini-batch transition risk, replay training, a target network, and periodically synchronized parameters.The algorithm samples multiple next states and updates the online network using a target network.
- Problem formulation: The state records the robot position, unvisited collection points, and carried payload, while termination occurs after all collections are visited and no payload remains.Destruction is also terminal through an absorbing state.
- Cost structure: The one-step cost combines stochastic collection loss, payload-dependent movement costs, and transmission rewards or empty-transmission penalties.The transition risk mapping aggregates randomness from the next-state value function, including the stochastic collection payload.
- Modeling caveat: Absorbing destruction is equivalent to discounting only for conditional expectation; with nonlinear risk mappings, the approximation error grows with risk weight and batch size.For N=2, the discrepancy is modest but nonzero, motivating evaluation with explicitly simulated destruction events.
- Decomposed training methodology: A hierarchical decomposition assigns high-level collect-or-transmit choices to DDQN and delegates low-level collision-free path execution to exact Dijkstra search.This removes low-level function-approximation error and concentrates learning on uncertain task decisions.
- Feature representation: The engineered representation uses quantities invariant under grid isometries, avoiding the raw encoding’s need to learn equivalent-state invariances.The raw representation can inflate sample requirements by a factor of order |G|.
6 Results
The experiments compare feature representations and risk-sensitive policies in underwater robot navigation. Engineered, symmetry-aware features generalize across instance sizes, while N=2 improves the risk–return profile under simulator misspecification.
- Training setup: 8000 training episodes use randomly generated configurations, with destruction absorbed into the discount factor during training.Evaluation uses held-out configurations and separate test environments.
- Feature representations: The engineered feature model uses task-relevant features, whereas the raw representation contains the full state and configuration.The comparison evaluates training loss and cumulative reward on 300 held-out validation configurations.
- Feature representations: The engineered representation converges to higher, more stable validation reward, while the raw model achieves lower training loss but worse validation reward.The raw input has dimension 5n^2 + 1, versus a fixed engineered dimension of 10, and separates states related by problem symmetries.
- Generalization: 100% success is achieved in both test configurations by the engineered-feature model across 300 held-out environments.Configuration A is a 7 × 7 grid and Configuration B is a 12 × 12 grid with different numbers of collection points, transmission nodes, and obstacles.
- Generalization: The raw-feature model obtains mean reward 236.15 and 95% success in Configuration A, but cannot accept Configuration B because its input dimension is tied to training grid size.The engineered representation transfers from the 7 × 7 setting to the 12 × 12 setting without retraining.
- Risk-sensitive evaluation: The mini-batch mapping interpolates between risk-neutral behavior at N=1 and worst-case behavior as N increases, with N=2 used in the experiments.The method replaces the Bellman conditional expectation with a coherent risk measure over sampled transitions.
- Risk-sensitive evaluation: Under misspecification, N=2 improves mean reward and reduces upper semideviation simultaneously: +1.8% and −11.8% at δ=0.05, and +35.8% and −8.6% at δ=0.10.Under the nominal model, mean reward decreases from 229.29 to 219.99 while upper semideviation decreases from 742.44 to 719.13.
7 Conclusions
The paper develops a risk-averse deep Q-learning method using mini-batch transition risk mappings and applies it to large underwater robot navigation problems. Its experiments show improved risk–return performance under simulator misspecification, while convergence, semi-Markov risk consistency, batch-size trade-offs, and explicit destruction-risk modeling remain open.
- Method: Mini-batch mappings convert nonlinear transition-kernel risk functionals into expected functions of N next-state values, enabling estimation from sampled transitions.For N=2, combining the mapping with conditional expectation yields the mean–Gini model, making batch size an interpretable risk-aversion parameter.
- Method: The double-network construction removes action-selection bias, leaving a convexity-induced bias with the conservative sign appropriate for risk-averse learning.The maximum over the mini-batch is an exact evaluation of the risk mapping conditional on network parameters.
- Case study: Hierarchical path planning and symmetry-invariant features enable learning only the uncertain high-level decision and transfer to larger instances without retraining.The engineered features do not depend on instance size, unlike the raw encoding.
- Results: Under misspecified destruction dynamics, the risk-averse policy outperforms the risk-neutral policy in both mean and tail criteria, whereas at the nominal model it sacrifices some mean for a slightly better tail.The reported interpretation connects this result to the dual representation of coherent risk measures and distributional robustness.
- Open questions: The method has no convergence guarantee for nonlinear Q-learning, and the interaction between time consistency and temporally extended actions remains unresolved.The study also leaves systematic batch-size trade-offs and explicit treatment of destruction events for future work.