# When Should a Robot Replan? Regret-Guided Update Scheduling in Time-Varying MDPs [Canonical reading](https://escapemeridian.com/readings/when-should-a-robot-replan-regret-guided-update-scheduling-in-4164370b) In their paper, Negin Musavi, Gokul Puthumanaillam, Ruben Hernandez, William Schafer and Melkior Ornik ask when a robot should spend limited onboard energy and compute on a fresh plan as its environment changes. They study time-varying Markov decision processes (TVMDPs), where transition dynamics drift over time at a rate bounded by an assumed known limit. In their “skip-update” scheme, the robot estimates the transition kernel—the probabilities of moving between states—and computes a finite-horizon policy at selected update times. Between updates, it reuses that policy with a propagated state estimate. The authors analyze how dynamic regret, a measure of the cost of not adapting to changing dynamics, grows during intervals without updates. They use the resulting bound to develop an online rule that allocates a limited update budget adaptively, guided by regret. The paper reports evaluations in a simulated Mars-rover navigation task with changing slip dynamics and on a Crazyflie quadrotor in indoor obstacle fields; adaptive allocation outperforms other budgeted baselines in these evaluations. The approach makes update timing—not just the choice of plan—a central part of operating under compute and energy limits. The abstract does not establish how the reported advantage carries over to other environments or how performance changes when the assumed bound on transition drift is.\* Headline and summary by Escape Meridian, prepared by Luna from the attributed source. A source check is not independent confirmation of the source’s claims. ## Original source arXiv eess.SY · Article Original source date: Jun 15, 2026 (2026-06-15). Date basis: Date basis not provided. Added to Escape Meridian: 2026-11-10T09:25:45.277Z. First observed: 2026-11-03T08:58:53.498Z. Retrieved: 2026-11-03T22:31:09.883Z. - [When Should a Robot Replan? Regret-Guided Update Scheduling in Time-Varying MDPs](https://arxiv.org/abs/2606.16972) ## Limits The analysis is framed for time-varying Markov decision processes with a known bound on the rate of transition drift. The abstract reports evaluations in a simulated Mars-rover task and on a Crazyflie quadrotor in indoor obstacle fields; it does not provide numerical results or establish performance in other settings. ## Open question How does adaptive allocation perform in environments beyond the simulated rover task and indoor quadrotor obstacle fields? ## Source-stated The authors frame replanning frequency as a resource-allocation problem because onboard energy and compute limit full state estimation and replanning. > onboard energy and compute budgets cap how often a full state estimation and re-planning step can be performed. - [Supporting source](https://arxiv.org/abs/2606.16972) ## Source-stated The proposed skip-update scheme estimates the transition kernel and computes a finite-horizon policy at chosen update times, then reuses the policy between updates. > at chosen update times, the agent estimates the transition kernel by maximum likelihood and computes a finite-horizon policy, and between updates reuses this policy under a propagated state estimate. - [Supporting source](https://arxiv.org/abs/2606.16972) ## Source-stated The authors analyze dynamic regret during skip intervals and use the resulting bound to devise an online rule for adaptive update-budget allocation. > the resulting bound answers the opening question via an online, regret-guided update rule that allocates the budget adaptively. - [Supporting source](https://arxiv.org/abs/2606.16972) ## Source-stated The abstract reports that adaptive allocation outperforms other budgeted baselines in a simulated Mars-rover task and a Crazyflie quadrotor task. > We evaluate the rule in a simulated Mars-rover navigation task with time-varying slip dynamics and on a Crazyflie quadrotor in indoor obstacle fields. Adaptive allocation outperforms other budgeted baselines. - [Supporting source](https://arxiv.org/abs/2606.16972) ## Source and contributor context Musavi, Negin, Puthumanaillam, Gokul, Hernandez, Ruben, Schafer, William, Ornik, Melkior · Article author These are credits stated by the source; they do not establish a profile match or authorship of every passage. ## Source media No suitable media was found by the supported page extraction. ## Terms and references Reference context selected by Escape Meridian; separate from source evidence. Entity mentions do not establish authorship, involvement or endorsement. ## TIME TIME is a news magazine publishing reporting on world affairs, business, technology and the workers behind digital services. - [Explore this context](/entities/time) - [Reference](https://time.com/) ## arXiv arXiv is a research manuscript repository where authors share papers that may not yet have been peer reviewed. - [Explore this context](/entities/arxiv) - [Reference](https://arxiv.org/) - [Reference](https://info.arxiv.org/help/api/index.html) ## Editorial provenance Version 1. Publication ID: 865ea2e8-41f5-4783-8d8c-779a43c871a8. Prepared by gpt-6-luna; grounding review by gpt-6-luna. Source check: uncertain by anthropic/claude-opus-5.5 on 2026-11-10T09:25:45.277Z. This checks fidelity to the source, not whether its claims are independently true. Editorial selection: accept; reasons: material\_development. Observation: faf574cfd042fad200d6b68df0cb5638029eb2bb675e9834d09d4054c5bf00cb. Source text hash: d745c5ca271416fe44972b74e5be84f78532cf1b7f80c363d544bf25b91fbdac. ## Revision and source-check history ### Version 1 — 2026-11-10T09:25:45.277Z In their paper, Negin Musavi, Gokul Puthumanaillam, Ruben Hernandez, William Schafer and Melkior Ornik ask when a robot should spend limited onboard energy and compute on a fresh plan as its environment changes. They study time-varying Markov decision processes (TVMDPs), where transition dynamics drift over time at a rate bounded by an assumed known limit. In their “skip-update” scheme, the robot estimates the transition kernel—the probabilities of moving between states—and computes a finite-horizon policy at selected update times. Between updates, it reuses that policy with a propagated state estimate. The authors analyze how dynamic regret, a measure of the cost of not adapting to changing dynamics, grows during intervals without updates. They use the resulting bound to develop an online rule that allocates a limited update budget adaptively, guided by regret. The paper reports evaluations in a simulated Mars-rover navigation task with changing slip dynamics and on a Crazyflie quadrotor in indoor obstacle fields; adaptive allocation outperforms other budgeted baselines in these evaluations. The approach makes update timing—not just the choice of plan—a central part of operating under compute and energy limits. The abstract does not establish how the reported advantage carries over to other environments or how performance changes when the assumed bound on transition drift is.\* ## Original source arXiv eess.SY · Article Original source date: Jun 15, 2026 (2026-06-15). Date basis: Date basis not provided. Added to Escape Meridian: 2026-11-10T09:25:45.277Z. First observed: 2026-11-03T08:58:53.498Z. Retrieved: 2026-11-03T22:31:09.883Z. - [When Should a Robot Replan? Regret-Guided Update Scheduling in Time-Varying MDPs](https://arxiv.org/abs/2606.16972) ## Limits The analysis is framed for time-varying Markov decision processes with a known bound on the rate of transition drift. The abstract reports evaluations in a simulated Mars-rover task and on a Crazyflie quadrotor in indoor obstacle fields; it does not provide numerical results or establish performance in other settings. ## Open question How does adaptive allocation perform in environments beyond the simulated rover task and indoor quadrotor obstacle fields? ## Source-stated The authors frame replanning frequency as a resource-allocation problem because onboard energy and compute limit full state estimation and replanning. > onboard energy and compute budgets cap how often a full state estimation and re-planning step can be performed. - [Supporting source](https://arxiv.org/abs/2606.16972) ## Source-stated The proposed skip-update scheme estimates the transition kernel and computes a finite-horizon policy at chosen update times, then reuses the policy between updates. > at chosen update times, the agent estimates the transition kernel by maximum likelihood and computes a finite-horizon policy, and between updates reuses this policy under a propagated state estimate. - [Supporting source](https://arxiv.org/abs/2606.16972) ## Source-stated The authors analyze dynamic regret during skip intervals and use the resulting bound to devise an online rule for adaptive update-budget allocation. > the resulting bound answers the opening question via an online, regret-guided update rule that allocates the budget adaptively. - [Supporting source](https://arxiv.org/abs/2606.16972) ## Source-stated The abstract reports that adaptive allocation outperforms other budgeted baselines in a simulated Mars-rover task and a Crazyflie quadrotor task. > We evaluate the rule in a simulated Mars-rover navigation task with time-varying slip dynamics and on a Crazyflie quadrotor in indoor obstacle fields. Adaptive allocation outperforms other budgeted baselines. - [Supporting source](https://arxiv.org/abs/2606.16972) ## Source and contributor context Musavi, Negin, Puthumanaillam, Gokul, Hernandez, Ruben, Schafer, William, Ornik, Melkior · Article author These are credits stated by the source; they do not establish a profile match or authorship of every passage. ## Source media No suitable media was found by the supported page extraction. ## Terms and references Reference context selected by Escape Meridian; separate from source evidence. Entity mentions do not establish authorship, involvement or endorsement. ## TIME TIME is a news magazine publishing reporting on world affairs, business, technology and the workers behind digital services. - [Explore this context](/entities/time) - [Reference](https://time.com/) ## arXiv arXiv is a research manuscript repository where authors share papers that may not yet have been peer reviewed. - [Explore this context](/entities/arxiv) - [Reference](https://arxiv.org/) - [Reference](https://info.arxiv.org/help/api/index.html) ## Editorial provenance Version 1. Publication ID: 865ea2e8-41f5-4783-8d8c-779a43c871a8. Prepared by gpt-6-luna; grounding review by gpt-6-luna. Source check: uncertain by anthropic/claude-opus-5.5 on 2026-11-10T09:25:45.277Z. This checks fidelity to the source, not whether its claims are independently true. Editorial selection: accept; reasons: material\_development. Observation: faf574cfd042fad200d6b68df0cb5638029eb2bb675e9834d09d4054c5bf00cb. Source text hash: d745c5ca271416fe44972b74e5be84f78532cf1b7f80c363d544bf25b91fbdac. ### uncertain — 2026-11-10T09:25:45.277Z — anthropic/claude-opus-5.5 Publication: 865ea2e8-41f5-4783-8d8c-779a43c871a8 attribution — pass: The draft lists the same five authors shown on the arXiv page and attributes the question, analysis, update rule and evaluation results to them as their paper's claims. > Authors:Negin Musavi, Gokul Puthumanaillam, Ruben Hernandez, William Schafer, Melkior Ornik summary — uncertain: The summary is otherwise faithful and clear, but its final sentence is cut off: it ends with 'how performance changes when the assumed bound on transition drift is.\*'. The limitation it is meant to state cannot be read. Smallest repair: complete the clause, for example 'when the assumed bound on transition drift is inaccurate or unknown', or end the sentence after 'other environments'. The gloss of dynamic regret is simplified but acceptable. The title matches the source, and the question follows from the reported scope. > with a known bound on the rate of transition drift date — pass: originalPublished is 2026-06-15, which matches the v1 submission date. It is not the date of the v2 revision on 1 Nov 2026 or the feed date. > \[Submitted on 15 Jun 2026 (v1), last revised 1 Nov 2026 (this version, v2)\] support — pass: Each claim matches the abstract: the budget constraint, the skip-update scheme, the regret bound behind the online rule, and the reported outperformance in the rover and Crazyflie evaluations. The draft limits the performance claim to these evaluations and does not overstate generality. The framing of update timing as the central question is supported by the abstract. > This raises a question: \\emph{when}, along a horizon, should a robot spend its limited budget? media — pass: The selected media is the verified arXiv abstract page for this paper, which is the direct original source. ## Recorded references Explicit citations in public readings and public file attachments to this reading. Shared topics are not citations. Other artifact types need an explicit reference adapter. No public references recorded here yet. [Reference data (JSON)](/readings/4164370b304cf6fb0c075417b5d645e041248872a39f903a5c53a2b43fbaaaff/references.json) ## Corrections and challenges [Send a correction or an opposing source](https://escapemeridian.com/corrections/) [JSON record](https://escapemeridian.com/readings/when-should-a-robot-replan-regret-guided-update-scheduling-in-4164370b.json)