Cycle Rewards and Long-Run Reward Rates

From Regenerative Cycles to Reward Rates

A regenerative process can be viewed as a sequence of cycles that restart probabilistically in the same way. If each cycle earns a random reward and takes a random amount of time, a natural candidate for the long-run reward earned per unit time is the mean reward of one cycle divided by its mean length. This tutorial defines those quantities, explains the assumptions needed for the ratio to be well-defined, and shows how the calculation works in several settings. The ratio is a candidate rate here; establishing when a time average converges to it is the subject of the renewal-reward theorem.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Consider a continuous-time regenerative process $(X_t)_{t\geq 0}$ with state space $S$, finite or countable. Write its regeneration times as $T_0=0,T_1,T_2,\ldots$, and define the cycle lengths by $C_k=T_k-T_{k-1}$ for $k\geq1$. For an ordinary regenerative process started at a regeneration, the cycles are independent and identically distributed: each cycle has the same law, and the path in a new cycle is independent of the preceding cycles. We assume $C_k>0$ almost surely. The precise regenerative structure of a model determines which times qualify as regeneration times.

Definition: The length of cycle $k$ is $C_k$. Given a measurable state reward rate $g:S\to\mathbb{R}$ and a lump-sum reward $L_k$ assigned to cycle $k$, its total reward is $$ R_k=\int_0^{C_k}g(X_{T_{k-1}+s})\,ds+L_k. $$ The cycle reward includes both reward accumulated over time and any separate reward paid at a cycle event. The candidate reward rate is $$ r=\frac{\mathbb{E}[R_1]}{\mathbb{E}[C_1]}, $$ provided $0<\mathbb{E}[C_1]<\infty$ and $\mathbb{E}[|R_1|]<\infty$.

The integrability conditions matter. The denominator must be finite and positive, and the expected reward must exist as a finite real number. For example, if $g$ is bounded and $\mathbb{E}[C_1]<\infty$, then the time-integrated part of $R_1$ is integrable. If lump-sum rewards are present, it is enough to require $\mathbb{E}[|L_1|]<\infty$. A signed reward can have cancellations within a cycle, so one must not assume that finiteness of $\mathbb{E}[R_1]$ alone makes every component of the reward integrable.

Occupation Within a Cycle

When the reward depends only on the state, it is useful to record the time spent in each state during a cycle. For $i\in S$, define $$ D_{1i}=\int_0^{C_1}\mathbf{1}_{\{X_{T_0+s}=i\}}\,ds. $$ This is the cycle's occupation time in state $i$. Since the state at almost every time in a cycle is one member of $S$, the occupation times add up to the cycle length. Countability of $S$ lets us express the integrated state reward as a sum over states.

Proposition: Suppose $S$ is finite or countable, $g$ is bounded, and $0<\mathbb{E}[C_1]<\infty$. If $\mathbb{E}[|L_1|]<\infty$, then every $D_{1i}$ is integrable and $$ \mathbb{E}[R_1]=\sum_{i\in S}g(i)\mathbb{E}[D_{1i}]+\mathbb{E}[L_1], \qquad \sum_{i\in S}\mathbb{E}[D_{1i}]=\mathbb{E}[C_1]. $$ In particular, the numbers $w_i=\mathbb{E}[D_{1i}]/\mathbb{E}[C_1]$ are nonnegative and sum to $1$, and $$ r=\sum_{i\in S}w_i g(i)+\frac{\mathbb{E}[L_1]}{\mathbb{E}[C_1]}. $$

Proof. For each $i$, $0\leq D_{1i}\leq C_1$, so $\mathbb{E}[D_{1i}]<\infty$. At each time $s$ in the cycle, exactly one indicator $\mathbf{1}_{\{X_{T_0+s}=i\}}$ is $1$; hence $\sum_{i\in S}D_{1i}=C_1$ pathwise. Taking expectations of the increasing finite partial sums gives $\sum_i\mathbb{E}[D_{1i}]=\mathbb{E}[C_1]$. Also, with $M=\sup_{i\in S}|g(i)|<\infty$, the absolute sum of the integrated rewards is bounded by $M C_1$. It is therefore integrable, so expectation and the countable sum can be interchanged. On each cycle, the time-integrated reward is $\sum_i g(i)D_{1i}$; adding $L_1$ and taking expectations proves the first identity. Dividing the occupation identity by the positive finite $\mathbb{E}[C_1]$ shows that the $w_i$ are nonnegative and sum to $1$. Dividing the reward identity by $\mathbb{E}[C_1]$ gives the displayed formula for $r$. $\square$

The weights $w_i$ are expected fractions of a cycle spent in each state. Thus, with no lump-sum reward, the candidate rate is a weighted average of the state reward rates, with weights determined by cycle occupation—not by how many times the process visits each state.

Why This Ratio Is the Natural Candidate

The ratio can be characterized without claiming a time-average limit. It is the unique real number $a$ for which the expected excess reward $R_1-aC_1$ of a cycle is zero. This centering property also gives an exact check using any fixed number of complete cycles.

Proposition: If $(C_k,R_k)_{k\geq1}$ are independent, identically distributed cycle length-reward pairs with $0<\mathbb{E}[C_1]<\infty$ and $\mathbb{E}[|R_1|]<\infty$, then $r=\mathbb{E}[R_1]/\mathbb{E}[C_1]$ is the unique real number satisfying $\mathbb{E}[R_1-rC_1]=0$. For every positive integer $m$, the ratio of the expected total reward in $m$ complete cycles to the expected total duration of those cycles is also $r$.

Proof. The assumptions make both expectations in $\mathbb{E}[R_1-aC_1]$ finite for every real $a$. Linearity gives $\mathbb{E}[R_1-aC_1]=\mathbb{E}[R_1]-a\mathbb{E}[C_1]$. Since $\mathbb{E}[C_1]>0$, this expression is zero exactly when $a=\mathbb{E}[R_1]/\mathbb{E}[C_1]$, proving existence and uniqueness. For $m$ cycles, linearity of expectation gives $\mathbb{E}[\sum_{k=1}^m R_k]=m\mathbb{E}[R_1]$ and $\mathbb{E}[\sum_{k=1}^m C_k]=m\mathbb{E}[C_1]$. Their ratio is $r$. This is a ratio of expectations for a fixed number of cycles; it is not, by itself, a proof that a reward divided by elapsed time converges along a sample path. $\square$

Worked Cycle Calculations

Worked Example: Alternating On and Off Periods

A device alternates deterministically between state $U$ (on) for $2$ time units and state $D$ (off) for $1$ time unit. A cycle starts when the device enters $U$. Let the reward rate be $g(U)=1$, $g(D)=0$, and let there be no lump-sum reward. Find the candidate reward rate.

The cycle length is $C_1=2+1=3$. The cycle spends $D_{1U}=2$ time units on and $D_{1D}=1$ time unit off. The reward is $$ R_1=2\cdot 1+1\cdot 0=2. $$ Since these cycles are deterministic, $\mathbb{E}[C_1]=3$ and $\mathbb{E}[R_1]=2$, so $r=2/3$.

Check: The occupation weights are $w_U=2/3$ and $w_D=1/3$; they are nonnegative and sum to $2/3+1/3=1$. The state-reward formula gives $w_Ug(U)+w_Dg(D)=(2/3)\cdot1+(1/3)\cdot0=2/3$, agreeing with the cycle-reward calculation.

Worked Example: Exponential Operating Time and Fixed Repair

A machine starts each cycle newly repaired. Its operating lifetime $U$ is exponential with rate $2$, after which repair takes exactly $1/2$ time unit. The next cycle begins when repair is complete. Let $X_t$ record whether the machine is operating or under repair, with state space $S=\{\mathrm{up},\mathrm{down}\}$. The reward rate is $1$ when up and $0$ when down. Find the candidate fraction of time rewarded per unit time.

The cycle length is $C_1=U+1/2$. For an exponential random variable with rate $2$, $\mathbb{P}(U>t)=e^{-2t}$ for $t\geq0$, so $$ \mathbb{E}[U]=\int_0^\infty \mathbb{P}(U>t)\,dt =\int_0^\infty e^{-2t}\,dt=\frac12. $$ The reward in a cycle is its operating time, $R_1=U$. Therefore $\mathbb{E}[C_1]=1/2+1/2=1$ and $\mathbb{E}[R_1]=1/2$, giving $r=1/2$.

Check: Expected down time in a cycle is $1/2$; expected up time is $1/2$. Their sum is $1$, the expected cycle length. The occupation formula therefore gives the up-state weight $w_{\mathrm{up}}=(1/2)/1=1/2$ and the down-state weight $w_{\mathrm{down}}=(1/2)/1=1/2$. With rewards $1$ and $0$, respectively, the rate is $1\cdot1/2+0\cdot1/2=1/2$, as before.

Worked Example: Random Cycle Types

At the start of each cycle, an independent fair choice selects one of two cycle types. Type A has length $1$ and reward $2$; type B has length $3$ and reward $0$. The types are independently selected from cycle to cycle. Find the candidate reward rate, and compare it with the average of the two type-specific reward-to-length ratios.

Each type has probability $1/2$, so $$ \mathbb{E}[C_1]=\frac12\cdot1+\frac12\cdot3=2, \qquad \mathbb{E}[R_1]=\frac12\cdot2+\frac12\cdot0=1. $$ Thus the candidate rate is $r=1/2$. The type-specific ratios are $2/1=2$ for type A and $0/3=0$ for type B; their unweighted average is $(2+0)/2=1$, not $1/2$.

Check: For one cycle, expected reward is $1$ and expected duration is $2$, so their ratio is $1/2$. Over $m$ cycles, expected total reward is $m\cdot1=m$ and expected total duration is $m\cdot2=2m$; their ratio is $m/(2m)=1/2$ for every positive integer $m$. The longer, zero-reward type contributes more expected time, which is why averaging the type-specific rates equally gives the wrong value.

Conditions, Scope, and Common Pitfalls

The ratio is a useful candidate only when the expectations are well-defined and the cycle length has a positive finite mean. If $\mathbb{E}[C_1]=0$, division by the mean length is impossible; if $\mathbb{E}[C_1]=\infty$, the finite-mean rate formula does not apply. Likewise, if rewards are signed, it is important to control absolute integrability rather than rely on cancellation. For bounded $g$, finite $\mathbb{E}[C_1]$ guarantees integrability of the time reward, but it does not by itself guarantee integrability of a separate lump-sum reward.

A concrete failure of the careless cancellation argument is a cycle of almost surely finite length $C_1$ with infinite mean, split into two equal halves. Set $g(A)=1$ on the first half and $g(B)=-1$ on the second, and let $L_1=0$. The total cycle reward is $R_1=0$ on every sample path. But the occupation times are $D_{1A}=D_{1B}=C_1/2$, each with infinite expectation. Writing the reward expectation as $\mathbb{E}[D_{1A}]-\mathbb{E}[D_{1B}]=\infty-\infty$ is invalid, even though the pathwise total reward is zero. The proposition avoids this problem by requiring $\mathbb{E}[C_1]<\infty$, which makes each occupation time integrable.

Common mistake. Do not replace the ratio of expected reward to expected length by the average of cycle-specific ratios. In the random-type example, that incorrect calculation is $\frac12(2/1)+\frac12(0/3)=1$. The correct calculation uses the same cycle distribution for both expectations: $\mathbb{E}[R_1]/\mathbb{E}[C_1]=1/2$. Cycle types with longer durations contribute more elapsed time, even though each cycle is selected with equal probability.

Finally, the ratio concerns expected reward and expected duration per cycle. A separate limit theorem is needed to conclude that the realized reward divided by realized elapsed time approaches this value. The assumptions for such a limit, and the proof of that convergence, should not be inferred merely from the cycle-ratio calculation.

Check Your Understanding

For each question, identify the cycle quantity being used and check the relevant assumptions.

A regenerative cycle has expected length $4$ and expected reward $6$. What is its candidate reward rate, and what integrability condition must hold for that ratio to be meaningful?
In a cycle, the process spends expected times $3$ and $1$ in states $a$ and $b$. If $g(a)=2$, $g(b)=-1$, and there is no lump-sum reward, compute the candidate rate.
Why does finite $\mathbb{E}[C_1]$ make each occupation time $D_{1i}$ integrable?
Two equally likely cycle types have length-reward pairs $(1,4)$ and $(5,0)$. Compute the ratio of expected reward to expected length, then compute the unweighted average of the two type-specific rates. Explain why they differ.
Does the identity $\mathbb{E}[\sum_{k=1}^mR_k]/\mathbb{E}[\sum_{k=1}^mC_k]=r$ by itself prove almost-sure convergence of reward per unit time? Explain.