Let it Cook: Learning to Wait in Sequential Decision Making

The paper addresses the question of whether agents in sequential decision making need to actively participate at every timestep. The authors note that tasks such as brewing coffee include periods that are served equally well by letting the environment evolve without constant monitoring and control. During such periods, the agent could simply wait to conserve its resources, or redirect its attention to another task.

The prevailing paradigm treats agents as active, closed-loop systems that continually monitor and react to their environment, but the authors argue that many real-world tasks inherently possess passive dynamics that can be exploited to achieve goals more efficiently. They give examples from a busy kitchen: a kettle takes time to boil, a soup takes time to cook, and a coffee machine operates independently once set to brew.

The authors formalize the problem using a Waiting Markov Decision Process (WMDP), defined as a tuple M=(S,A,wait,W,P,R,µ) where:

• S is the set of states (discrete or continuous)

• A is the set of primitive actions

• wait ∈ A is a distinguished wait action

• W ⊆ N+ is a finite set of waiting durations

• P is the transition probability function

• R is the reward function

• µ is the initial state distribution

A waiting macro-action of duration w ∈ W corresponds to forgoing sensing and executing the primitive wait action for w consecutive timesteps. A waiting policy π: S → ∆(A∪W) can yield either primitive actions or waiting macro-actions.

The paper defines a vector-valued objective J(π) ∈ R2 where:

• J0(π) is the expected cumulative task reward

• J1(π) is the expected cumulative waiting reward (equal to-1 times the number of times the policy is queried)

The lexicographic ordering is defined such that "[J0, J1] ≤ [J0′, J1′] ⇔ J0 < J0′ OR (J0 = J0′ AND J1 ≤ J1′). This means a policy is 'better' than another policy if and only if it either (1) achieves higher cumulative task reward J0, or (2) it achieves equal J0 and higher cumulative waiting reward J1."

The authors emphasize that this lexicographic approach renders the relative magnitudes of the task rewards and the waiting rewards inconsequential, which alleviates the need to perform a hyperparameter sweep to find an appropriate weighting of task reward vs. waiting reward.

The authors propose LQ-Learning (Algorithm 1), which adapts lexicographic Q-Learning to handle waiting macro-actions. The algorithm maintains two Q-estimates: Q0 for task reward and Q1 for waiting reward. Greedy policy inference uses a Lex-Argmax function that:

1. First identifies actions that are σ-close to optimal with respect to Q0 (where σ is a small tolerance parameter)

2. Then selects among those the action maximizing Q1

The tolerance parameter prevents a slightly inaccurate empirical Q0 estimate from erroneously ruling out the lexicographically optimal action during the Q1 update. Updates are only performed when the policy is queried, not during the primitive wait actions within a waiting macro-action.

The paper also describes how to train a waiting wrapper around an existing policy π base. This involves creating an induced two-action WMDP where a new action a base simulates π base. The wrapper policy can choose between executing π base or waiting. This approach enjoys efficient exploration because the wrapper policy has a small set of possible actions.

This is useful because in domains where large pre-trained policies exist, such as in robotic manipulation... it may be unnecessary to train a policy from scratch.

The paper evaluates on 7 environments:

1. Cook (and variants CookLonger, CookTwice): Based on Overcooked, the agent must cook and serve dishes. The soup takes 18 timesteps to cook (36 in CookLonger, and CookTwice requires two soups).

2. Coffee: A MiniGrid gridworld where the agent must toggle a coffee machine to heat (8 timesteps), then brew (18 timesteps), while also collecting cream and sugar.

3. Pong: A modified Atari Pong where the agent plays against a scripted opponent and must win one point as quickly as possible.

4. MountainCar: The agent must climb a mountain by building momentum. Even small amounts of waiting hinder task performance.

5. CartPole: The agent must balance a pole for as long as possible, with a maximum horizon of 200.

The authors find that our method yields policies that wait (in some environments, for over 50% of the task duration) without sacrificing task performance compared to a vanilla RL, non-waiting baseline.

In the Cook environment, the learned policy chooses the duration 5 wait action twice during the 33 timesteps taken to fetch ingredients, cook, and serve the soup. Interestingly, the policy does not take the duration-15 wait even though the soup takes 18 timesteps to cook, because our LQ-Learning approach discovers a policy that fetches the dish during the time the soup is cooking: this permits optimal cumulative task reward... yet precludes the opportunity to wait for 15 uninterrupted timesteps.

In Coffee, LQ-Learning learns a clever policy that achieves a higher value of Equation (1) than possible by naively waiting: the learned policy fetches sugar as the coffee brews.

The authors compare against a scalarized reward baseline that requires a hyperparameter sweep over values of λ in each new environment. They find that "under a strict preference for task performance, our lexicographic MORL approach achieves near-identical task and waiting performance to the scalarized approach, without needing a hyperparameter sweep to discover the best reward-weighting coefficient for each environment."

For Pong and CartPole, our learned waiting wrapper policies... preserve the DQN-trained base policy's perfect cumulative task reward while spending well over half of the timesteps committed to waiting.

Training a waiting wrapper is often more sample-efficient than training from scratch. For example, in Pong training a waiting wrapper policy via LDQN converges after ∼250k training environment steps, while training a waiting policy from scratch with LDQN typically takes more than 600k steps.

The authors demonstrate a simple form of policy interleaving in the Coffee task. When the waiting policy selects a duration-N wait, they check time-to-completion estimates for each not-yet-completed auxiliary task and execute the longest-duration auxiliary task that can be completed in N timesteps. This allows the agent to complete Coffee in a total of 45 timesteps, matching the amount of time taken to complete the task by vanilla Q-Learning.

The paper situates its contribution relative to several research areas:

• Cost of Agent Intervention: Prior work on event-triggered control and sensing costs

• Temporal Abstractions: Options framework and action repetition, noting that prior work focuses on reducing the amount of environmental interaction (sample complexity) needed to train a performant policy rather than minimizing deployment-time decisions

• Multi-objective RL: Lexicographic approaches allow strict prioritization of objectives, which is well-suited for our setting in which we wish to wait as much as possible without sacrificing expected cumulative task reward

The authors note limitations and future directions:

1. Their approach does not leverage the inherent structure of extended duration waiting - future work could fit single-step dynamics models to multi-timestep waiting experiences

2. They only expect our techniques to work well in fully observed environments - future work could learn memoryful waiting policies

3. The policy interleaving is only an initial proof-of-concept case study - future work needs a stringent definition of what actions cause the aspects of the environment's state that are relevant to the primary task to evolve as they would under the waiting action

The project was funded by NSF SLES 2331783, NSF CAREER 2239301, ONR N00014-22-1-2677, DARPA TIAMAT HR00112490421, and a gift from Amazon AWS to the ASSET center at Penn.

Improvement 1: Resource-Aware Autonomous Agents with Lexicographic Waiting Objectives

I can build an AI agent that explicitly optimizes for task completion while minimizing active decision-making queries. Using the WMDP framework and lexicographic Q-learning, the agent learns when to wait (forgo sensing/acting) without sacrificing task reward. This enables deployment in resource-constrained settings (e.g., battery-powered robots, cloud APIs with per-call costs) where the agent conserves energy or bandwidth by waiting during passive dynamics (e.g., a kettle boiling, a file uploading). The system automatically discovers wait durations (e.g., 5, 15 timesteps) that align with environmental dynamics, and can interleave auxiliary tasks during waits—e.g., a kitchen robot fetches a dish while soup cooks, or a server processes other jobs during a database replication delay.

Improvement 2: Sample-Efficient Wrapper Policies for Pretrained Models

I can create a lightweight waiting wrapper around any existing pretrained policy (e.g., a DQN-trained Pong agent or a robotic manipulation policy). The wrapper learns only a binary choice—execute the base policy or wait—using the induced two-action WMDP. This reduces the action space drastically, leading to convergence in 250k steps versus >600k for training from scratch. The improved system can take an off-the-shelf policy and immediately add waiting capabilities, making it ideal for retrofitting legacy AI systems with energy-saving or cost-reduction features without retraining the core policy.

Improvement 3: Hyperparameter-Free Multi-Objective Optimization via Lexicographic Ordering

I can implement a decision-making system that avoids the need for reward-weighting hyperparameter sweeps (e.g., λ in scalarized rewards). By using lexicographic ordering—maximizing task reward first, then waiting reward—the system guarantees that waiting is only increased when task performance is exactly preserved. This removes the risk of suboptimal trade-offs and eliminates manual tuning in new environments. The improved system can be deployed across diverse tasks (e.g., cooking, navigation, game-playing) with zero per-task calibration, automatically adapting its waiting behavior to each environment’s passive dynamics.

Improvement 4: Proactive Task Interleaving During Waiting Periods

I can build an agent that, upon selecting a wait action of duration N, estimates time-to-completion for pending auxiliary tasks and executes the longest one that fits within N timesteps. This enables true multitasking—e.g., in the Coffee environment, the agent fetches sugar while coffee brews, completing the task in 45 timesteps (same as non-waiting baseline) while also handling secondary objectives. The improved system can manage multiple concurrent goals (e.g., a home robot cooking dinner while doing laundry) by exploiting wait windows, increasing overall throughput without compromising primary task performance.

Improvement 5: Robust Waiting Under Model Uncertainty

I can incorporate the σ-tolerance parameter from Lex-Argmax into the Q-learning updates, making the agent robust to small errors in task-reward estimates. This prevents the system from prematurely discarding lexicographically optimal waiting actions due to noisy empirical Q-values. The improved system maintains high task performance even in stochastic environments, where waiting decisions must be made with imperfect knowledge—e.g., a delivery drone waiting for wind conditions to improve, or a trading agent pausing during market volatility, without risking suboptimal task outcomes.