Paper deep dive
Deliberate Practice: Learning Robot Skills under a Budget
Shivam Vats, Sudarshan Harithas, Mete Tuluhan Akbulut, Arvind Raghunathan, George Konidaris
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/16/2026, 2:24:36 AM
Summary
The paper introduces Deliberate Practice (DP), an active skill learning algorithm for robots that computes a provably budget-optimal allocation of practice time to maximize expected cumulative reward in sequential tasks. Unlike greedy methods, DP uses a bilinear program derived from MDP duality to jointly reason about skill competence and task planning under strict time budgets, demonstrated in simulated and real-world manipulation tasks.
Entities (10)
Relation Signals (8)
Deliberate Practice → uses → Bilinear Program
confidence 95% · Our key contribution is a bilinear program that can compute this exactly using off-the-shelf solvers.
Deliberate Practice → solves → Budgeted Skill Learning
confidence 93% · We formalize the problem of autonomous skill practice for sequential tasks as budgeted skill learning, and propose an active learning algorithm, Deliberate Practice (DP)
Deliberate Practice → appliedto → Cleanup
confidence 92% · 1. Cleanup (simulated)... We evaluate our method in three long-horizon table-top manipulation tasks.
Deliberate Practice → appliedto → Breakfast
confidence 92% · 3. Breakfast (real-robot)... We evaluate our method in three long-horizon table-top manipulation tasks.
Deliberate Practice → outperforms → Greedy Active Learning
confidence 90% · DP significantly outperforms prior active learning methods... The greedy active learning baselines... fail to discover higher-reward plans
Breakfast → requiresrobot → Franka Panda
confidence 90% · A Franka Panda robot can toast bread or make hot oatmeal
Deliberate Practice → usessolver → Gurobi
confidence 88% · supported by popular solvers, such as Gurobi
Deliberate Practice → usesoptimizer → CMA-ES
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We consider the problem of autonomously learning robot skills under a limited practice budget for sequential tasks. We propose an active skill learning algorithm, \emph{Deliberate Practice (DP)}, that computes a provably \emph{budget-optimal} allocation---practicing skills that maximize expected cumulative reward while being learnable within the budget. DP estimates both the time needed to master skills and the cumulative reward of the task plans that the skills unlock. Computing a budget-optimal allocation is challenging as it requires reasoning about combinatorially many skill plans over a large practice budget. Our key contribution is a bilinear program that can compute this exactly using off-the-shelf solvers. Through simulated and real-world experiments on long-horizon manipulation tasks, we show that our approach allows robots to optimally use limited practice time to acquire useful policies and improve long-horizon planning.
Tags
Links
- Source: https://arxiv.org/abs/2608.13415v1
- Canonical: https://arxiv.org/abs/2608.13415v1
Trouble viewing inline? Open PDF directly →
Full Text
45,105 characters extracted from source content.
Expand or collapse full text
Deliberate Practice: Learning Robot Skills under a Budget Shivam Vats 1 Sudarshan Harithas 1 Mete Tuluhan Akbulut 1 Arvind Raghunathan 2 George Konidaris 1 1 Brown University 2 Mitsubishi Electric Research Laboratories Correspondence to shivam vats@brown.edu Abstract: We consider the problem of autonomously learning robot skills under a limited practice budget for sequential tasks. We propose an active skill learn- ing algorithm, Deliberate Practice (DP), that computes a provably budget-optimal allocation—practicing skills that maximize expected cumulative reward while be- ing learnable within the budget. DP estimates both the time needed to master skills and the cumulative reward of the task plans that the skills unlock. Com- puting a budget-optimal allocation is challenging as it requires reasoning about combinatorially many skill plans over a large practice budget. Our key con- tribution is a bilinear program that can compute this exactly using off-the-shelf solvers. Through simulated and real-world experiments on long-horizon manip- ulation tasks, we show that our approach allows robots to optimally use limited practice time to acquire useful policies and improve long-horizon planning. Keywords: Task and Motion Planning, Active Learning, Robot Skills 1 Introduction Recent progress in large-scale robot learning has produced general-purpose robot policies that can perform diverse skills and transfer to novel environments [1, 2, 3]. When combined with classical planning methods, such as Task and Motion Planning (TAMP) [4, 5, 6] and search [7, 8], these policies can allow robots to perform long-horizon tasks in homes and factories, charting a path for more autonomous robots. However, pretraining alone does not cover all the possible scenarios a robot may face in the real-world, often leading to unreliable task execution. Therefore, a promising solution is to allow robots to learn from experience through autonomous practice [9, 10, 11]. Unfor- tunately, current RL algorithms remain highly sample inefficient [12, 13], limiting their applicability to deployment-time learning. Since robots typically have only limited downtime during deployment, they require methods explicitly designed for budgeted practice. Our key insight is that downtime is often known in advance, and robots should leverage this infor- mation to adapt their learning process to the resulting practice budget. Intuitively, a large practice budget should encourage robots to practice more rewarding skills even if they are hard, while a small budget should lead to conservative learning behaviour. We formalize the problem of autonomous skill practice for sequential tasks as budgeted skill learning, and propose an active learning algo- rithm, Deliberate Practice (DP), that optimally uses the budget to maximize task reward. We con- sider the standard TAMP setting in which a robot is given high-level skill specifications, including preconditions, termination conditions, and effects. For example, in the breakfast domain in Sec- tion 6, the StartToaster skill requires moving above the toaster lever to press it and has the effect of turning on the toaster. The robot must learn parameterized control policies that ground skills into low-level actions through practice in the environment. At decision time, a task plan- ner computes a plan consisting of skills, e.g., (Pick(bread), Place(bread, toaster), Start(toaster)) to toast bread. Figure 1 illustrates how our approach allows the robot to de- cide which skills to practice to make breakfast. The robot can either practice one skill to toast bread arXiv:2608.13415v1 [cs.RO] 13 Aug 2026 Figure 1: Deliberate Practice allows robots to intelligently use a limited practice budget to actively learn skills to maximize long-horizon task reward. (top) Under a small budget, the robot practices an easy task plan that toasts bread and provides reward 1. (bottom) Under a larger budget, it practices a more difficult but higher-reward task plan that microwaves oatmeal and provides reward 2. or use additional practice time to learn two skills required to microwave oatmeal and achieve a higher reward. As shown in Section 6, with a budget of 30 episodes, DP correctly estimates that only one skill can be learned reliably and hence practices to toast bread. Under a budget of 60 episodes, it instead practices to microwave oatmeal to take advantage of the additional practice time. Deliberate Practice first estimates the difficulty of learning each skill as a function of the practice budget. It then computes a budget allocation that provably maximizes expected planning perfor- mance, and practices its skills accordingly. We show in Section 4 that computing an optimal allo- cation requires solving a challenging bilevel optimization problem. Existing active learning algo- rithms approximate this problem greedily, leading to myopic and suboptimal learning (Section 4.1). By contrast, we derive an exact single-level reformulation of the bilevel problem using the linear programming (LP) formulation of Markov decision processes. This allows us to compute the opti- mal budget allocation using off-the-shelf solvers. Through experiments in simulated and real-world long-horizon manipulation tasks, we demonstrate that Deliberate Practice is uniquely budget-aware and enables robots to learn effectively under deployment constraints. 2 Related Work Active Skill Learning. Deliberate practice is a widely studied mechanism underlying expert human performance [14], characterized by structured, goal-directed training that allocates effort toward the most limiting components of a skill. In robotics, active learning has similarly been central for skill acquisition due to the high cost of data collection. Prior work includes methods for actively learn- ing parameterized robot skills from practice [15], human demonstrations [16], and across multiple tasks [17, 18, 19]. However, these approaches focus on efficiently acquiring individual skills without considering the sequential nature of long-horizon problems. By contrast, our approach studies active skill learning embedded in a complex sequential decision process under explicit budget constraints. Task and Motion Planning (TAMP). TAMP [4, 20, 5] addresses robotic planning problems that require joint reasoning over discrete task structure and continuous motion feasibility. Most TAMP systems adopt a hierarchical approach, where a high-level planner [21, 22] solves an abstract version of the problem to compute a task plan, which is then grounded into low-level robot actions using motion planning and control [23]. Recent TAMP approaches leverage machine learning to improve scalability and performance, for example, by learning heuristics to guide symbolic search [24], 2 or by learning symbolic operators and task representations [25, 26]. Our work is closely related to approaches that plan to practice skills for autonomous improvement in long-horizon tasks [27, 28]. However, these methods rely on greedy practice strategies and often allocate practice time suboptimally. By contrast, our method computes a budget-optimal allocation of practice time. 3 Background We model the environment as a Markov decision process (MDP) with continuous state and action spaces, defined by the tupleM := (S,A,P,r,γ), whereS is the low-level state space,A is the low- level robot action space, P (s ′ |s,a) is the transition function, r(s,a) is the reward function, γ is the discount factor. We assume an abstract MDPM h := (S h ,A h ,P h ,r h ,γ), where a state abstraction function typically α :S →S h projects raw sensory observations to abstract states. Abstract Dynamics. We assume that the robot is provided with a library of skillsU , which are de- fined using an extension of the options framework, consisting of the following components: a) Pre- condition (PRE) defines the states in which a skill can be initiated, b) Effect (EFF) describes the out- come of executing a skill successfully, c) Control policy (π) computes the low-level actions to be ex- ecuted by the robot, d) Termination condition (β) specifies when a skill should terminate, e) Compe- tence (p) is the probability that the skill will successfully achieve the desired effect. The abstract ac- tion spaceA h is defined by skill libraryU that the robot can use to transition between abstract states. Skill effect and competence together define the high-level transition function P h : P h (s ′ |s,a) = p, if s ′ corresponds to the effect of skill u ∈ U when executed in state s, otherwise transitioning to an absorbing failure state. We use a task planner to solve this abstract MDP M h to compute a sequence of skills with the correct parameters to reach the goal, e.g., (Open(top-drawer), Pick(toy), Place(toy, top-drawer)). The skills then ground this abstract task plan by computing feasible robot trajectories. Structured Robot Skill. We use a combination of motion planning and parameterized policies to handle contact-rich interactions with the environment. We structure every contact-rich policy as an object-centric Composable Interaction Primitive (CIP) [29], which consists of three phases: a) Pre- interaction: motion plan to a pose near the object, b) Interaction: execute a parameterized policy, and c) Post-interaction: motion plan away from the object. The interaction policy is learned by the robot by practicing in the environment. Task and Skill Reward. The robot is tasked with maximizing a task reward function R with one or more absorbing goal states, defined by a goal function g :S →0, 1. We also define skill-specific reward functions to learn the policy parameters through practice. 4 Budgeted Skill Learning for Planning Given the high-level descriptions of a library of skills U , consisting of their preconditions, termi- nation conditions, and effects, the robot must learn the policy parameters of its skills to improve overall planning performance under a limited practice budget B, e.g., maximum number of trials. We adopt the standard episodic reinforcement learning setting without access to expert demonstra- tions. Our goal is to compute a budget allocation b u across all skills U to maximize the expected planning performance. Formally, this can be expressed as the following optimization problem: max b X s∈S e s v s subject to X u∈U b u ≤ B, v s ∈ SolveMDP(M h ,b), (1) 3 where e s is the initial state distribution, and v s is the state value function. This is a bilevel optimiza- tion problem where the outer problem computes a budget allocation b for practicing policies, and the inner problem solves the resulting task MDP M h to compute the expected planning performance after practicing with budget allocation b. 4.1 Greedy Active Learning Converges to Local Minima Figure 2: An example illustrat- ing how greedy active learning can make suboptimal decisions. Prior active skill learning methods [27, 28] for sequential tasks greedily practice the skill that will most improve the expected task performance J task after one round of training. These meth- ods can be viewed as performing one-step reasoning to solve equation 1. However, this is inherently myopic: it can over- look higher-performing task plans that require deliberate prac- tice over multiple episodes to be mastered. We provide an il- lustrative example in Figure 2. This MDP consists of 5 states: A, B, C, D and a terminal failure state. The robot always starts at A, while B and D are terminal goal states. The MDP can be solved either by using π 1 to reach B or by using π 2 and π 3 to reach D. All skills have identical competence p = 0.1; they transition to the failure state with probability 0.9. The robot must decide which skills to practice among π 1 ,π 2 ,π 3 under a budget of 20 episodes given each skill has the same rate of improvement ∆p i = 0.1 per practice episode. The optimal policy for the MDP before practice is to use π 1 to reach B. Hence, J task = p 1 × R B = 0.1. Let π ′ i be the skill after a round of practice. The greedy task improvement measure of each skill is computed below: Practice π 1 =⇒ J task (π ′ 1 ,π 2 ,π 3 ) = (p 1 + ∆p 1 )× R B = 0.2× 1 = 0.2 Practice π 2 =⇒ J task (π 1 ,π ′ 2 ,π 3 ) = (p 2 + ∆p 2 )× p 3 × R D = 0.2× 0.1× 4 = 0.08 Practice π 3 =⇒ J task (π 1 ,π 2 ,π ′ 3 ) = p 2 × (p 3 + ∆p 3 )× R D = 0.1× 0.2× 4 = 0.08. Therefore, greedy methods practice only π 1 since it always maximizes one-step J task improvement resulting in the final reward 1. However, this misses the optimal solutionπ 2 ,π 3 which will provide reward 4 under 20 rounds of practice, because identifying the optimal budget allocation requires reasoning about deliberate practice across π 2 and π 3 over multiple rounds. 5 Deliberate Practice Our algorithm allocates the practice budget provably optimally by jointly reasoning about all robot skills across the entire practice budget. As shown in Figure 3, our approach comprises three steps: 1. Competence Prediction. Competence improvement is modeled as a function of the prac- tice budget. This model is initialized with a domain-specific prior and updated online based on the robot’s actual improvement. 2. Budget Allocation. A budget-optimal task plan Π ∗ is computed along with the correspond- ing budget allocation b ∗ needed to master it. 3. Skill Practice. The robot sequentially masters the skills that are reachable from the start and then uses them to plan to reach and practice downstream skills. 5.1 Competence Prediction The competence prediction function f improv (p u ,b u ) predicts the expected skill competence after practicing a skill with a competence of p u for b u rounds. While our approach supports linear, piece-wise linear and exponential models of competence prediction, empirically a piece-wise linear 4 Figure 3: Overview: Our approach predicts skill competence as a function of practice budget, computes a budget allocation for practice, and practices skills by interacting with the environment. model provides a good balance between performance and efficiency. f improv (u,b) = min(1,p u + ∆ u b),(2) where ∆ u is the rate of improvement of a skill u estimated from practice. ∆ u is estimated online as a running average of competence improvement observed after practicing skill u over time: ∆ t u = ε∆ t−1 u + (1− ε)(p t u − p t−1 u ), where ε ∈ [0, 1] is a smoothing factor. To capture highly non-linear dynamics (such as deep reinforcement learning), our approach also supports more complex models, such as the saturating exponential: f improv (u,b) = p u + (1−p u )(1−e −αb ), where α is the learning rate that is estimated online. 5.2 Budget Allocation Next, we use the competence prediction model to compute the best task plan feasible within the practice budget. Long-horizon manipulation tasks require deliberately practicing multiple skills over many episodes to be reliably solved. As the bilevel optimization problem (Equation 1) shows, this requires jointly reasoning about all skills and the entire practice budget. However, this opti- mization is notoriously difficult due to its nested structure: the feasible set of the outer problem is defined implicitly by the solution of the inner optimization. This coupling leads to highly noncon- vex and often non-smooth objectives, even when both levels are individually convex. We derive an exact single-level reformulation using duality, yielding a structured single-level bilinear program that enables efficient optimization using standard nonlinear programming solvers, eliminating the need for nested optimization, and greedy approximations. To our knowledge, this is the first exact formulation of robot learning on a budget as an optimization problem. We first state the bilinear program and then outline the derivation. The lines in black in equation 3 correspond to the standard dual linear program of an MDP [30], and our proposed changes are high- lighted in blue. μ a s are dual variables that correspond to state-action occupancy, e s is the initial state distribution, P a s ′ s is the current transition function, and ̄ P a s ′ s (b) is the predicted transition function after practicing with budget allocation b. Surprisingly, we show that practice budget constraints can 5 be directly incorporated into the standard dual linear program. max b,μ X ∀s∈S X ∀a∈A r a s μ a s subject to X ∀a∈A μ a s − γ X s ′ X ∀a ̄ P a s ′ s (b)μ a s ′ = e s ,∀s ̄ P a s ′ s (b) = f improv (P a s ′ s ,b) X b ij ≤ B μ a s ≤ 1 1− γ ,∀s,a. (3) This is a nonsmooth bilinear mathematical program because of the piece-wise linear model in equa- tion 2 and bilinear terms ̄ P a s ′ s (b)μ a s ′ in the constraints. While being a nonsmooth, nonconvex nonlin- ear problem, there exist powerful techniques to solve it to global optimality. In particular, piecewise McCormick envelopes can be used to develop convex relaxations of the bilinear constraints and are supported by popular solvers, such as Gurobi [31]. Theorem 1. Deliberate Practice is budget-optimal, i.e, it computes a globally optimal allocation of the practice budget. Proof. First, we show that the bilinear program in Equation 3 is an exact reformulation of the bilevel program in Equation 1. Our key idea is to replace the inner optimization with its linear program- ming formulation. This allows us to convert the bilevel problem into a max min problem. Then, we utilize LP duality to reformulate it as a single-level max problem with bilinear constraints. We solve equation 3 to global optimality using spatial branch and bound methods [32], which han- dle bilinear constraints via convex relaxation techniques, such as Piecewise McCormick Envelopes. Constructing these relaxations requires valid finite bounds on all the variables appearing in the bi- linear constraints. We derive tight lower and upper bounds for all variables μ and P appearing in bilinear constraints, enabling the certification of global optimality. In particular, P a s ′ ≤ 1 since it corresponds to transition probability, and μ a s ≤ 1 1−γ since it is the discounted state-action occupancy measure. A detailed proof is in Appendix A.2. 5.3 Skill Practice Once the robot computes a budget allocation and a corresponding budget-optimal task plan, it con- structs a curriculum to practice the selected skills. This requires the robot to plan with its existing skills to first reach the precondition of the skill being practiced [28]. Specifically, the robot sequen- tially masters each of the skills on the budget-optimal plan computed by Deliberate Practice and uses each newly acquired skill to reach and practice subsequent skills. 6 Experimental Evaluation We evaluate our method in three long-horizon table-top manipulation tasks. Our simulated environ- ments are implemented in MuJoCo [33] using LIBERO [34]: 1. Cleanup (simulated). A Franka Panda robot must clear a table by placing an object into one of three drawers. The task MDP has 47 abstract states and 10 skills in total, with the longest task plan consisting of 4 skills. The robot is provided abstract specifications of Pick, Place, OpenDrawer, and CloseDrawer skills. 2. Cleanup-Multi (simulated). This is a challenging multi-object version of the Cleanup task in which four objects must be placed into a drawer. The task MDP has 5000 abstract states and 22 skills in total, with the longest task plan consisting of 10 skills. 6 Figure 4: (a) Breakfast task requires learning forceful manipulation skills to interact with novel articulated objects. (b) Cleanup task requires the robot to place objects in the top, middle, or bottom drawer with rewards 1, 2 and 4 respectively. 3. Breakfast (real-robot). A Franka Panda robot can toast bread or make hot oatmeal using a microwave to achieve a higher reward. The former requires learning a StartToaster skill, while the latter requires learning OpenMicrowave and CloseMicrowave skills, and hence is harder. These skills require forceful interaction with novel articulated objects and hence must be learned by practicing. The robot has additional pick and place skills for transporting objects using motion planning that need not be learned. Baselines. We compare Deliberate Practice (DP) against the following baselines: (1) Estimate, Extrapolate, Situate (EES) estimates the expected improvement of each skill and greedily practices the skill that most improves task performance [28]. (2) Competence Improvement (CI) practices the skill with the highest expected competence improvement [35, 36]. (3) Least Competent First (LCF) practices the skill with the lowest estimated competence. (4) Random (R) randomly samples a reachable skill for practice. Implementation details are provided in the Appendix. Skill Practice. We implement all learnable skills as Cartesian-space impedance controllers [37] parameterized by waypoints and impedance parameters. For each skill, we define a reward function and optimize the corresponding interaction policy parameters using CMA-ES [38]. We use CMA-ES because our objective is evaluated through rollouts and is not differentiable with respect to the policy parameters. CMA-ES is a robust gradient-free optimizer for such continuous black-box objectives. 6.1 Experimental Results DP is budget-aware. Figure 4 shows three possible task plans in the Cleanup task that place items in the top, middle and bottom drawers to achieve rewards of 1, 2, and 4, respectively. We compare the effect of different practice budgets on all methods in Figure 5. DP intelligently chooses which skills to learn based on the available budget: conservatively placing items in the top drawer when the budget is 100 episodes, placing items in the middle drawer under a budget of 150 episodes, and maximizing reward by placing items in the bottom drawer under a budget of 250 episodes. By contrast, baselines cannot adapt their behavior to the budget and greedily practice the easiest (and lowest-reward) task plan, irrespective of the budget. DP significantly outperforms prior active learning methods. As shown in Figure 5, DP and EES perform similarly under a low budget, but DP significantly outperforms all baselines in medium (150 7 Figure 5: We evaluate all methods on Cleanup with budgets (B) of 100 (low), 150 (medium), and 250 (high) episodes. While they perform similarly under a low budget, DP is significantly better under medium and high budgets. We report the mean and standard deviation averaged over 5 seeds. episodes) and high budget (250 episodes) settings. The greedy active learning baselines, EES and CI, reason myopically and, therefore, fail to discover higher-reward plans which require practicing skills that do not immediately improve task performance. This trend continues in the more complex Cleanup-Multi task, which requires sequencing 10 skills. Interestingly, random practice outperforms EES in this setting because EES lacks an exploration mechanism when the myopic task improvement measure ∆J task is zero for all skills. By contrast, DP can look ahead and hence does not suffer from this limitation. DP for larger problems. We evaluate the scalability of DP in Cleanup-Multi, which has 22 skills and 5000 abstract states resulting in a large bilinear program. Despite the size of this problem, DP consistently computes the optimal budget allocation within a maximum solve time of 6 minutes. In larger settings where the solver may not prove global optimality within the allotted time, the same optimization procedure can still return a bounded-suboptimal alloca- tion as Gurobi maintains an incumbent feasible solution and a global bound from convex relax- ations of the bilinear constraints, providing an optimality-gap certificate upon early termination. Figure 6: Real-world Breakfast task. Real-world Validation. We conduct experiments on a real Franka Panda robot to validate our design choices. To complete the Breakfast task, the robot must learn either to toast bread or microwave oatmeal. As shown in Figure 1, toasting provides a reward of 1 and requires practicing only the StartToaster skill, while microwaving oat- meal provides a reward of 2, but requires practicing two skills: OpenMicrowave and CloseMicrowave. The robot is provided with additional Pick and Place skills that can be used to transport items. We evaluate DP under two practice budgets: 30 episodes and 60 episodes. As shown in Figure 6, DP correctly chooses the conserva- tive toast-bread plan under the smaller budget, but learns to microwave oatmeal under the larger budget, thereby achieving higher task reward. 7 Conclusion We propose Deliberate Practice, an active skill learning algorithm that allocates a limited practice budget to many robot skills to provably maximize long-horizon planning performance. Our algo- rithm models each skill’s competence as a function of the practice budget, computes an optimal budget allocation, and sequentially practices the skills in the environment. Computing this allo- cation requires solving a challenging bilevel optimization problem, for which we derive an exact 8 single-level reformulation that can be solved using off-the-shelf solvers. Simulated and real-robot experiments show that our method is uniquely budget-aware and allows robots to better leverage their practice budgets compared to existing methods to master long-horizon manipulation tasks. 8 Limitations One key assumption of our approach is access to approximate priors over skill competence. If these priors are overly optimistic, the robot may allocate practice to task plans that are actually infeasible within the available budget. This limitation could be addressed by using conservative priors or by explicitly incorporating uncertainty in skill-competence predictions. A second limitation is that solving the bilinear program to global optimality may become challenging for very large problems. An important direction for future work is therefore to develop bounded-suboptimal optimization strategies. Finally, we plan to extend our approach to practicing generalizable skills acros multiple tasks on mobile manipulators, moving toward the broader goal of general-purpose robots. Acknowledgments This work was supported by the Office of Naval Research (ONR) under REPRISM MURI N000142412603 and ONR grant N00014-22-1-2592, as well as by the National Science Foundation (NSF) via grant 1955361 and ARL grant W911NF-18-2-0218. Partial funding was also provided by the Robotics and AI Institute. Sudarshan was supported by the Office of Naval Research (ONR) grant N00014-22-1-259. 9 References [1] P. Pastor, M. Kalakrishnan, S. Chitta, E. Theodorou, and S. Schaal. Skill learning and task outcome prediction for manipulation. In 2011 IEEE international conference on robotics and automation, pages 3828–3834. IEEE, 2011. [2] Y. Zhu, Z. Jiang, P. Stone, and Y. Zhu. Learning generalizable manipulation policies with object-centric 3d representations. arXiv preprint arXiv:2310.14386, 2023. [3] C. Chi, Z. Xu, S. Feng, E. Cousineau, Y. Du, B. Burchfiel, R. Tedrake, and S. Song. Diffusion policy: Visuomotor policy learning via action diffusion. The International Journal of Robotics Research, 44(10-11):1684–1704, 2025. [4] S. Cambon, R. Alami, and F. Gravot. A hybrid approach to intricate motion, manipulation and task planning. The International Journal of Robotics Research, 28(1):104–126, 2009. [5] C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L. P. Kaelbling, and T. Lozano-P ́ erez. Integrated task and motion planning. Annual review of control, robotics, and autonomous systems, 4(1):265–293, 2021. [6] B. Hedegaard, Z. Yang, Y. Wei, A. Jaafar, S. Tellex, G. Konidaris, and N. Shah. Beyond task and motion planning: Hierarchical robot planning with general-purpose policies. arXiv preprint arXiv:2504.17901, 2025. [7] J. Liang, M. Sharma, A. LaGrassa, S. Vats, S. Saxena, and O. Kroemer. Search-based task planning with learned skill effect models for lifelong robotic manipulation. In 2022 Interna- tional Conference on Robotics and Automation (ICRA), pages 6351–6357. IEEE, 2022. [8] I. Mishani, Y. Shaoul, and M. Likhachev. Mosaic: A skill-centric algorithmic framework for long-horizon manipulation planning. arXiv preprint arXiv:2504.16738, 2025. [9] J. Kober, J. A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11):1238–1274, 2013. [10] M. P. Deisenroth, G. Neumann, and J. Peters. A survey on policy search for robotics. Founda- tions and Trends® in Robotics, 2(1-2):1–142, 2013. [11] S. Gu, E. Holly, T. Lillicrap, and S. Levine. Deep reinforcement learning for robotic manipula- tion with asynchronous off-policy updates. In 2017 IEEE international conference on robotics and automation (ICRA), pages 3389–3396. IEEE, 2017. [12] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. nature, 518(7540):529–533, 2015. [13] D. Kalashnikov, A. Irpan, P. Pastor, J. Ibarz, A. Herzog, E. Jang, D. Quillen, E. Holly, M. Kalakrishnan, V. Vanhoucke, et al. Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on robot learning, pages 651–673. PMLR, 2018. [14] K. Anders Ericsson. Deliberate practice and acquisition of expert performance: a general overview. Academic emergency medicine, 15(11):988–994, 2008. [15] B. Da Silva, G. Konidaris, and A. Barto. Active learning of parameterized skills. In Interna- tional Conference on Machine Learning, pages 1737–1745. PMLR, 2014. [16] S. Chernova and M. Veloso. Interactive policy learning through confidence-based autonomy. Journal of Artificial Intelligence Research, 34:1–25, 2009. [17] A. Fabisch and J. H. Metzen. Active contextual policy search. The Journal of Machine Learn- ing Research, 15(1):3371–3399, 2014. 10 [18] S. Vats, O. Kroemer, and M. Likhachev. Synergistic scheduling of learning and allocation of tasks in human-robot teams. In 2022 International Conference on Robotics and Automation (ICRA), pages 2789–2795. IEEE, 2022. [19] S. Vats, M. Zhao, P. Callaghan, M. Jia, M. Likhachev, O. Kroemer, and G. Konidaris. Optimal interactive learning on the job via facility location planning. Robotics: Science and Systems (RSS), 2025. [20] S. Srivastava, E. Fang, L. Riano, R. Chitnis, S. Russell, and P. Abbeel. Combined task and motion planning through an extensible planner-independent interface layer. In 2014 IEEE international conference on robotics and automation (ICRA), pages 639–646. IEEE, 2014. [21] M. Fox and D. Long. Pddl2. 1: An extension to pddl for expressing temporal planning domains. Journal of artificial intelligence research, 20:61–124, 2003. [22] K. Hauser. Task planning with continuous actions and nondeterministic motion planning queries. In Proc. of AAAI Workshop on Bridging the Gap between Task and Motion Plan- ning, 2010. [23] C. R. Garrett, T. Lozano-P ́ erez, and L. P. Kaelbling. Pddlstream: Integrating symbolic planners and blackbox samplers via optimistic adaptive planning. In Proceedings of the international conference on automated planning and scheduling, volume 30, pages 440–448, 2020. [24] R. Chitnis, D. Hadfield-Menell, A. Gupta, S. Srivastava, E. Groshev, C. Lin, and P. Abbeel. Guided search for task and motion plans using learned heuristics. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pages 447–454. IEEE, 2016. [25] T. Silver, R. Chitnis, J. Tenenbaum, L. P. Kaelbling, and T. Lozano-P ́ erez. Learning sym- bolic operators for task and motion planning. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3182–3189. IEEE, 2021. [26] N. Shah and S. Srivastava. Hierarchical planning and learning for robots in stochastic set- tings using zero-shot option invention. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10358–10367, 2024. [27] S. Vats, M. Likhachev, and O. Kroemer. Efficient recovery learning using model predictive meta-reasoning. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 7258–7264. IEEE, 2023. [28] N. Kumar, T. Silver, W. McClinton, L. Zhao, S. Proulx, T. Lozano-P ́ erez, L. P. Kaelbling, and J. Barry. Practice makes perfect: Planning to learn skill parameter policies. In Robotics: Science and Systems (RSS), 2024. [29] B. Abbatematteo, E. Rosen, S. Thompson, T. Akbulut, S. Rammohan, and G. Konidaris. Com- posable interaction primitives: A structured policy class for efficiently learning sustained- contact manipulation skills. In 2024 IEEE International Conference on Robotics and Automa- tion (ICRA), pages 7522–7529. IEEE, 2024. [30] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. [31] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https:// w.gurobi.com. [32] M. Tawarmalani and N. V. Sahinidis. Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algorithms, software, and applications, volume 65. Springer Science & Business Media, 2013. 11 [33] E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026–5033. IEEE, 2012. [34] B. Liu, Y. Zhu, C. Gao, Y. Feng, Q. Liu, Y. Zhu, and P. Stone. Libero: Benchmarking knowl- edge transfer for lifelong robot learning. arXiv preprint arXiv:2306.03310, 2023. [35] A. Stout and A. G. Barto. Competence progress intrinsic motivation. In 2010 IEEE 9th inter- national conference on development and learning, pages 257–262. IEEE, 2010. [36] C. Colas, P. Fournier, M. Chetouani, O. Sigaud, and P.-Y. Oudeyer. Curious: intrinsically motivated modular multi-goal reinforcement learning. In International conference on machine learning, pages 1331–1340. PMLR, 2019. [37] N. Hogan. Impedance control: An approach to manipulation: Part i—theory. Journal of Dynamic Systems, Measurement, and Control, 107(1):1–7, 1985. [38] N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolution strate- gies. Evolutionary computation, 9(2):159–195, 2001. [39] G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part i—convex underestimating problems. Mathematical programming, 10(1):147–175, 1976. [40] S. Garrido-Jurado, R. Mu ̃ noz-Salinas, F. J. Madrid-Cuevas, and M. J. Mar ́ ın-Jim ́ enez. Auto- matic generation and detection of highly reliable fiducial markers under occlusion. Pattern Recognition, 47(6):2280–2292, 2014. [41] G. Bradski. The opencv library. Dr. Dobb’s Journal: Software Tools for the Professional Programmer, 25(11):120–123, 2000. [42] I. A. Sucan, M. Moll, and L. E. Kavraki. The open motion planning library. IEEE Robotics & Automation Magazine, 19(4):72–82, 2012. [43] S. Chitta, I. Sucan, and S. Cousins. Moveit![ros topics]. IEEE robotics & automation maga- zine, 19(1):18–19, 2012. 12 A Appendix A.1 Linear Programming Formulation of MDPs We leverage the linear programming (LP) formulation of MDPs to instantiate SolveMDP in Equa- tion 1. Using the primal LP formulation for computing the optimal value function of an MDP, we get the following bilevel problem: max b X s∈S e s v s subject to X u∈U b u ≤ B v s ∈ arg min v X s e s v s subject to v s ≥ r a s + γ X s ′ ̄ P a s ′ (b)v s ′ , ∀a,s v s unconstrained, ∀s (4) This is a bilevel program (also called a Stackelberg game), where the inner program (follower) is conditioned on decision variables that are chosen by the outer program (leader). In particular, the follower’s constraints depend on the budget decided by the leader since the transition function ̄ P is a function of the budget b via the competence improvement function ̄ P a s ′ = f improve (P a s ′ ,b) A.2 Single-Level Reformulation The follower is a b-parameterized LP for which Slater’s conditions hold. Lemma 1. Suppose b is given. Then the LP min v e T v : v s ≥ r a s + γ P s ′ ̄ P a s ′ (b)v s ′ , ∀s,a satisfies Slater’s condition. Proof. The satisfaction of Slater’s condition is equivalent to showing that there exists ˆv such that inequalities are strictly satisfied. Let α = max s,a r a s . Then, it is easy to verify ˆv s = α γ 2 ∀s satisfies the inequalities strictly. This proves the claim. It is intractable to directly solve the bilevel program. A standard approach for reformulating such bilevel problems into single-level problems is to replace the follower with its KKT conditions since they are both necessary and sufficient for optimality. This results in a single-level optimization with complementarity constraints which can be solved using mixed integer programming. However, this formulation is usually difficult to solve in practice. Our key observation is that both the leader and the follower are optimizing the same objective. Hence, the bilevel problem can be rewritten as a max-min problem: max b∈B min v e T v : v s ≥ r a s + γ X s ′ ̄ P a s ′ (b)v s ′ , ∀s,a where, B :=b u : X b u ≤ B (5) Since the LP satisfies Slater’s condition (Lemma 1) strong duality holds, i.e. the primal and dual are both feasible and attain their respective optimal values which are equal. By strong duality, the dual of the follower attains the same optimum as the primal. Hence, we can replace the inner min 13 problem with its dual max LP. max b∈B max μ X ∀s∈S X ∀a∈A r a s μ a s subject to X ∀a∈A μ a s − γ X s ′ X ∀a P a s ′ s μ a s ′ = e s ,∀s where,B :=b u : X b u ≤ B (6) The inner problem is feasible for every choice of budget. Hence, we can jointly maximize the budget and dual variables in single max optimization: max b,μ X ∀s∈S X ∀a∈A r a s μ a s subject to X ∀a∈A μ a s − γ X s ′ X ∀a ̄ P a s ′ s (b)μ a s ′ = e s ,∀s X b u ≤ B (7) This is a surprisingly simpler single-level program, where the budget constraints have been added to the dual LP formulation of the MDP. Note that it is a non-linear problem even when the competence improvement function is linear. However, standard optimizers, such as Gurobi [31] can natively handle such bilinear constraints via the classic McCormick Envelope [39]. A.3 Experimental Details A.3.1 Skill Practice We use CMA-ES to practice robot skills. CMA-ES is a gradient-free evolutionary-based optimiza- tion approach for reward maximization. For each skill, we define a reward function and optimize the corresponding interaction policy parameters using CMA-ES [38]. We use CMA-ES because our objective is evaluated through rollouts and is not differentiable with respect to the policy parameters. CMA-ES is a robust gradient-free optimizer for such continuous black-box objectives. We imple- ment all learnable skills as Cartesian-space impedance controllers [37] parameterized by waypoints and impedance parameters. The optimizer takes as input the policy parameters to be optimized, together with a Gaussian prior over these parameters, specified by a mean and diagonal covariance matrix. At each iteration of CMA-ES, we sample N = 6 candidate parameter vectors from the current Gaussian search distribution. Each candidate is evaluated by executing the corresponding policy on the real robot in the environment. At the end of each episode, the robot receives a binary reward, and the top half candidates are used to update the mean and covariance of the search distribution. Over successive iterations, the search distribution shifts toward regions of the parameter space that provide higher rewards and improve competence. A.4 Baselines 1. Estimate, Extrapolate, Situate (EES) estimates the expected improvement from practic- ing each skill independently using f improv (π, 1). For each skill, it uses a task planner to compute the expected improvement in task performance after practicing that skill for one round: arg max π ∆J task (π) = arg max π J task ( ̄ P π )− J task (P ), where ̄ P π is the skill transition matrix after practicing π for one round. J task is computed by solving the MDP induced by P using its linear programming formulation. The robot greedily practices the skill predicted to yield the largest task-performance improvement in the next round [28]. 14 Figure 7: (a) Breakfast domain. The robot can either toast bread to achieve reward 1 or microwave oatmeal to achieve reward 2. The former requires practicing StartToaster while the latter requires practicing OpenMicrowave and CloseMicrowave. (b) Cleanup-multi domain. The achieves reward 1 for placing all objects in the top drawer, reward 2 for placing them in the middle drawer and reward 4 for placing them in the bottom drawer. The lower drawers are blocked by the upper drawers, so the robot must learn CloseDrawer skills to place objects in the lower drawers. 2. Competence Improvement (CI) practices the skill with the highest expected competence improvement [35, 36], i.e., arg max π f improv (π, 1) CI is biased towards skills that are easy to learn and, hence often wastes time on skills that are not relevant to the task. 3. Least Competent First (LCF) practices the skill with the lowest current competence, i.e,. arg min π p π This encourages the robot to focus on underdeveloped skills and gradually master the full skill set. However, it can waste time on skills that are not relevant to the task or are too hard to learn within the practice budget. 4. Random (R) unformly randomly samples a reachable skill for practice. A.5 Real-Robot Breakfast Domain As shown in Figure 7, the Breakfast task is conducted on a bimanual robot with two Franka Panda arms.. The skill library comprises 7 skills: PickBread, PlaceBread, StartToaster, OpenMicrowave, PickBowl, PlaceBowl, CloseMicrowave. Our perception system in- cludes a wrist mounted Intel-Realsense D435 camera. Auroco Markers are mounted on the interior of the microwave door. Once the door is opened, the markers are detected using OpenCV Auroco Detection [40, 41], and depth measurements are used to estimate the dimensions and position of the microwave door. The resulting detected pose is used to construct a collision model of the scene, which enables collision-aware motion planning using OMPL [42] through MoveIt [43]. Contact- rich skills StartToaster, OpenMicrowave, CloseMicrowave require forceful interaction with the toaster and microwave and are implemented using Cartesian-space impedance controllers parameterized by relative actions in the end-effector frame and impedance parameters that deter- mine the forces applied by the robot during interaction. These impedance parameters are sensitive 15 Figure 8: Breakfast domain. After pressing the microwave button, the robot estimates the position of the microwave door using a RealSense wrist camera. This information is used to construct a collision model of the scene for motion planning. to the object properties and task context, and therefore must be learned through practice. To ensure safe exploration, we specify a bounded range of impedance parameters that the robot may explore and use a reward function to encourage the robot to apply the minimum force necessary to solve the task. A.5.1 Cleanup Domain The Cleanup domain requires a Franka Panda robot to place an item in one of three open drawers to clean the table. Cleanup-multi is a harder version with 4 items on the table (shown in Figure 7). Both of them are implemented in MuJoCo [33] using LIBERO [34] which provides realistic physics simulation. The robot receives higher reward for placing items in lower drawers. However, these placements are more challenging to learn because they require the robot to first learn how to close the upper drawers. The Cleanup domain has 41 abstract states, and Cleanup-multi has 5001 ab- stract states consisting of the following variables: DrawerState (open, closed) for every drawer, ObjectState (in-hand, on-table, in-top-drawer, in-middle-drawer, in-bottom-drawer) for every object, and a terminal failure state. The robot is provided with abstract specifications for 22 manip- ulation skills including their preconditions, termination conditions and effects: 1. OpenDrawer × top, middle, bottom drawer: opens a drawer by grasping the handle and pulling it. The pull action is learned through practice. 2. CloseDrawer×top, middle, bottom drawer: closes a drawer by pushing. The push action is learned through practice. 3. Pick× 4 items: picks an object with a grasp pose learned through practice. 4. Place × 4 items × 3 drawers: moves the object to the target drawer and places it. The object release position depends on the object size and the target drawer and is learned from practice. All skills are implemented as Cartesian-space impedance controllers with a fixed impedance and waypoints defined with respect to the target object. We use privileged information about object positions from the simulator to prameterize all object-centric skills. The highest reward task plan requires sequencing 10 skills to first close the top two drawers and place all items in the lowest drawer. 16