{"id":"6b64d487-5d2a-4304-b29d-d6c6694f0e69","arxiv_id":"2608.13415","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Deliberate Practice allocates a limited robot practice budget across skills by solving an exact bilinear program, and beats greedy active-learning baselines in long-horizon manipulation tasks.","lead":"A new algorithm, Deliberate Practice, decides which robot skills to practice first when practice time is limited, by solving a mathematical program that trades off skill difficulty against the task reward the skills unlock. If the model is accurate, the allocation is provably optimal, and simulated and real-robot experiments show it outperforms greedy practice strategies.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The bilinear reformulation is exact, but budget-optimality is only relative to the unvalidated linear competence model; Section 8 admits optimistic priors can make the chosen plan infeasible, so the real-robot claim is not yet supported.","rationale":"The reader identified the same weakest assumption, and I agree with the conditional verdict. The central duality argument in A.2 is valid: replacing the inner MDP LP with its dual and maximizing jointly over b and mu is exact, and the missing explicit mu>=0 is implied by the equality constraints together with gamma<1 and stochastic transitions. The only real proof gap is Lemma 1's candidate for strict feasibility, which uses a constant that does not work for all gamma; it is easily repaired by taking a larger constant, so this is a minor typo, not a load-bearing flaw. The substantive issue is that Theorem 1's conclusion is stated unconditionally, while the objective is defined through f_improv. The experimental section does not validate f_improv against realized competence, does not report variance on the real-robot run, and Section 8 concedes that optimistic priors can break budget feasibility. This warrants a conditional acceptance rather than rejection: the reformulation is a genuine contribution, but the budget-optimality claim must be scoped to the fitted competence model and empirically calibrated. Therefore my read does not change the reader's verdict.","tokens_in":1032,"tokens_out":879,"duration_ms":163517,"concrete_test":"Run Cleanup-Multi at B=150 and B=250 with DP using the online piecewise-linear Delta_u estimates versus an oracle variant in which Delta_u is measured offline from CMA-ES learning curves in the same simulator; over at least 10 seeds, record realized task reward and the realized competence of each practiced skill after its allocated b_u episodes. If the oracle variant improves mean task reward by more than 10%, or if realized competence deviates from f_improv by more than 20%, the model premise underlying Theorem 1 is not met in practice.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The bilinear reformulation in Eq. (3) is a correct exact single-level rewrite of the model-level bilevel problem, so the mathematical core is not the issue. The load-bearing assumption is Eq. (2): f_improv(u,b)=min(1,p_u+Delta_u b) is treated as a deterministic, accurate description of how competence grows with practice episodes. The optimization in Eq. (3) and Theorem 1 then report global optimality only with respect to this predicted transition function. In deployment, practice budgets are integer episodes, CMA-ES updates are stochastic and use small batches (N=6 per iteration in A.3), and Delta_u is estimated online from a running average of competence differences; none of this is reflected in the theorem. If the true learning curve is nonlinear, saturating, or the prior is optimistic, the computed allocation can be infeasible or suboptimal. The paper's own Section 8 states that optimistic priors may make the chosen plan infeasible within the budget, and the real-robot results in Fig. 6 have no error bars or calibration check of f_improv against realized competence. Thus 'provably budget-optimal' is a theorem about the fitted model, not about the robot; that gap is the central load-bearing concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the problem of allocating a limited practice budget across a library of robot skills in a sequential task-and-motion-planning setting. It formulates budgeted skill learning as a bilevel optimization problem (Eq. 1) whose inner level solves the task MDP induced by the budget-dependent competence model, and whose outer level chooses a budget allocation. The main contribution is Deliberate Practice (DP), which models competence improvement with a piecewise-linear function (Eq. 2), derives an exact single-level bilinear reformulation of the bilevel problem via LP duality (Eq. 3 and Appendix A.2), and solves it with off-the-shelf global solvers. The authors claim that DP is provably budget-optimal (Theorem 1) and validate it in two simulated manipulation domains and one real-robot breakfast-making task.","tokens_in":11911,"tokens_out":8882,"duration_ms":95665,"significance":"The idea of coupling a practice budget to long-horizon task planning is timely and practically motivated, and the LP-duality reformulation is an interesting technical contribution that goes beyond greedy active-learning baselines. If the reformulation and its optimality proof are correct, the paper offers a principled way to make budget-aware decisions in robot skill learning, with experiments spanning nontrivial state spaces (up to 5000 abstract states and 22 skills) and a real robot. The paper also gives a clear, reproducible problem statement and an explicit comparison to myopic baselines. However, the optimality claim is conditional on the competence model and the proof contains fixable but nontrivial gaps; the empirical evidence does not yet establish that the computed allocations are optimal or even feasible for the real robot.","major_comments":[{"comment":"The displayed bilinear program omits the nonnegativity constraint on the dual variables mu_s^a. In the standard dual LP of an MDP these variables are state-action occupancies and must satisfy mu_s^a >= 0. Without this constraint, the feasible set allows negative values for individual actions as long as the sum over actions satisfies the flow equality. Because the objective is linear in mu, a solver could shift occupancy from a low-reward action to a higher-reward action with identical transition probabilities, improving the objective while violating the intended MDP interpretation. The claim that Eq. (3) is an exact reformulation of Eq. (1) therefore is not supported as written. The fix is straightforward -- add mu_s^a >= 0 -- but the theorem and proof must be updated to state and use this constraint.","section":"Appendix A.2, Eq. (7) and Section 5.2, Eq. (3)"},{"comment":"The proof of Slater's condition is incorrect: the proposed candidate hat v_s = alpha/gamma^2 does not strictly satisfy the constraints for discount factors with gamma > 0.618. For example, with gamma = 0.9 the left-hand side alpha/0.81 is smaller than the maximum right-hand side alpha + alpha/0.9 = alpha(1 + 1/gamma). A correct choice would be hat v_s = C with C > alpha/(1-gamma), which yields strict satisfaction. Since the LP is feasible and bounded for discounted MDPs, strong duality can be established by standard LP arguments, but the lemma as stated is mathematically wrong and must be corrected.","section":"Appendix A.2, Lemma 1"},{"comment":"The budget B is defined as a number of trials or episodes, but the optimization in Eq. (3) treats the allocation b as a continuous variable with no integrality constraint and no rounding analysis. The competence model f_improv(u,b) is evaluated at real-valued b, while practice episodes are indivisible. The proof of global optimality in Theorem 1 is therefore over the continuous relaxation, not over integer allocations. The paper does not show that the continuous optimum can be rounded to an integer allocation without losing optimality or feasibility. This is a load-bearing gap between the mathematical claim and the actual robot-setting where budgets are integer episode counts.","section":"Section 4 and Section 5.1, Eq. (2)"},{"comment":"Theorem 1 certifies optimality only with respect to the competence prediction model of Eq. (2), not with respect to the robot's realized competence. The paper's own Section 8 states that optimistic priors can make the chosen plan infeasible within the budget, which means the 'provably budget-optimal' claim is conditional on an unvalidated model. The real-robot results in Fig. 6 are reported without error bars, without repeated trials, and without any calibration check comparing predicted competence f_improv to the competence actually achieved after practice. The abstract's wording that DP 'maximizes expected cumulative reward while being learnable within the budget' overstates what is established. The claims should be qualified to optimality under the assumed competence model, and the empirical section should include calibration evidence or a sensitivity analysis over priors.","section":"Section 8 and Section 6.1 (Fig. 6)"}],"minor_comments":[{"comment":"The text uses 'Auroco Markers' and 'Auroco Detection'; the correct spelling is ArUco.","section":"Appendix A.5"},{"comment":"The online estimation of Delta_u is not fully specified: the update uses p_t values, but it is not stated how p_t is estimated from the outcome of a single practice episode or how many episodes are used. A binary success/failure per episode makes a running average of differences very noisy; please specify the estimation window and any smoothing used in the experiments.","section":"Section 5.1"},{"comment":"The real-robot figure lacks information about the number of independent runs and does not show variability. Reporting mean plus standard deviation or individual trial outcomes would strengthen the claim that DP reliably selects the correct plan under each budget.","section":"Section 6.1, Fig. 6"},{"comment":"The transition-probability indexing is inconsistent between the general notation P^a_{s's} in Eq. (7) and the earlier use of \\bar P^a_{s's}(b) in Eq. (3); the reader must infer which index is the source state. Please unify the notation.","section":"Appendix A.2, Eq. (6) and Eq. (7)"},{"comment":"The sentence claiming 'to our knowledge, this is the first exact formulation of robot learning on a budget as an optimization problem' is an overclaim and difficult to verify; tempering it to 'to our knowledge, the first exact single-level formulation of this budgeted skill-learning problem' would be more defensible.","section":"Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the central idea is promising and the LP-duality reformulation is potentially a strong contribution, but the proof has fixable gaps (missing nonnegativity constraint on mu, incorrect Slater bound) and the optimality claim is conditional on an unvalidated competence model. The paper needs a careful revision of the optimization formulation and a more cautious presentation of the real-robot claims before it can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core result is real. The paper replaces the bilevel budget-allocation/task-MDP problem with an exact single-level bilinear program using LP duality, and that reformulation is the actual contribution. It avoids the greedy myopia of EES and similar methods, and the math in the appendix checks out. The main caveat, which the authors themselves admit, is that provable optimality is relative to the competence model in Eq. (2), not to the real robot.\n\nWhat is new and what works: the formulation in Eq. (3) is a clean way to fold practice-budget constraints into the MDP dual LP. The Figure 2 example shows a concrete case where greedy one-step selection fails and a lookahead allocation succeeds. The derivation in A.2 is sound: Slater's condition is proved, strong duality holds, and the joint max over b and mu is legitimate. Simulated Cleanup results have means and standard deviations over five seeds and show the expected qualitative pattern: DP shifts to higher-reward plans as the budget grows, while baselines get stuck. The real-robot breakfast demo is a nice qualitative demonstration of budget-awareness, though not more than that.\n\nSoft spots, roughly in order of importance. First, the load-bearing assumption is f_improv(u,b)=min(1,p_u+Delta_u b). Delta_u is estimated online as a running average, but there is no calibration check of the linear improvement model against realized competence in either simulation or real hardware. If the true learning curve is nonlinear or saturating, the computed allocation is optimal for the wrong model. The authors mention exponential alternatives but do not validate them. Second, the budget is defined in episodes while b is continuous in the optimization. With B=30 that is not a purely cosmetic issue; rounding a continuous allocation can matter in small-budget regimes. I suspect it is benign in their demonstrations, but it deserves a sentence or a constraint. Third, Theorem 1 asserts global optimality of the bilinear program, but the appendix proves the reformulation, not the convergence of spatial branch-and-bound. The paper does acknowledge early termination gives bounded suboptimality, so this is more a presentation gap than a mathematical error. Fourth, the real-robot results have no error bars and no sensitivity analysis over the prior competence estimates, so they should be treated as qualitative.\n\nWho is this for? Researchers working on active skill learning, TAMP with skill libraries, and deployment-time robot learning. It deserves a serious referee. I would ask for code release and either a calibration experiment for Eq. (2) or a sensitivity analysis over Delta_u before accepting, but the central idea is solid and should not be desk-rejected.","headline":"A genuinely new exact reformulation of budgeted skill practice, with a sound derivation and a caveat that 'budget-optimal' is only as good as the fitted competence model.","tokens_in":12441,"tokens_out":2163,"would_cite":true,"duration_ms":26427,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a robot can spend a fixed practice budget across its skills in a globally optimal way, by solving one bilinear program that jointly picks the budget allocation and the task plan.","keywords":["budgeted skill learning","active learning","task and motion planning","bilevel optimization","bilinear program","robot skills","practice budget","long-horizon manipulation"],"falsifier":"Run DP on a small MDP such as the five-state example in Section 4.1, enumerate every feasible allocation of a 20-episode budget by brute force, and solve each resulting MDP exactly; if any enumerated allocation achieves higher expected reward than DP's chosen allocation, Theorem 1 is false. On a real robot, give two robots the same budget but deliberately different competence priors: the one with optimistic priors should, per the paper's own limitation, sometimes pick a plan it cannot finish within the budget, showing that budget-optimality holds for predicted rather than realized improvement.","tokens_in":11471,"feed_emoji":"🤖","tokens_out":5455,"duration_ms":55797,"temperature":0.7,"pith_summary":"Robots refining skills during deployment often have only a limited number of practice episodes. This paper introduces Deliberate Practice (DP), an algorithm that decides in advance how many episodes to spend on each skill in a library so that the expected reward from the best reachable task plan is maximized. The central result is Theorem 1: the bilevel problem of choosing a budget allocation while solving the resulting task MDP is exactly equivalent to one flat bilinear program, which off-the-shelf global solvers can optimize. If the competence-improvement model is right, the resulting practice plan is globally optimal for the budget. Experiments in simulated and real long-horizon manipulation show DP switching from an easy low-reward plan under a small budget to a harder high-reward plan under a larger one, whereas greedy baselines stay stuck.","feed_headline":"One bilinear program makes practice budgets provably optimal","feed_subtitle":"Deliberate Practice tells a robot which skills to train so its expected reward is maximized within limited practice time.","key_machinery":"The load-bearing object is the bilinear program of Eq. (3), which jointly optimizes the practice allocation $b_u$ and dual state-action occupancy variables $\\mu_s^a$, with skill transition probabilities $\\bar P^a_{s's}(b) = f_{\\text{improv}}(P^a_{s's}, b)$ entering bilinearly into the occupancy constraints. The competence prediction model $f_{\\text{improv}}(u,b) = \\min(1, p_u + \\Delta_u b)$ is the mechanism that maps practice episodes into improved transitions, with $\\Delta_u$ estimated online from observed improvement. The bilinear terms are relaxed by piecewise McCormick envelopes, and the resulting nonconvex program is solved to global optimality by spatial branch-and-bound, using finite bounds on $\\mu$ and the transition probabilities to certify the result.","core_discovery":"The paper's central claim is that budgeted skill learning—maximize expected task value over a library of skills with a total practice budget—can be solved to global optimality by a single bilinear program (Eq. 3), rather than approximated by greedy one-step improvement. The move is to replace the inner MDP solve with its dual linear program, then fold the budget constraint into the dual feasibility equations, because the leader and follower optimize the same objective. Strong duality turns the bilevel max-min problem into a joint maximization over the allocation $b$ and the state-action occupancy variables $\\mu$. The paper proves the reformulation is exact, gives finite bounds on the occupancy and transition variables so that piecewise McCormick envelopes produce valid convex relaxations, and invokes spatial branch-and-bound for global certification. The corollary, stated as Theorem 1, is that the returned allocation is budget-optimal: it maximizes expected cumulative reward among all allocations feasible within the budget, for the predicted competence dynamics.","pith_inferences":["The duality reformulation is not tied to the particular linear competence model: any competence predictor that enters the transition probabilities as a function of $b$ and yields finite bounds could be placed in the same program, so the machinery may extend to saturating or learned improvement curves with the same global-optimality framework.","Because Theorem 1 holds for the predicted competence model, a natural stress test is to compare DP's allocation under optimistically biased priors against a robust or uncertainty-aware allocation; the paper itself flags optimistic priors as the key failure mode.","The same 'replace the follower with its dual' move applies to any bilevel resource-allocation problem whose inner problem is a linear program with an aligned objective, so budget-optimal skill learning may transfer to settings such as allocating teaching time among sub-skills or tuning a fleet of policies."],"forward_implications":["A robot with a known downtime window can compute, before practicing, exactly which skills to train and for how long, instead of adapting greedily after each episode.","Under small budgets the optimal behavior is conservative—practice only the easy, low-reward plan—while under larger budgets the same procedure shifts to hard high-reward plans that require multiple skills, as demonstrated in simulation and on a real robot.","Greedy active-learning baselines plateau at local optima because one-step task improvement is zero for skills that only pay off when practiced together; DP's joint lookahead avoids that failure.","The bilinear program scales to task MDPs with about 5,000 abstract states and 22 skills, solving within minutes; if interrupted before proving optimality, the solver still returns an allocation with an optimality-gap certificate."],"supporting_citations":[{"why":"Supplies the dual LP of an MDP used to replace the inner optimization in the bilevel problem.","marker":"[30]"},{"why":"Provides the off-the-shelf solver that handles bilinear constraints through convex relaxations.","marker":"[31]"},{"why":"Provides the spatial branch-and-bound machinery used to certify global optimality of the bilinear program.","marker":"[32]"},{"why":"Gives McCormick envelopes, the convexification technique used to relax the bilinear terms.","marker":"[39]"},{"why":"The greedy 'practice makes perfect' baseline that DP is contrasted against and that is shown to be myopic.","marker":"[28]"}],"fun_headline_variants":["Bilinear program yields budget-optimal robot practice","Provably optimal practice: one bilinear program","Exact skill practice allocation under budget","Maximize expected reward with budget-optimal training"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole plan is only as good as the robot's guess of how much each skill will improve per practice episode; if that guess is wrong, the 'optimal' allocation is optimal only inside the model.","fun_headline_variants_meta":{"raw":{"variants":["Bilinear program yields budget-optimal robot practice","Provably optimal practice: one bilinear program","Exact skill practice allocation under budget","Maximize expected reward with budget-optimal training"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000241,"raw_usage":{"total_tokens":1493,"prompt_tokens":887,"completion_tokens":606,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":503,"completion_tokens_details":{"reasoning_tokens":549}},"tokens_in":503,"tokens_out":606,"duration_ms":6918,"temperature":1.0,"reasoning_tokens":549,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:27:17.688610+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DP on a small MDP such as the five-state example in Section 4.1, enumerate every feasible allocation of a 20-episode budget by brute force, and solve each resulting MDP exactly; if any enumerated allocation achieves higher expected reward than DP's chosen allocation, Theorem 1 is false. On a real robot, give two robots the same budget but deliberately different competence priors: the one with optimistic priors should, per the paper's own limitation, sometimes pick a plan it cannot finish within the budget, showing that budget-optimality holds for predicted rather than realized improvement.","supporting_citations":[{"cited_title":"Gurobi Optimizer Reference Manual, 2024","cited_arxiv_id":null,"evidence_quote":"Provides the off-the-shelf solver that handles bilinear constraints through convex relaxations."},{"cited_title":"Tawarmalani and N","cited_arxiv_id":null,"evidence_quote":"Provides the spatial branch-and-bound machinery used to certify global optimality of the bilinear program."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives McCormick envelopes, the convexification technique used to relax the bilinear terms."}],"review_version":1}