We propose a robust Q-learning algorithm for Markov decision processes under model uncertainty when each state--action pair is associated with a finite ambiguity set of candidate transition kernels. This finite-measure framework enables user-designed uncertainty models, including competing fitted models and stress scenarios. {The learner observes successor states and their deterministic rewards from every candidate simulator, without requiring explicit knowledge of the transition probabilities or the reward function.} We establish almost sure convergence of the learned Q-function to the robust optimum, and derive a time-uniform high-probability error certificate that separates an observable empirical Bellman residual from transition-kernel estimation error. We also give quantitative finite-ambiguity approximation results for Wasserstein and parametric uncertainty models on finite state spaces. Numerical examples illustrate the effect of scenario selection and compare the tabular algorithm with robust value iteration.
Algorithm 1 Robust Q -learning for finite ambiguity sets
State x
0
1
2
3
4
5
6
7
8
9
10
Robust, P1
1
1
1
1
1
0
0
−1
−1
−1
−1
Robust, P2
1
1
1
0
0
0
−1
−1
−1
−1
−1
Robust, P3
1
1
0
0
0
0
0
0
0
−1
−1
Robust, P4
0
0
0
0
0
0
0
0
0
0
0
Non-robust
1
1
1
1
1
0
−1
−1
−1
−1
−1
Table 1. Reference policies obtained by robust value iteration for the indicated ambiguity sets, and the non-robust reference policy.
ptrue
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Robust, P1
−0.3110
−0.1905
−0.0431
0.1567
0.3036
0.2979
0.1301
−0.1028
−0.2997
Robust, P2
−0.2438
0.0499
0.2100
0.2473
0.2267
0.1189
−0.0519
−0.1913
−0.3110
Robust, P3
−0.0774
0.1510
0.1117
0.0442
0.0211
0.0442
0.1117
0.1510
−0.0774
Robust, P4
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
Non-robust
−0.3108
−0.1851
−0.0098
0.2311
0.3541
0.2311
−0.0098
−0.1851
−0.3108
Table 2. Expected reward per step under the reference policies in Table 1 . Bold entries indicate the largest reward among the five policies at each test parameter.
Figure 1. Expected reward per step of the reference policies as a function of the binomial test parameter ptrue . The values are computed directly from the binomial probabilities.
Known kernels
Empirical kernels
N
∥QT−Q∗∥∞
Time (s)
∥QT−Q∗∥∞
Time (s)
2
0.0905±0.0368
0.160
0.0937±0.0392
0.271
5
0.0766±0.0248
0.178
0.0743±0.0253
0.692
11
0.0758±0.0207
0.186
0.0725±0.0301
1.328
Table 3. Comparison on the coin toss example. Errors are means ± sample standard deviations over five seeds; learning times are means. The empirical variant estimates candidate reward expectations from observed rewards, whereas the known-kernel variant uses exact reward expectations. The known-kernel variant uses 106 simulator calls, whereas the empirical-kernel variant uses N⋅106 calls; thus the table compares a fixed number of updates, not equal sampling budgets.
Figure 2. Supremum-norm errors for P1 (left) and P2 (right), comparing known kernels and exact reward expectations with empirical kernels and observed reward means. Lines indicate means over five seeds, and shaded regions show the corresponding minima and maxima.
Robust Q -learning
Empirical
Sample-split
Pooled nominal
n
1/n
n−0.6
robust planning
planning
planning
2
0.063709
0.039677
0.086618
0.058029
0.051647
5
0.031361
0.040422
0.052322
0.035593
0.035536
10
0.035933
0.038940
0.058389
0.038611
0.038559
20
0.039101
0.035712
0.062242
0.041117
0.028810
50
0.021770
0.031331
0.037958
0.026105
0.015235
Table 4. Mean true robust policy regret over 200,000 repetitions for p1=0.60 , p2=0.61 , and c=0.10 . The budget n is the number of observations per candidate; all methods use the same 2n stochastic simulator calls. The same policies, hence the same entries, result when rewards are learned, with two additional deterministic safe-action calls. Smaller values are better. A zero entry means that no incorrect actions were observed.
Figure 3. Mean robust policy regret in the three-state example (left, 200,000 repetitions) and the control with p2=0.45 (right, 100,000 repetitions), keeping p1=0.60 and c=0.10 . The risky action is robust-optimal on the left and the safe action on the right. The budgets and sampling conventions are the same in both panels.
Figure 4. Cumulative sums of return signs and the original training and testing windows. The numerical evaluations use the observation-index intervals specified in the text.
Test Period 1
Test Period 2
Test Period 3
Days
299
199
500
Negative returns
1078
635
1573
Positive returns
1015
758
1927
Robust ( P )
−0.0048±0.0029
−0.0035±0.0059
−0.0024±0.0027
Non-robust: Period 1 ( P1 )
−0.1071±0.0069
−0.0438±0.0071
−0.0383±0.0050
Non-robust: Period 2 ( P2 )
−0.0639±0.0057
−0.0052±0.0048
0.0121±0.0060
Table 5. Mean directional reward per time step across seven stocks. The learning rows report means ± sample standard deviations across five seeds, after averaging over stocks within each seed. Bold entries indicate the highest mean in each period.
Figure 5. The histograms illustrate the results from Table 5 .