{"id":"f5fa2df3-1b7b-4ea4-9457-5d4d87045002","arxiv_id":"2505.00490","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"COIL casts multi-task interactive robot learning as an uncapacitated facility location problem and uses approximation algorithms to plan skill, preference, and help queries that reduce human effort.","lead":"COIL is a new planner that decides, for every task in a robot's work sequence, whether the robot should act alone, ask the person to do it, learn a new skill, or request the user's preference, all to minimize total human effort. It models this as a facility location problem with fast polynomial-time solvers and tests the idea in simulated and physical manipulation tasks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"UFL encoding permits skill facilities to be opened without any corresponding teaching query at the origin task, so solver-returned plans may be unexecutable.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: the UFL formulation does not enforce that a skill facility at task i also serves task i, which is necessary for the teaching action to occur. This concern is not merely theoretical; the UFL solver is unconstrained and can select cheaper infeasible assignments, invalidating the claimed equivalence between UFL solutions and executable plans. The paper's theoretical contribution depends on this equivalence for both the cost-optimality claim and the approximation guarantee. The concern is testable with a small constraint change or a counterexample instance. The empirical results may still be informative, and the issue may be fixable by adding the origin-assignment constraint or by proving that an optimal UFL solution always satisfies it, so the reader's CONDITIONAL verdict is appropriate and I recommend no change.","tokens_in":20945,"tokens_out":9837,"duration_ms":100791,"concrete_test":"Instrument SOLVE_UFL on a two-task instance with c_hum=100, c_skill=10, c_11=200, c_12=10 and verify whether the returned UFL solution opens skill facility 1 without assigning task 1 to it. Then add the constraint that any opened skill facility must serve its origin task (or equivalently restrict skill facilities to service only the origin task and future tasks only if the origin task is also served), re-solve, and compare. If the constrained optimum has higher cost or a different action sequence on this instance or on any of the 30 Gridworld/Manipulation task sequences, the original UFL encoding was producing infeasible plans.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim, that COIL's UFL solutions are executable interaction plans with bounded suboptimality, rests on an unstated feasibility constraint. In Algorithm 1 (lines 6-8), each skill facility i_skill has opening cost c_skill and service costs c_skill_ij for all j >= i, but nothing forces demand i to be assigned to i_skill. A UFL solver can therefore open i_skill while assigning task i to the human facility, and use i_skill only for later tasks. The interaction protocol executes one action per task, and the only way to acquire skill pi_i is to issue a skill request while processing task i. If task i is assigned to the human, no teaching query occurs, so the robot never obtains pi_i and later assignments to i_skill are meaningless. The UFL objective does not include a constraint such as y_i_skill = 1 => x_{i,i} = 1. Concrete failure: with c_hum=100, c_skill=10, c_11=200, c_12=10, the UFL optimum opens skill 1 (10), assigns task 1 to the human (100), and task 2 to skill 1 (10), total 120, while any executable plan costs at least 200 (human for both tasks) or 210 (skill for task 1 and 2). Thus the claimed cost-optimality and approximation guarantees apply to a relaxation of the real problem. Figure 2 and Algorithm 1 describe a facility/action mapping but never prove that every UFL solution decodes into a sequentially executable action sequence; the Limitations section also does not flag this gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes COIL, a multi-task interactive learning planner that chooses among skill requests, preference requests, and human help for each task in a known sequence, with the goal of minimizing total human burden. The central idea is to formulate the known-preferences subproblem as an uncapacitated facility location (UFL) problem, where tasks are demands and human, skill, and robot actions are facilities; bounded-suboptimal plans are then obtained in polynomial time via an off-the-shelf approximation algorithm. For preference uncertainty, the planner performs one-step belief-space planning that uses the UFL planner as a subroutine. The paper reports experiments in a Gridworld simulator, a simulated 7-DoF manipulation domain, and a physical conveyor task, claiming 12%--20% cost reductions in simulation and 23% in the physical experiment relative to the best baseline, while maintaining task success.","tokens_in":21226,"tokens_out":9169,"duration_ms":105701,"significance":"If the UFL equivalence is correct, the paper makes a valuable theoretical contribution by connecting multi-task interactive learning to a well-studied operations-research problem, enabling polynomial-time bounded-suboptimal planning and the use of off-the-shelf solvers. The empirical evaluation is comparatively extensive: 30 randomized task sequences, three human cost profiles, several challenging-to-learn settings, online replanning after teaching failures, and a physical robot demonstration with statistical comparisons. These experiments are a useful benchmark among planners under a common cost model. However, the central formal claim is currently not supported: as detailed in the major comments, the UFL formulation admits solutions that cannot be executed under the paper's own interaction protocol, so the optimality and approximation guarantees have been proven only for a relaxed problem. The paper would also benefit from clarifying which approximation guarantee actually applies to the constructed instances.","major_comments":[{"comment":"The UFL formulation does not enforce that an opened skill facility serves its own origin task. Under the interaction protocol, exactly one action is executed per task and skill pi_i can be acquired only at task tau_i; therefore a UFL solution that opens i_skill, assigns tau_i to the human facility, and assigns later tasks to i_skill is not executable. As a concrete failure, with c_hum=100, c_skill=10, c_11=200, and c_12=10, the UFL optimum opens skill facility 1 (cost 10), serves task 1 by the human (100), and serves task 2 by skill facility 1 (10), giving total 120, while every executable plan costs at least 200. The manuscript neither states nor verifies the required constraint y_i_skill => x_{i,i}=1, so the claimed cost-optimality and bounded-suboptimality guarantees apply only to a relaxation of the actual interaction problem. This gap is load-bearing for the paper's central contribution and should be fixed by proving that every UFL solution decodes into an executable plan, or by reformulating the optimization with the self-assignment constraint and re-deriving the guarantees.","section":"Section IV-A, Algorithm 1"},{"comment":"The paper invokes the 3-approximation guarantee of Jain and Vazirani without establishing that the constructed UFL instance is metric. The service-cost matrix contains infinite entries (human facilities cannot serve non-origin tasks) and facility-dependent offsets derived from a learned reward model, so the instance is not obviously metric. For non-metric UFL, the stated 3-approximation does not follow; the paper mentions a log(n) bound 'otherwise' but does not identify which bound is being used for the experimental instances. The authors should either prove the metric property of the constructed cost structure or explicitly state and rely on the appropriate worst-case approximation bound.","section":"Section IV-A, Approximation Algorithms"}],"minor_comments":[{"comment":"The condition 'if cpref + ¯JPb1 ≤ J then' is not a well-formed expression as printed; it should be rewritten with explicit parentheses or a definition of the averaging operator so that the preference-request decision is unambiguous.","section":"Algorithm 1, line 22"},{"comment":"The notation 'ci_query = ci_hum + ci_skill + ci_pref' mixes superscripts and subscripts inconsistently; please clarify whether these are task indices or type labels, and make the equation typographically consistent.","section":"Equation (2) and Section III"},{"comment":"Several reported statistics use 'F = −3.54' where a t-statistic is intended, and p-values are inconsistently reported as p<0.01 and p<0.001 in the text versus the figures; these should be corrected and made uniform.","section":"Appendix E-D and Figure 3"},{"comment":"The axes are unclear: the caption mentions 'Ratio', 'Suboptimality', and 'Speedup', but the figure does not clearly indicate which curve uses which scale. Please add axis labels and a legend.","section":"Figure 4"},{"comment":"The baselines C-ADL and IG use hyperparameters (confidence threshold alpha=0.8 and information-gain scale beta=0.01) that appear to be chosen on the same evaluation domains; please report sensitivity analyses or explain why these choices do not bias the comparison.","section":"Section V-A and Appendix D-D"},{"comment":"The physical experiments use only five task sequences, with one teaching-failure run reported separately; the claim of 'significantly lower cost' should be supported by an appropriate statistical test or explicitly described as a descriptive comparison.","section":"Table III and Section VI-D"}],"recommendation":"major_revision","confidential_remarks":"The infeasibility counterexample in major comment 1 is decisive: the UFL formulation as written optimizes over a superset of executable interaction plans. This must be resolved before the theoretical claims can stand. The authors may be able to repair the model by adding a self-assignment constraint and re-analyzing the approximation guarantee, or by reframing the contribution as a heuristic planning method with empirical support. I do not recommend outright rejection because the experimental study is substantive and the underlying idea is promising, but the formal claims in the abstract and Section IV.A need to be corrected rather than merely qualified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper proposes COIL, a planner that decides for each task in a stream whether the robot should execute a known skill, ask to be taught a new skill, ask a preference, or hand the task to the human. The genuinely new piece is the reduction of this multi-task interaction planning problem to uncapacitated facility location (UFL), which brings polynomial-time bounded-suboptimal algorithms (Jain-Vazirani) and off-the-shelf solvers to bear. That reduction is new relative to the authors' prior MIP-based ADL, and the one-step belief-space extension for preference uncertainty is a reasonable way to keep the UFL benefits. The experimental work is solid: 30 seeds, three cost profiles, three domains including a physical conveyor setup, and the cost reductions (12-20% simulation, 23% physical) are consistent.\n\nThe soft spot is not in the experiments; it is in the claimed equivalence between UFL solutions and executable interaction plans. The UFL encoding places a skill facility at task i with service costs to all later tasks, but nothing forces the plan to actually request the skill at task i. A solver can open skill i, assign task i to the human, and then use skill i on later tasks, which is impossible in the interaction protocol because the skill is acquired only by requesting it at its origin task. The stress-test example makes this concrete: with chum=100, cskill=10, c11=200, c12=10, the UFL optimum costs 120 while every executable plan costs at least 200. The paper never states or proves the constraint y_i => x_{i,i}, and the Limitations section doesn't mention it. The 'optimal' language also overstates what is a model-relative, approximate, one-step-greedy method.\n\nThat said, the flaw is likely fixable. If the authors add the constraint (or prove it's implied under their cost model) the theory would match the protocol. The empirical benchmark value remains interesting even if the theoretical guarantee needs qualification. This deserves peer review: a serious referee should ask for the feasibility constraint and a revised theoretical claim. I'd suggest major revision.\n\nOverall: new formulation, honest experiments, one load-bearing gap in the theory. Worth engaging, especially for readers in interactive robot learning and task allocation.","headline":"New and useful UFL formulation for multi-task interactive learning, but the central equivalence between UFL solutions and executable plans is not proven and can be violated; fixable, deserves review.","tokens_in":21764,"tokens_out":3833,"would_cite":false,"duration_ms":39191,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"COIL recasts multi-task interactive robot learning as an uncapacitated facility location problem, making query selection a polynomial-time, bounded-suboptimal planning task that cut measured human cost by 12–20% in simulation and 23% on a…","keywords":["interactive robot learning","facility location","multi-task planning","preference queries","skill learning","human-robot collaboration","approximation algorithms","belief-space planning"],"falsifier":"Run COIL on a two-task sequence $\\tau_1,\\tau_2$ with identical objects, set $c_{\\mathrm{hum}}$ high and $c_{\\mathrm{skill}}$ low, and inspect the returned plan; if the solver opens the skill facility at $\\tau_2$ and serves $\\tau_1$ from it without also serving $\\tau_2$ by that facility, the plan cannot be executed by the robot's protocol, and the claimed cost guarantee would not transfer. This check directly tests whether the UFL solution set coincides with the executable policy set.","tokens_in":20712,"feed_emoji":"🤖","tokens_out":7352,"duration_ms":71774,"temperature":0.7,"pith_summary":"This paper argues that multi-task interactive robot learning—deciding, for each task in a known sequence, whether to ask the user to teach a skill, answer a preference question, or do the task by hand—can be recast exactly as an uncapacitated facility location (UFL) problem. In that recasting, each task is a demand, each possible query is a facility with an opening cost equal to the human's effort, and serving a demand costs the robot's execution cost minus the predicted reward of the skill. Because UFL has polynomial-time approximation algorithms, COIL can produce bounded-suboptimal interaction plans that in the paper's experiments cut total human burden by 12–20% in simulation and 23% in a physical conveyor task, while keeping task success intact. A one-step belief-space extension decides when a preference query is worth asking before committing to a plan. The appeal is practical: if the reduction holds, robots can plan long sequences of on-the-job learning without exponential search.","feed_headline":"Facility-location planning cuts robot-teaching effort by up to 23%","feed_subtitle":"Treating each task as a demand node, COIL picks the queries that minimize total user burden across the whole job.","key_machinery":"The load-bearing object is the uncapacitated facility location instance $\\langle D,F,f_i,c_{ij}\\rangle$ built from the task sequence. Demands are the tasks; facilities are the three query/execution actions—human help, skill teaching, and zero-cost use of an already-learned skill—each with opening cost equal to its human effort and service costs computed from a similarity-based safety model $\\rho^{\\mathrm{safe}}_\\pi(\\tau',\\theta')$ and the current preference belief $b_\\Theta$. The UFL objective $\\min \\sum_{i\\in F'} f_i + \\sum_{j\\in D} \\min_{i\\in F'} c_{ij}$ is what carries the argument: it converts the combinatorial look-ahead over query types into a problem with known polynomial-time approximation algorithms, and the same facility-location solver is reused as a subroutine inside the one-step belief-space planner for preference requests.","core_discovery":"COIL's central claim is that optimal interaction can be planned globally rather than myopically: over a fixed sequence of tasks, the choice between learning a skill, requesting a preference, asking the human to do the task, or executing an existing skill is a facility location decision. A skill facility opened at task $i$ costs $c_{\\mathrm{skill}}$ and can serve any later task $j$ at service cost $c_{ij}^{\\mathrm{skill}}=c_{\\mathrm{rob}}-\\max_{\\theta\\in\\Theta}\\hat{R}_j(\\pi_i,\\theta)$; a human facility costs $c_{\\mathrm{hum}}$ and serves only its own task; a robot facility costs zero and serves any task the already-learned skill can reach. Minimizing total opening plus service cost over all tasks yields the interaction plan, and the paper proves that using a standard primal-dual UFL approximation keeps the runtime polynomial in the number of tasks and preference parameters while guaranteeing bounded suboptimality. When preferences are uncertain, COIL evaluates the expected value of asking the current task's preference by comparing the current plan against the expected cost of replanning under each possible response, and executes the preference request only when the expected improvement outweighs $c_{\\mathrm{pref}}$. The paper reports the resulting cost reductions and shows the planner reallocates tasks to the human when a skill repeatedly fails to be learned.","pith_inferences":["The UFL mapping suggests a natural extension to streaming or unordered task sets: because facility location solvers are incremental, one could re-solve or update the plan as new tasks arrive, avoiding the paper's stated need to know the full sequence in advance.","If service costs were learned rather than hand-built from task similarity, the same UFL machinery would apply; a testable extension would replace $\\rho^{\\mathrm{safe}}$ with a learned generalization model and measure whether the bounded-suboptimality guarantee still holds in practice.","The equivalence between UFL solutions and executable plans would be tightened by enforcing that a skill facility opened at task $i$ also serves task $i$; until that constraint is explicit, the claimed optimality guarantee applies to the UFL problem, not necessarily to the robot's one-action-per-task execution."],"forward_implications":["For a known task sequence, COIL can plan skill, preference, and human-help queries in polynomial time, so planning stays fast as the horizon grows; the paper reports large speedups over an optimal mixed-integer formulation with near-identical plan cost.","The planner will favor learning skills for objects that repeat and delegate singleton or hard-to-learn tasks to the human, which is the behavior that produces the measured 12–20% (simulation) and 23% (physical) reductions in interaction cost.","Online replanning with an updated teaching-success probability $\\lambda_{\\mathrm{teach}}$ lets the robot stop requesting demonstrations for skills that keep failing and instead assign those tasks to the human.","Preference requests are made only when the expected future plan improvement outweighs the user's answer cost, so the user is not asked about preferences for tasks the robot will not perform.","The same planner transfers to a physical conveyor sorting task, indicating the cost model and UFL solver behave outside simulation."],"supporting_citations":[{"why":"Supplies the uncapacitated facility location formulation and its approximation-theoretic background that the reduction leans on.","marker":"[35, chapter 4]"},{"why":"Provides the primal-dual approximation algorithm used as the polynomial-time UFL solver inside COIL.","marker":"[16]"},{"why":"Defines the ADL mixed-integer programming approach that COIL's facility location formulation is designed to replace, and whose confidence-based variant is a baseline.","marker":"[33]"},{"why":"Motivates multiple query types with associated human costs, the interaction paradigm COIL extends to multi-task planning.","marker":"[10]"},{"why":"Introduces the hidden-parameter MDP model used to represent tasks with unknown user preference parameters.","marker":"[9]"},{"why":"Provides the Gridworld simulation environment used for the main cost-comparison experiments.","marker":"[7]"},{"why":"Provides the simulated 7DoF manipulation environment used for scalability and teaching-failure experiments.","marker":"[38]"},{"why":"Supplies the pretrained open-vocabulary pick-and-place policy used to generate demonstrations in the physical conveyor experiments.","marker":"[18]"},{"why":"Supplies the state-of-the-art mixed-integer programming solver used as the optimal baseline in the scalability comparison.","marker":"[11]"}],"fun_headline_variants":["COIL: facility-location planning for multi-task robot learning","One planner, three queries: cut human effort in robot teaching","Multi-task robot learning: facility-location planner reduces human burden","COIL: optimal multi-task interaction planner minimizes user effort","Balancing skill, preference, and help queries cuts teaching effort"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The planning formulation assumes that whenever the robot pays to learn a skill for a task, it is also assigned to perform that same task; if the optimal facility-location solution instead learns a skill and only uses it on later, similar tasks, the resulting plan may not be something the robot can actually execute.","fun_headline_variants_meta":{"raw":{"variants":["COIL: facility-location planning for multi-task robot learning","One planner, three queries: cut human effort in robot teaching","Multi-task robot learning: facility-location planner reduces human burden","COIL: optimal multi-task interaction planner minimizes user effort","Balancing skill, preference, and help queries cuts teaching effort"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001362,"raw_usage":{"total_tokens":5548,"prompt_tokens":993,"completion_tokens":4555,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":609,"completion_tokens_details":{"reasoning_tokens":4470}},"tokens_in":609,"tokens_out":4555,"duration_ms":28988,"temperature":1.0,"reasoning_tokens":4470,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:42:47.115537+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run COIL on a two-task sequence $\\tau_1,\\tau_2$ with identical objects, set $c_{\\mathrm{hum}}$ high and $c_{\\mathrm{skill}}$ low, and inspect the returned plan; if the solver opens the skill facility at $\\tau_2$ and serves $\\tau_1$ from it without also serving $\\tau_2$ by that facility, the plan cannot be executed by the robot's protocol, and the claimed cost guarantee would not transfer. This check directly tests whether the UFL solution set coincides with the executable policy set.","supporting_citations":[{"cited_title":"Primal-dual ap- proximation algorithms for metric facility location and k-median problems","cited_arxiv_id":null,"evidence_quote":"Provides the primal-dual approximation algorithm used as the polynomial-time UFL solver inside COIL."},{"cited_title":"Synergistic scheduling of learning and allocation of tasks in human-robot teams","cited_arxiv_id":null,"evidence_quote":"Defines the ADL mixed-integer programming approach that COIL's facility location formulation is designed to replace, and whose confidence-based variant is a baseline."},{"cited_title":"INQUIRE: INteractive Querying for User- aware Informative REasoning","cited_arxiv_id":null,"evidence_quote":"Motivates multiple query types with associated human costs, the interaction paradigm COIL extends to multi-task planning."},{"cited_title":"Hidden parameter markov decision processes: A semiparamet- ric regression approach for discovering latent task parametrizations","cited_arxiv_id":null,"evidence_quote":"Introduces the hidden-parameter MDP model used to represent tasks with unknown user preference parameters."}],"review_version":1}