💻 computer science

Deliberate Practice: Learning Robot Skills under a Budget

This paper introduces Deliberate Practice (DP), an active skill learning algorithm that uses a bilinear program to compute a provably budget-optimal allocation of practice time, enabling robots to autonomously acquire skills that maximize expected cumulative reward for long-horizon sequential tasks under limited resources.

Original authors: Shivam Vats, Sudarshan Harithas, Mete Tuluhan Akbulut, Arvind Raghunathan, George Konidaris

Published 2026-08-14

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Shivam Vats, Sudarshan Harithas, Mete Tuluhan Akbulut, Arvind Raghunathan, George Konidaris

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where robots aren't just pre-programmed to do one specific thing, but are curious learners capable of figuring out how to handle new objects and solve complex puzzles on their own. This is the frontier of robotics, a field where scientists are trying to teach machines to think and move like humans. However, there's a catch: robots are terrible at learning from scratch. They need to practice thousands of times to get good at a simple task, and in the real world, they don't have infinite time to mess around. They have a "budget"—a limited amount of downtime or practice time before they have to go back to work. The big question scientists are asking is: If a robot only has a short window to practice, how should it spend that time? Should it practice the easy things it's already okay at, or should it risk its limited time on a super-hard skill that could unlock a much bigger reward later? This paper tackles that exact dilemma, offering a new way for robots to be smart about how they learn.

The researchers behind this study, Shivam Vats and his team, propose a clever algorithm called Deliberate Practice (DP). Think of it as a robot coach that doesn't just tell the robot to "practice more," but tells it exactly what to practice to get the most out of its limited time. In the past, robots used to learn in a "greedy" way. Imagine a student cramming for a test who only reviews the easiest chapters because they know they can get an A on those quickly. They ignore the hard chapters that might be worth more points, simply because they look scary. This paper argues that this greedy approach is a mistake. Instead, Deliberate Practice acts like a strategic planner. It looks at the entire "menu" of possible tasks a robot might need to do, estimates how hard each one is to learn, and calculates the perfect mix of practice time to maximize the final score.

The core idea is that the amount of time a robot has to practice changes the strategy. If the robot only has a tiny budget (say, 30 practice sessions), the algorithm might decide it's safer to master one easy skill, like "toasting bread," which gives a small reward. But if the robot has a bigger budget (say, 60 sessions), the algorithm realizes it can afford to tackle a harder, multi-step challenge, like "microwaving oatmeal," which requires learning two difficult skills but pays out a much higher reward. The paper shows that by using a specific mathematical tool called a "bilinear program," the robot can solve this complex planning puzzle exactly, rather than just guessing.

In their experiments, the team tested this on simulated robots and a real Franka Panda robot. They set up scenarios like cleaning up a table or making breakfast. When the practice budget was low, the robot using Deliberate Practice correctly chose the easy path. When the budget was higher, it switched to the harder, high-reward path. In contrast, other methods that just picked the "easiest" skill to practice got stuck on low-reward tasks, even when they had plenty of time to learn something better. The paper proves that by thinking ahead and calculating the best use of time, robots can learn much more effectively, turning a limited practice session into a major upgrade in their abilities. It's a step toward robots that don't just work, but actually learn to work smarter.

Technical Summary: Deliberate Practice – Learning Robot Skills under a Budget

Problem Statement

The paper addresses the challenge of autonomously learning robot skills for sequential, long-horizon tasks under a limited practice budget (e.g., a fixed number of downtime episodes). While recent advances in large-scale robot learning and Task and Motion Planning (TAMP) enable robots to perform diverse skills, pretraining alone often fails to cover all real-world scenarios, leading to unreliable execution. Conversely, standard Reinforcement Learning (RL) is highly sample-inefficient, making deployment-time learning difficult when robots have only limited opportunities to practice.

The core problem is formalized as budgeted skill learning: given a library of high-level skill specifications (preconditions, effects, termination conditions), the robot must determine which skills to practice and how much time to allocate to each to maximize the expected cumulative reward of the resulting task plan. The challenge lies in the combinatorial nature of the problem: a robot must reason about multiple skill plans simultaneously, balancing the difficulty of learning specific skills against the potential reward of the task plans they unlock.

Methodology: Deliberate Practice (DP)

The authors propose Deliberate Practice (DP), an active learning algorithm that computes a provably budget-optimal allocation of practice time. The approach operates in three main stages:

1. Competence Prediction

DP models the improvement of a skill's competence (probability of success) as a function of the practice budget.

The model is initialized with a domain-specific prior and updated online based on observed improvements.
While the framework supports various models (linear, exponential), the authors empirically utilize a piece-wise linear model: $f_{improv}(u, b) = \min(1, p_u + \Delta_u b)$ , where $p_u$ is the initial competence and $\Delta_u$ is the rate of improvement.
More complex dynamics (e.g., deep RL) can be modeled using saturating exponential functions.

2. Budget Allocation (The Core Contribution)

The central technical contribution is the formulation of the budget allocation problem.

The Challenge: The problem is naturally a bilevel optimization: the outer level allocates the budget $b$ to skills, while the inner level solves the resulting Task MDP to determine the expected planning performance. Existing methods approximate this greedily (one-step lookahead), which is myopic and often suboptimal because it fails to recognize that practicing a sequence of difficult skills might yield a higher-reward plan than practicing a single easy skill.
The Solution: The authors derive an exact single-level reformulation of this bilevel problem. By utilizing the linear programming (LP) formulation of Markov Decision Processes (MDPs) and LP duality, they transform the problem into a structured single-level bilinear program.
- The objective maximizes the expected reward $\sum r_s^\mu \mu_s^\mu$ subject to constraints on state-action occupancy.
- Crucially, the practice budget constraints are directly incorporated into the dual LP formulation.
- The resulting problem is a nonsmooth, non-convex bilinear program.
Solving: The authors solve this using off-the-shelf solvers (e.g., Gurobi) employing spatial branch-and-bound methods and piecewise McCormick envelopes to handle the bilinear constraints and achieve global optimality (or bounded sub-optimality).

3. Skill Practice

Once the optimal budget allocation and task plan are computed, the robot executes a curriculum:

It sequentially masters the skills in the optimal plan.
It uses existing skills to reach the preconditions of the target skill, practices the target skill, and then uses the newly acquired skill to reach subsequent skills in the plan.

Key Contributions

Problem Formulation: The paper formalizes autonomous skill learning for sequential tasks under explicit budget constraints, highlighting the limitations of greedy, myopic active learning strategies.
Exact Optimization: The derivation of an exact single-level bilinear program reformulation for the budgeted skill learning problem. This eliminates the need for nested optimization or greedy approximations, allowing for provably optimal budget allocation using standard solvers.
Theoretical Guarantee: The authors prove that Deliberate Practice computes a globally optimal allocation of the practice budget (Theorem 1).
Empirical Validation: The method is validated in both simulated and real-world long-horizon manipulation tasks, demonstrating its ability to adapt learning behavior based on the available budget.

Experimental Results

The authors evaluated DP against several baselines: Estimate-Extrapolate-Situate (EES), Competence Improvement (CI), Least Competent First (LCF), and Random (R).

Budget Awareness: In the "Cleanup" task (simulated), DP successfully adapted its strategy to the budget size. With a low budget (100 episodes), it chose a conservative, low-reward plan. With medium (150) and high (250) budgets, it shifted to more complex, higher-reward plans that required practicing multiple difficult skills. Baselines failed to adapt, consistently choosing the easiest (lowest reward) plans regardless of budget.
Performance: DP significantly outperformed greedy baselines (EES, CI) in medium and high-budget settings. The greedy methods failed to discover high-reward plans that required multi-step practice, whereas DP's lookahead capability allowed it to identify these opportunities.
Scalability: In the "Cleanup-Multi" task (5,000 abstract states, 22 skills), DP computed optimal allocations within 6 minutes. Even when global optimality could not be proven within the time limit, the solver provided bounded-suboptimal solutions with optimality-gap certificates.
Real-World Validation: In a real-robot "Breakfast" task, DP correctly chose to learn only the "StartToaster" skill under a 30-episode budget (reward 1). Under a 60-episode budget, it correctly allocated time to learn both "OpenMicrowave" and "CloseMicrowave" skills to achieve the higher reward of 2.

Significance and Claims

The paper claims that Deliberate Practice is uniquely budget-aware, enabling robots to optimally utilize limited downtime to acquire useful policies.

Unlike prior active learning methods that focus on efficient acquisition of individual skills or rely on greedy heuristics, DP explicitly reasons about the sequential nature of long-horizon tasks and the combinatorial trade-offs of the practice budget.
The work provides the first exact formulation of robot learning on a budget as an optimization problem, moving beyond approximations to achieve provable optimality.
The results suggest that by leveraging known downtime constraints, robots can significantly improve their long-horizon planning performance and autonomy in deployment scenarios.

Limitations

The authors acknowledge two primary limitations:

Prior Dependence: The approach relies on approximate priors for skill competence. Overly optimistic priors could lead to infeasible allocations. Future work could address this via conservative priors or uncertainty incorporation.
Scalability of Optimization: While effective for the tested problems, solving the bilinear program to global optimality may become computationally challenging for extremely large problems. The authors suggest developing bounded-suboptimal strategies as a direction for future work.