acceptodds
Under review as a conference paper at ICLR 2027

Dynamic Minimax Regret Optimization for Robust LLM Post-Training

Abstract

Modern LLM training increasingly relies on heterogeneous data sources spanning different domains, tasks, preference distributions, and difficulty levels. We study *dynamic minimax regret* for group-distributionally robust LLM post-training under instantaneous mini-batch-only bandit feedback. The framework views the training as a two-player sampler-optimizer process: a sampler adaptively selects among data sources using bandit feedback, while an optimizer updates the model parameters using stochastic gradients from the selected source. We focus on the practically restrictive setting where source losses evolve with model training but historical data are not re-evaluated, requiring the sampler to track instantaneous worst-sources from stale partial feedback. We propose DUCB-OGD, a simple and scalable algorithm that couples a Discounted Upper-Confidence-Bound sampler with an Online Gradient Descent optimizer. The sampler maintains exponential moving average loss estimates and confidence radii based on discounted effective sample sizes, avoiding costly re-evaluation of past data or intrusive changes to standard training pipelines. For data sources and training steps, we prove that DUCB-OGD achieves a dynamic minimax regret of , which is optimal up to logarithmic factors for the undiscounted objective under our feedback model. Extensive experiments across supervised fine-tuning, preference optimization, and reinforcement learning show that DUCB-OGD integrates seamlessly into modern LLM training pipelines and improves worst-group robustness with negligible computational overhead compared with standard sampling baselines.

Primary area:
learning theory
Keywords:
LLM post-training, group-distributionally robust optimization, dynamic minimax regret, adaptive data sampling, discounted UCB

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_EJPoOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the problem of robust LLM post-training, aiming at minimizing the maximal loss over all potential domains. The paper fomulate this problem as an online learning regret minimization problem, and then identified a regret decomposition that upper bound the regret with the regret of a online optimization, plus the regret of bandit with drifting reward. Algorithms for these problems, together, indicate an regret upper bound of O(K1/4T3/4)O(K^{1/4}T^{3/4}) regret upper bound, thus a sample complexity upper bound of O(K1/4T−1/4)O(K^{1/4}T^{-1/4}). The paper further conducts experiment on three training objectives and two models.

Critical strengths
  1. This paper provide a pretty clean mathematical formulation of robust online post-training. This formulation naturally leads to the application of algorithms like online gradient descent and non-stationary bandit algorithm.
  2. The paper is generally cleanly written and easy to follow.
Critical weaknesses
  1. The problem setup introduces several (seemingly) quite strong assumptions. While it is reasonable to make some assumptions for technical simplicty, the following assumptions might be too strong in practice and lacks corresponding justification
    1. Assumption 1 requires that the algorithm output is restricted to a pretty narrow area. This might not be realistic in LLM practice.
    2. Similarily, Assumption 2 requires the loss function to be Lipschitz. This might be not sufficiently realistic, as the landscape of the loss induced by LLM might be very spiky
  2. The problem setup it self assume several separate data sources. However, in practice, given a dataset that mixes different domain, how should the learner reliably divide the training set so that different part represent different source?
  3. The experiment setup is not clear enough. One of the key problem setup is the assumption of separate KK data source. However, in the presentation of Section 4.1, it is unclear whether the adopted datasets have such explicit separation.
    1. Also, could the author explain why the dataset for DPO and GRPO differes?
  4. It looks like that DUCB sometimes leads to inferior performance compare to baselines.
    1. Could the author clarify if there is any additional advantage of DUCB over other non-uniform baselines?
    2. Could the author provide discussion on the performance of DUCB? If it is due to discrepancy between theory and practice, then which assumptions in theory might be violated?
Questions for authors

See weakness section.

2 comments
AuthorsOpenReview ↗

Assumption Clarification, Source Construction, and Empirical Performance

We thank the reviewer for requesting clearer explanations of the assumptions, source construction, and evaluation metrics. We have also refined the assumption statements (page 4, lines 182 - 188), and further clarified the experimental setup (page 7, line 368 - 415) accordingly in the updated PDF.

Weakness 1: Clarification of Bounded-Domain and Lipschitz Assumptions

  1. Assumption Relevance: Assumptions 1 and 2 are used only for the convex OGD analysis and do not claim that a transformer is globally Lipschitz over its full parameter space. It also does not require this region to be narrow or successive iterates to remain close to a fixed point. Contrarily, we state the bounded domain condition for the iterates visited by the training trajectory and require Lipschitzness only on a bounded region containing the iterates visited during model training.

  2. Empirical Justification: We report empirical diagnostics in Appendix-D.5, which shows the maximum per-step source-loss variations are modest (0.06-0.17 across all tasks). These observations are consistent with the slowly-varying and trajectory-level Lipschitzness interpretation used by the analysis.

  3. Regularization During Practical Training: Practical training mechanisms also help keep the optimization trajectory bounded through techniques such as gradient clipping. Moreover, LLM post-training commonly employs KL regularization with respect to a reference model. This mechanism discourages large deviations from the fixed reference model, which further supports the boundedness condition.

Weaknesses 2 & 3: Data Source Definition and Dataset Selection

  1. Data Source Definition: Our framework assumes that each training example has a source label before training. The sampler first selects a source and then draws a mini-batch from the corresponding subset. In our experiments, these labels are obtained directly from dataset domains or task categories:

    • SFT: Tulu-v2 contains Math (for math reasoning) and Orca (for instruction following) subsets, regarded as two sources;
    • DPO: HelpSteer3 contains three problem types including Code, Multilingual, and STEM, regarded like three sources;
    • GRPO-Reasoning: Reasoning is an aggregated dataset of three reasoning tasks including Arc, Countdown, and Zebra, regarded as three sources;
    • GRPO-CommonsenseQA: CommonsenseQA contains four question answering categories including Social, Physical, Causal-Temporal, and General, regarded as four sources.
  2. Datasets of DPO v.s. GRPO: DPO and GRPO use different datasets because they require different forms of supervision: DPO requires paired preferred-dispreferred responses, whereas GRPO requires prompts with task-compatible reward signals for on-policy rollouts. They use different datasets because they belong to fundamentally different task families..

Weakness 4: When DUCB Helps and Why It Can Underperform

  1. The Robustness Objective and Minimum Source-Wise Performance: The robust learning problem studied in our framework targets minimum source-wise performances rather than average accuracy. In the six main settings, our proposed DUCB achieves the highest minimum accuracy in five settings and remains competitive with the top performing baseline (i.e. AMA-S) in the remaining setting. We note that some baselines obtain higher average accuracies due to the expected minimum-average trade-off, since DUCB tends to allocate more training budget to the data source with comparatively worse performances.

  2. Advantages of DUCB Compared to Other Baselines: DUCB’s practical advantage is strongest when the worst source changes during training (as shown in Tab-1, Sec-4.3, and Appendix-D.5). It is also suitable when only instantaneous mini-batch feedback is available or affordable. For example, although AMA-S slightly exceeds DUCB in one of the DPO settings, it requires training KK additional source-specific specialist models. In contrast, DUCB requires no auxiliary model training or historical re-evaluation, maintains only O(K)O(K) scalar sampler state, and has per-step runtime comparable to Uniform sampling.

  3. Relation Between Theory and Empirical Performances: The proposed theory provides a regret guarantee for population training losses under convexity and regularity assumptions. The mismatch between training loss as a sampling signal and downstream evaluation metrics could also affect the performance of different algorithms, since minimizing the training loss is not always equivalent to minimizing the downstream worst-source accuracy.

Nevertheless, although the theoretical bounds does not guarantee that DUCB will dominate every specialized baseline in finite-horizon downstream task accuracy, the strong minimum-accuracy results of DUCB across five of the six main settings suggests that the proposed DUCB has considerable practical relevance.

I thank the authors for the detailed responses. I have updated my rating accordingly.

Reviewer_GhJiOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies robust LLM post-training across heterogeneous data sources through the lens of dynamic minimax regret. The authors argue that the worst-performing data source can change throughout training, making static sampling strategies insufficient for maintaining worst-group robustness. To address this challenge, they propose DUCB-OGD, which combines a Discounted Upper Confidence Bound (DUCB) sampler with Online Gradient Descent (OGD). The method adaptively prioritizes underperforming data sources using discounted historical loss estimates and confidence bounds, requiring only instantaneous mini-batch feedback without additional model evaluations or historical data replay. The authors establish a dynamic minimax regret bound of (\widetilde{\mathcal O}(K^{1/4}T^{3/4})) under convexity and regularity assumptions and claim matching minimax optimality up to logarithmic factors. Experiments across supervised fine-tuning (SFT), direct preference optimization (DPO), and reinforcement learning (GRPO), involving multiple LLM families and model sizes, demonstrate improvements in worst-source accuracy over several baselines with negligible computational overhead.

Critical strengths

1. Practical and computationally efficient framework. The proposed method addresses dynamic worst-source tracking using only instantaneous mini-batch feedback, without historical data re-evaluation or additional model evaluations. This makes it practical for large-scale LLM post-training with negligible computational overhead.

2. Broad empirical evaluation. Experiments across SFT, DPO, and GRPO, involving multiple LLM families, demonstrate improvements in worst-source performance over several baselines, supporting the method's practical applicability.

Critical weaknesses

1. Limited algorithmic novelty and insufficient comparisons. Dynamic data sampling and UCB-based worst-source tracking have already been explored in prior work. In particular, UCB-OGD [1] already combines UCB sampling with online gradient descent for robust learning. The proposed DUCB-OGD primarily replaces historical re-evaluation with discounted loss estimation. However, the paper lacks direct performance comparisons with UCB-OGD, while several other baselines are evaluated only through simplified implementations. This makes it difficult to establish the significance of the proposed contribution.

2. Concerns about theoretical correctness. The proof of Lemma 4 appears to contain an invalid inequality: it effectively drops a sampling indicator when summing increments that can be negative due to discounting. The stated bound admits counterexamples, potentially invalidating the subsequent bandit regret analysis and the main theoretical guarantee. Furthermore, the claimed matching minimax lower bound lacks a complete justification. These issues substantially undermine the paper's central theoretical contribution.

Reference

[1] Zang et al. "Adaptive Data Collection for Robust Learning Across Multiple Distributions." Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.

Questions for authors

1. Validity of the theoretical guarantee. In the proof of Lemma 4, the summation appears to drop the sampling indicator despite the possibility of negative increments caused by discounting. Could the authors clarify why this inequality holds and provide a rigorous justification? If it does not hold generally, how would this affect the bandit regret bound and Theorem 2?

2. Novelty and comparison with UCB-OGD. Given that UCB-OGD [1] already combines UCB sampling with online gradient descent for dynamic worst-source tracking, could the authors clarify the fundamental algorithmic novelty beyond discounted loss estimation? Could the authors also provide direct empirical comparisons with UCB-OGD to demonstrate the benefits and trade-offs of the proposed approach?

3. Justification of the minimax lower bound. Theorem 6 claims a matching minimax lower bound, but the paper does not provide a complete construction establishing this result for the coupled sampler-optimizer setting. Could the authors provide a rigorous proof and clarify how the lower bound on the decomposed regret establishes optimality for the original dynamic minimax regret objective?

6 comments
AuthorsOpenReview ↗

Instantaneous Feedback, Comparison to UCB, and Baseline Faithfulness (1/2)

We thank the reviewer for requesting clearer positioning relative to Zang et al. and identifying the gap in the proof of Lemma 4. We have made further clarifications and added a direct comparison with replay-based UCB by Zang et al.

Weakness-1 & Question-2: Novelty Compared to Zang et al

We agree that the dynamic worst-source tracking and the UCB-OGD structure is proposed by Zang et al. Our claimed contributions are the development of theoretical guarantees under a substantially weaker and more practical feedback oracle, together with implementation and evaluation in LLM post-training tasks.

We highlight two following aspects:

  1. Theoretical Guarantees Under Instantaneous Mini-Batch-Only Feedback: Zang et al. refresh source loss estimates by re-evaluating accumulated historical samples under the current model. Our sampler observes only the loss of the currently selected mini-batch and must track all source losses from stale partial feedback. This yields a replay-free formulation that tracks the population loss, without requiring auxiliary loss observations or the replay-to-population generalization step used by the analysis and algorithms of Zang et al.

  2. Computational and Implementation Consequences for LLM Post-Training: Our proposed replay-free design is particularly relevant for LLM post-training, which yields stricter computation and implementation constraints. In our case, auxiliary forward passes are expensive and replay evaluation requires intrusive modifications to established training libraries (such as TRL/veRL), which disrupts the regular training pipeline.

The comparison below further quantifies these aspects.

Weakness-1 & Question-2: Direct Comparison with Replay-UCB by Zang et al.

We add a controlled comparison between our proposed DUCB with Replay-UCB by Zang et al. on the DPO task using Qwen2.5-3B-Instruct model on the HelpSteer3 dataset under the same experimental setup. We run all methods over the same training sample pool for 500 steps on an NVIDIA RTX 4090 GPU.

Following the interval-based scheme adopted by Zang et al., Replay-UCB maintains a linearly growing historical sample buffer. We control the total replay budget at 8,640 evaluations across different replay intervals.

MethodMin Acc.Avg Acc.Throughput (Tok./s)Replay Time
DUCB (Ours)77.91 ±\pm 2.4180.08 ±\pm 1.312.62k0 min
Replay-UCB (replay interval = 50)67.8872.632.64k54.3 min
Replay-UCB (replay interval = 40)68.0672.952.63k54.1 min
Replay-UCB (replay interval = 25)68.4873.242.64k54.4 min

The results show that our proposed DUCB outperforms Replay-UCB by a noticeable margin. We provide complete results in Sec-4.3 and Appendix-D.7, while emphasizing on the following aspects:

  1. Computational Efficiency: For both DUCB and Replay-UCB, the measured optimizer throughputs are nearly identical, confirming that total training budget is consistent across runs. Notably, replay scoring by itself adds around 54 minutes of wall-clock time on an NVIDIA RTX 4090 GPU compared to DUCB, which takes up approximately 30% of the entire training while providing no clear performance benefit. A full history re-evaluation would incur even greater cost.

  2. Replay Interval and Allocation: Increasing the replay re-evaluation frequency only improves minimum and average accuracies marginally relative to its gap with DUCB. This is potentially associated with budget allocation: the training samples of Replay-UCB is dominated by mostly one source, suggesting that repeated re-evaluation over previously trained samples can reinforce sources with high observed empirical losses, causing imbalanced training.

  3. Connection to the Theoretical Framework: We further observe a mismatch in Replay-UCB between the replay-estimated worst source (STEM, occupying most of the budget) and the actual worst sources in evaluation (Code and Multilingual). More generally, this mismatch between replay and population distributions needs to be resolved (both theoretically and experimentally) by an additional generalization condition in Zang et al., which is not required in our proposed replay-free framework.

Weakness-1: Baseline Faithfulness

We would like to clarify the status and design choice of the non-uniform baselines:

  • AMA-R, AMA-S, and DUMP are faithful implementations;
  • DynamixSFT and MT-GRPO are implemented as sampler-only.

The latter is because the rest of the components in their baselines, such as the virtual updates scheme in DynamixSFT and the rollout filtering scheme in MT-GRPO, are irrelevant to sampler design.

These components are not directly compatible with a uniform comparison across different samplers since they do not translate across tasks. Thus the integration of such mechanisms with different sampling methods is beyond the scope of the current work.

AuthorsOpenReview ↗

Revision of Lemma 4 and Component-Wise Lower-Bound Balance (2/2)

We thank the reviewer for the careful theoretical scrutiny. We have revised the proof Lemma 4 and its downstream arguments while preserving the upper-bound rates. We also further clarified the component-wise scope of Theorem 6.

Weakness-2 & Question-1: Revision of Lemma 4 and Related Arguments

The missing term in the previous proof is caused by an attempt of unnecessary per-source bound. The original statement also omits the actual conditions on β\beta and γ\gamma used by the regret analysis.

We correct this by stating the lemma directly for the aggregate selected-source quantity under β∈[1/2,1]\beta\in[1/2,1] and γ∈[1−T−1,1]\gamma\in[1-T^{-1},1]. Because exactly one source is selected per round, this aggregation isolates the selected-source increment, and the signed term can then be bounded by its positive part. The corrected statement is as follows.

Lemma 4. Suppose T≥K+1T\ge K+1, β∈[1/2,1]\beta\in[1/2,1], and γ∈[1−T−1,1]\gamma\in[1-T^{-1},1]. Then ∑t=K+1TγT−tNtkt(β)≤2K12NT(β)12+4K12NT(γ)NT(β)−12.\sum_{t=K+1}^T \frac{\gamma^{T-t}}{\sqrt{N_t^{k_t}(\beta)}} \le 2 K^\frac{1}{2} N_T(\beta)^\frac{1}{2} + 4 K^\frac{1}{2} N_T(\gamma) N_T(\beta)^{-\frac{1}{2}}.

The revised statement introduces an additional K1/2K^{1/2} factor in the second term compared to the previous result. After substituting H(β)=η−2/3K1/3H(\beta)=\eta^{-2/3}K^{1/3} in the analyses of Propositions 9 and 10, the normalized bandit regret remains the same as O~(η1/3K1/3T)\tilde{O}(\eta^{1/3}K^{1/3}T). Consequently, with η=K−1/4T−3/4\eta=K^{-1/4}T^{-3/4}, the final upper bound also remains the same as O~(K1/4T3/4)\tilde{O}(K^{1/4}T^{3/4}) in Theorem 2.

The revised PDF (page 20, lines 1026 - 1071) provides the corrected lemma, and the corresponding arguments in the proof of Proposition 9 and 10 are also updated (page 21 - 23).

Weakness-2 & Question-3: Scope of the Component-Wise Lower Bound Balance

We agree that respective lower bounds for optimization and bandit components do not by themselves construct a coupled hard instance for minimax lower bound. We have revised the name of Theorem 6 to be Component-Wise Lower Bound Balance, which establishes a tuning benchmark for the two lower bounds by adjusting the shared learning rate.

The connection between the componentwise benchmark and our upper bound is through their shared dependence on the learning rate. Specifically, the optimization and slowly varying bandit upper bounds match the lower bounds in their respective problem classes. Since the learning rate η\eta is a hyperparameter shared by both components, it serves as a natural tuning factor, giving the order-wise balance: inf⁡η>0max⁡{η−1,K1/3η1/3T}=K1/4T3/4.\inf_{\eta>0} \max \bigl\lbrace \eta^{-1}, K^{1/3} \eta^{1/3} T \bigr\rbrace = K^{1/4} T^{3/4}. At the balancing choice of η=K−1/4T−3/4\eta=K^{-1/4}T^{-3/4}, the upper bound in Theorem 2 matches this component-wise balance. This means that our upper bound attains the same polynomial rate as the best joint tuning of the separately optimal component rates.

In the updated PDF, we revise the statement of Theorem 6 and provide explicit definition of algorithm admissibility. We have also adjusted the wording throughout the paper and describe the upper bound as “matching the optimal component-wise balance” to avoid confusion (including page 6, lines 319 - 328 as well as abstract and introduction). We leave the construction of a coupled hard instance as future work.

Thank you for the clarification. While I acknowledge the distinction from Zang et al. (2025), my concerns regarding the theoretical rigor, novelty, and experimental reliability remain insufficiently addressed. Therefore, I will maintain my original score.

Reviewer_ZaXrOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper formulates selecting at the minibatch level the training data from multiple data sources/domains dynamically during training as a (slowly) varying multi armed bandit, and propose a UCB algorithm that minimizes dynamic minimax regret defined in terms of the worst performing data source/domain.

Critical strengths
  • Mixture of data sources are common in LLM post training, framework is general and applicable
  • Principled algorithm, easy to implement, with little overhead, which makes it practical
  • Theoretical guarantees and experiments that showcase performance across varied settings
Critical weaknesses

Mixed-source sampling, the double-EMA, and exploration phase lack ablations.

Questions for authors

Clarification: How (or where if i missed it) is an admissible algorithm defined in Theorem 6? Shouldn't the statement restrict K>1? Future work: Running seeds for more of the experimental results, and experiments with more numerous and heterogeneous data sources.

1 comment
AuthorsOpenReview ↗

Component Ablations, Admissibility, and Additional Seeds

We thank the reviewer for the comments and suggestions. We have added the ablations, clarified admissibility, and further discussed the multi-seed results in the updated PDF.

Weakness: Ablation Study

We train a Qwen2.5-3B-Instruct for DPO on the Helpsteer3 dataset for 500 steps over three random seeds, ablating enforced exploration, double EMA (DEMA), and mixed-source sampling.

VariantMin Acc.Avg Acc.Δ\Delta Min Acc.Δ\Delta Avg Acc.
Full DUCB77.91 ±\pm 2.4180.08 ±\pm 1.31--
No Enforced-Exploration77.50 ±\pm 1.5679.78 ±\pm 0.74−0.41−0.30
No DEMA76.41 ±\pm 2.0379.20 ±\pm 1.13−1.51−0.89
No Mixed-Sampling77.50 ±\pm 2.3479.83 ±\pm 0.88−0.41−0.25

Each ablation changes only the indicated component: the exploration ablation retains source initialization and the UCB bonus; the EMA ablation uses a single EMA with the same discount; and the single-source variant preserves the sampling probabilities while removing mini-batch-level source mixing.

All three ablations reduce the minimum and average accuracies, where the isolated effects range from 0.41 to 1.51. We provide full details in Sec-4.3 and Appendix-D6.

Question: Lower Bound and Admissibility

The updated manuscript provides definition of admissibility explicitly in the remark after Theorem 6 (page 7, lines 330 - 334). Specifically, we consider instantaneous sampler-optimizer algorithms satisfying our feedback model:

  • The sampler observes feedback only from selected sources, without historical re-evaluation or auxiliary loss observations;
  • The optimizer follows the OGD update rule.

We also explicitly restrict the componentwise balance result to K≥2K\ge2. Indeed, when K=1K=1, the bandit component vanishes and the problem reduces to standard stochastic optimization.

Question: Additional Seeds and Source Diversity

The manuscript currently reports multi-seed DPO runs in Appendix-D2. DUCB improves minimum accuracy over Uniform in all three runs, with a paired gain of 2.57 ±\pm 1.04.

Existing experiments contain 2-4 explicitly defined sources across SFT, DPO, and GRPO. We agree that experiments with more numerous and heterogeneous source distribution would be valuable for the future work, noted in Sec-5.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.