Many useful robot jobs never end. Examples are keeping a counter clear, restocking a shelf, or wiping, drying and storing dishes over and over. Two features make these jobs hard to learn. The reward depends on history: a dish should be stored only after it is dried. And the reward is sparse, arriving once per completed round. The natural objective is reward per unit of time over an unbounded run, called the average reward. Algorithms that optimize it without first being told the system's mixing time (how long the robot's state distribution takes to settle into its long-run pattern) now exist. Their best-known version works by randomly choosing rollout lengths on a doubling scale, measured in raw time steps. We argue that for history-dependent recurring tasks this is the wrong clock. The task's own structure provides a better one: the number of completed rounds of the chore.
The proposal is to encode the chore as a reward machine, a small finite-state automaton whose states track which stage of the chore the robot is in. We then measure every rollout length, truncation level and averaging window in completed automaton cycles (or automaton transitions) rather than in time steps. A return to the automaton's start state marks the beginning of a new round of the chore. This gives an observable, per-policy stand-in for the unknown mixing time. It also guarantees that every gradient sample contains the rare reward events rather than only stretches of silence. The setting matters because real robot interaction is scarce. A method that needs a mixing-time oracle, a sweep over discount factors, or a reset after every round spends exactly the data a physical robot cannot afford.
Core Claim
We claim three things about continuing tasks specified by a cyclic reward machine over a physical system.
- A multi-level Monte Carlo actor-critic whose levels are indexed by completed automaton cycles gives average-reward policy gradients with lower variance at a fixed sample budget than the same estimator indexed by time steps. The gap should widen as the cycle length grows.
- Potential-based shaping computed from the automaton leaves the average reward of every policy unchanged, so it acts as a free, unbiased state-dependent baseline.
- The combination solves recurring manipulation chores where both discounted reward-machine methods and step-indexed mixing-time-free methods stall.
A second, more theoretical target is a bias bound. For linear critics, we aim to show that the bias of the cycle-indexed estimator depends on a "cycle mixing number": how many rounds it takes for the robot's configuration at the start of a round to forget where it began. The current analysis instead depends on the raw mixing time in steps.
Where This Sits
The mechanism comes from the mixing-time-free line of work. Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic introduced the Multi-Level Actor-Critic (MAC). MAC samples a rollout length from a geometric distribution over doubling levels and combines differences between successive levels so that start-up bias cancels. Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles proved global convergence for MAC with a $\sqrt{\tau_{\text{mix}}}$ dependence and no dependence on hitting times, using linear critics. It also reported that oracle-dependent methods could need $10^{14}$ samples before their first update. We reuse MAC's estimator and adaptive step sizes unchanged. Only the clock changes.
Both papers evaluate on memoryless grid worlds. Neither exploits task structure, which is where our proposal departs. Two other results constrain the design. Near-Optimal Sample Complexity for MDPs via Anchoring is parameter-free, but it requires a simulator that can be queried at arbitrary state-action pairs, which rules it out for online robot learning. Primal-Dual Stochastic Mirror Descent for MDPs warns that step sizes scaled by an assumed mixing time shrink to useless micro-steps in slowly mixing systems. That warning is why we avoid any explicit mixing-time estimate.
The task structure comes from Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. That paper defines the automaton over event labels. It adds counterfactual experience, which relabels each transition as if the automaton were in every one of its states, and automaton-based shaping. Its results are all episodic and discounted. Hierarchies of Reward Machines shows that hierarchical options over automata can explore up to 128 times more efficiently than primitive actions, but again only for episodic reach-avoid tasks. Reward Translation via Reward Machine in Semi-Alignable MDPs builds automata with a language model and transfers shaping into MuJoCo, making sparse Ant solvable. It too is discounted.
Two papers already combine average reward with automata, and they motivate us rather than compete with us. Exploration in Reward Machines with Low Regret is the closest prior work. It keeps the known automaton dynamics out of the exploration bonus and bounds regret with an automaton-restricted diameter. However, it is tabular, model-based, and needs confidence sets built from environment constants. Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards proves two things: temporal-logic objectives need memory, and they translate to limit-average rewards on automata. Its learning guarantees are only asymptotic, obtained by pushing the discount factor toward 1. Its impossibility result is our main reason to use the average-reward objective rather than a tuned discount factor.
The robotics side sets the regime. RoboCasa: Large-Scale Simulation of Household Tasks for Generalist Robots reports composite-task success "often below 12%" even with more than 100,000 synthetic trajectories. A Generalist Pair-wise Progress Critic Model for Vision-Language-Action Robots (VLAC) learns dense progress from human video. Its authors state that it assumes progress increases steadily over time and fails on cyclic tasks such as wiping, which is exactly our task class. SARM: Stage-Aware Reward Modeling for Long Horizon Robot Manipulation tracks discrete stages but needs human stage annotations. That cost is the reason we keep the automaton small and hand-written, and learn only its event detectors from little data.
Method
The agent acts in the product of the physical state and the automaton state. Let a cycle be the stretch between consecutive entries into the automaton's start state $u_0$. Suppose the physical state at each entry were independent of the past, so that cycles were exact regenerations. Then the renewal-reward theorem gives the average reward $\rho(\pi)$ of policy $\pi$ as
$$\rho(\pi) = \frac{\mathbb{E}_\pi[R_c]}{\mathbb{E}_\pi[L_c]},$$
where $R_c$ is the reward collected in one cycle and $L_c$ is its length in steps. In practice the robot's configuration at the start of a round depends on how the previous round ended, so cycles are only approximate regenerations. This is why we still need MAC's bias cancellation rather than the plain ratio.
Our estimator keeps MAC's structure. We draw a level $J$ with probability $2^{-J}$, truncated at a level set by the sample budget. We then form
$$g = g^{0} + 2^{J}\left(g^{J} - g^{J-1}\right),$$
where $g^{j}$ is the average of per-step score-function-times-advantage terms over the first $2^{j}$ completed cycles of a rollout. MAC instead averages over the first $2^{j}$ time steps.
Early in training no cycle may complete within the budget. For that case we fall back to indexing by automaton transitions, the individual stage changes. As a result the clock is always tied to observed task events, never to a guessed constant.
We add two ingredients from the reward-machine literature. First, counterfactual relabeling across automaton states feeds the critic. Second, a potential $\Phi(s,u)$ is obtained by value iteration on the automaton graph, and the shaping term $\Phi(s',u') - \Phi(s,u)$ is added to the reward. In the average-reward setting this term telescopes to zero in expectation under any policy's stationary distribution. Every policy's average reward is therefore unchanged, and the shaping shifts the differential action values only by a state-dependent amount. It acts as a baseline: it cannot bias the gradient, but it can make the critic's job easier. We will verify this invariance empirically instead of assuming it.
Event detectors come from simulator predicates in simulation. On hardware they are small classifiers trained on a few hundred labeled frames on top of a frozen video-pretrained encoder, which is the data-scarce constraint. We test how the method degrades as detector noise grows.
Research Program
The work has four parts.
The first part is theory with linear critics, following the proof in Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles. We define the cycle mixing number as the number of cycles needed for the distribution of the start-of-cycle physical state to come within a fixed total-variation distance of its stationary law. We then try to bound the estimator's bias and variance in terms of this number and the expected cycle length. The honest risk is that the bound reduces to the step-based one whenever cycle lengths vary a lot. We will state that outcome if it occurs.
The second part is controlled environments where cycle length and mixing can be dialed independently.
The third part is continuous control and simulated manipulation.
The fourth part is a small real-robot study, whose purpose is to test whether the method survives learned, noisy detectors and a fixed interaction budget.
Baselines
The naive reference is step-indexed MAC run on the physical state alone, without the automaton. We expect it to fail because the reward is non-Markovian. It shows how much of any gain comes from memory at all.
The strongest mixing-time-free competitor is step-indexed MAC (Beyond Exponentially Fast Mixing…) run on the same product space, with the same counterfactual relabeling and the same automaton shaping. This is also the ablation that isolates our key ingredient, because the only difference is the clock. On the memoryless 15×15 sparse grid world, MAC reached roughly 40% success over 100 trials while the other baselines stayed near zero (Towards Global Optimality…). We will first reproduce that figure as a sanity check.
The strongest discounted competitor is counterfactual reward-machine learning with automaton shaping, as in Reward Machines. We run it with Soft Actor-Critic in continuous domains and sweep the discount factor over {0.99, 0.995, 0.999}. The cited paper reports "an average of 9 laps per episode" on the back-and-forth HalfCheetah task, while DDPG failed even after 30 million steps. We will report the cost of the discount sweep as consumed samples.
The strongest average-reward deep baseline is Average-Reward Soft Actor-Critic on the product space. It is reported to outperform other average-reward methods on MuJoCo locomotion, but no reported result found on Lacuna for a numeric score on our tasks.
For tabular settings we compare against UCRL-RM from Exploration in Reward Machines with Low Regret, given its required constants as an oracle. No reported result found on Lacuna for its empirical regret values, so we will run it ourselves.
On manipulation, we compare against VLAC-style dense progress rewards (A Generalist Pair-wise Progress Critic…), with the policy trained by the same actor-critic. The only reported figure there is 30% rising to 90% in 200 episodes, on non-cyclic tasks.
Fairness rules apply to every method. All methods get identical samples, network sizes, event detectors and wall-clock compute. Every method gets the same tuning budget of 16 configurations, and that budget counts against its sample total. Beating a baseline means a higher long-run average reward, measured over a long evaluation run after training, with non-overlapping 95% intervals across 10 seeds.
Why not just…?
Why not just run step-indexed MAC on the product space? This is the real threat, and it is exactly the ablation above. Our argument for why it should fall short is that most of MAC's probability mass sits on short rollouts. When a reward arrives once per cycle of hundreds of steps, those short rollouts contain no reward events and contribute only critic noise. If step-indexed MAC matches us across the cycle-length sweep described below, the clock idea is not worth it. The contribution would then shrink to a demonstration that MAC combined with reward machines works on robots, and we would report it as that.
Why not just use discounted Soft Actor-Critic with automaton shaping and a large discount factor? It is simple and practical. However, Reinforcement Learning with LTL and ω-Regular Objectives… proves that no fixed discount preserves optimality for recurring temporal objectives. It also notes that effective horizons blow up as the discount approaches 1. Our experiments settle the practical side by charging the discount sweep to the sample budget. We also measure a failure the discount cannot express: leaving the workspace badly set up for the next round.
Why not just reset after each cycle and treat the task as episodic? Resets on hardware are expensive, which is the data-scarcity constraint. Resetting also hides the dependence between rounds, such as where the sponge is left for the next wipe. That dependence is precisely what the average-reward objective scores. We include an "oracle reset" episodic variant in simulation to measure how much reward this dependence is worth.
Why not just use a learned dense progress critic instead of an automaton? VLAC's own authors report failure on cyclic tasks, because rising progress and being stuck in a loop look alike to it. The VLAC baseline on our wiping and restocking tasks tests this directly.
Proposed Experiments
Controlled environments come first. We make the 15×15 sparse grid world and the RiverSwim and multi-room environments cyclic by adding an automaton that requires visiting k landmarks in order and then returning. We sweep k from 1 to 8 to lengthen the cycle at a fixed grid mixing rate. Separately, we add slippery transitions to slow mixing at a fixed cycle length.
The decisive check is a pair of predictions. As k grows at a fixed budget, cycle-indexed MAC should keep its average reward while step-indexed MAC falls toward the naive baseline. When only mixing slows, the two should degrade together. This second prediction tests whether our clock tracks task structure rather than mixing in general.
In continuous control, we make HalfCheetah laps continuing with no resets and compare laps per 1,000 steps against discounted counterfactual reward-machine learning.
In manipulation, we build RoboCasa recurring chores from its scripted task checkers used as event labels, such as open drawer, place item, close drawer, repeat. The metric is completed rounds per hour of simulated time. For context, RoboCasa's composite-task success sits below 12%.
The gain-invariance check evaluates final policies under unshaped reward. Shaped and unshaped training should converge to the same average reward, and shaping should reduce only the variance of the gradient estimates, which we measure directly.
The detector-noise sweep flips event labels at rates from 0% to 20%. It reports where each method breaks, and whether counting cycles becomes a liability when spurious cycle completions are frequent.
The small real-robot study uses a fixed budget of 200 episodes' worth of interaction on a wiping-and-stowing loop with learned detectors. It compares only our method, step-indexed MAC, and discounted counterfactual reward-machine learning, the three strongest arms.
References
- Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic
- Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles
- Near-Optimal Sample Complexity for MDPs via Anchoring
- Primal-Dual Stochastic Mirror Descent for MDPs
- Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning
- Hierarchies of Reward Machines
- Reward Translation via Reward Machine in Semi-Alignable MDPs
- Exploration in Reward Machines with Low Regret
- Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards
- RoboCasa: Large-Scale Simulation of Household Tasks for Generalist Robots
- A Generalist Pair-wise Progress Critic Model for Vision-Language-Action Robots
- SARM: Stage-Aware Reward Modeling for Long Horizon Robot Manipulation
- Average-Reward Soft Actor-Critic