PaperlayerView exact revision on arXiv

Source-linked AI summary

Average Age of Information with Hybrid ARQ under a Resource Constraint

Elif Tugce Ceran, Deniz Gunduz, Andras Gyorgy

arXiv:1710.04971v3cs.IT

TL;DR

The paper asks how to minimize long-term average AoI for status updates over error-prone channels while limiting average transmissions. It analyzes optimal ARQ and HARQ scheduling under known success probabilities and proposes average-cost reinforcement learning for unknown channels. Its numerical results show that single-bit ACK/NACK feedback with λ = 0.5 improves only slightly over ARQ, while smaller p0 decreases average AoI.

  • Problem

    The paper addresses minimizing average AoI at the destination under a source-side constraint on the average number of transmissions over an error-prone channel.

  • Method

    The paper derives scheduling policies for ARQ and HARQ, including randomized threshold policies, and uses average-cost SARSA with softmax when success probabilities are unknown.

  • Results

    Single-bit ACK/NACK feedback with λ = 0.5 improves only slightly over ARQ, while smaller p0 decreases average AoI.

  • Takeaways & Limitations

    The study characterizes resource-constrained scheduling for ARQ and HARQ and provides learning-based decisions for unknown transmission success probabilities.

Abstract

from arXiv · show

Scheduling of the transmission of status updates over an error-prone communication channel is studied in order to minimize the long-term average age of information (AoI) at the destination, under an average resource constraint at the source node, which limits the average number of transmissions. After each transmission, the source receives an instantaneous ACK/NACK feedback, and decides on the next update, without a priori knowledge on the success of the future transmissions. The optimal scheduling policy is studied under different feedback mechanisms; in particular, standard automatic repeat request (ARQ) and hybrid ARQ (HARQ) protocols are considered. Average-cost reinforcement learning algorithms are proposed when the error probabilities for the HARQ system are unknown.

I. INTRODUCTION

The paper studies scheduling status updates over error-prone channels to minimize average AoI under an average transmission constraint. It analyzes ARQ and HARQ, including optimal policies and reinforcement learning when channel success probabilities are unknown.

  • Problem: The scheduling problem balances retransmitting failed information, which can improve decoding success, against sending fresher updates with higher error probability.HARQ combines previous attempts, whereas fresh transmissions provide more up-to-date status information.
  • Problem: Average AoI is minimized under a long-term constraint limiting the transmitter’s average number of transmissions.The constraint reflects limited sensor resources such as energy supplies.
  • Protocols and policies: Both HARQ retransmissions and ARQ pre-emption are considered, and the general structure of the optimal policy is determined.Under ARQ, a failed out-of-date packet is discarded and the latest status is transmitted after NACK feedback.
  • Protocols and policies: For standard ARQ, the optimal preemptive policy is a closed-form threshold-type randomized policy.The policy decides whether to remain idle or transmit based on the scheduling state and feedback history.
  • Unknown channels: When transmission success probabilities are unknown, average-cost SARSA with softmax exploration learns scheduling decisions from ACK/NACK feedback.The algorithm balances exploration and exploitation while adapting to the communication environment.
  • Numerical results: Single-bit ACK/NACK feedback with λ = 0.5 improves only slightly over ARQ, while smaller p0 decreases average AoI.The paper also uses numerical simulations to examine feedback, resource constraints, and ARQ/HARQ effects on freshness.

A. Related Work

Prior AoI work studies queueing, multiple receivers, channel selection, and HARQ, but generally omits the joint setting of resource constraints, retransmissions, and unknown error probabilities. This paper identifies that setting as its contribution and applies average-cost reinforcement learning.

  • Earlier AoI models: Earlier AoI studies primarily use queue-based models with exogenous status-update arrivals.These models include LCFS, preemptive retransmissions, and related queueing policies.
  • Multiple receivers: Multiple-receiver work considers unreliable broadcast channels but restricts attention to work-conserving policies without update-count constraints.Those policies update information every time slot because no constraint is imposed on the number of updates.
  • Scheduling formulations: Prior studies also examine threshold scheduling over perfect channels and channel selection between free unreliable and costly reliable links.The channel-selection formulation has a Lagrangian structure similar to the standard ARQ problem considered here.
  • HARQ studies: Existing HARQ studies analyze coding choices, queueing, or zero-wait operation, but omit the resource-constrained generate-at-will setting with pre-emption.One cited model assumes MDS coding, while another has no resource constraint or pre-emption.
  • Paper gap and contribution: The paper claims the first resource-constrained HARQ status-update study and the first to combine unknown error probabilities with average-cost reinforcement learning for average AoI.It distinguishes this setting from earlier reinforcement learning work focused on learning arrival statistics without unreliable links or HARQ.

II. SYSTEM MODEL AND PROBLEM FORMULATION

The system is a slotted generate-at-will status-update process over an error-prone link with instantaneous ACK/NACK feedback. Scheduling chooses idling, a fresh update, or retransmission to minimize average AoI subject to an average transmission constraint.

  • System model: The source monitors a time-varying process and can generate a status update at any time slot.Each transmission takes one time slot, and time durations are normalized by that slot duration.
  • Feedback protocols: ACK indicates successful decoding, while NACK indicates failure; ARQ discards failed packets and sends a fresh update rather than retransmitting them.Under ARQ, the error probability remains the same across retransmissions, motivating fresh-update transmission.
  • Feedback protocols: HARQ combines received signals from previous attempts, so the error probability generally decreases with each retransmission.The error probability depends on the combining technique and channel conditions.
  • Age metric: AoI is the number of elapsed slots since the generation of the newest packet successfully decoded at the receiver.After a failure it increases by one; after successful decoding it resets to one for ARQ or retransmissions plus one for HARQ.
  • Decision process: The state is (δ_t, r_t), and each slot permits idling, transmitting a new update, or retransmitting the previously failed update.Here r_t counts previous attempts for the same packet, while δ_t is the AoI at the slot beginning.
  • Optimization problem: The CMDP minimizes average AoI while keeping the long-term average transmission cost at most C_max ∈ (0, 1].The AoI cost equals the current age, while transmission cost is zero when idle and one otherwise.

III. LAGRANGIAN RELAXATION AND THE STRUCTURE OF THE OPTIMAL POLICY

The constrained scheduling problem is relaxed with a transmission penalty and solved through average-cost MDP structure. The optimal constrained policy is stationary, randomizes in at most one state, and can be implemented by mixing two deterministic policies.

  • Lagrangian relaxation: The CMDP is rewritten as an unconstrained average-cost MDP with instantaneous cost δ_t + η·1[a_t ≠ i].The multiplier η prices each transmission while preserving AoI as the state cost.
  • Bellman formulation: The differential cost function h_η satisfies Bellman optimality equations, and Q_η combines current AoI, transmission penalty, and expected next-state differential cost.The optimal deterministic action minimizes the corresponding state-action cost.
  • Optimal-policy structure: An optimal stationary policy exists for the CMDP, is optimal for the unconstrained problem at some η = η*, and randomizes in at most one state.It can be expressed as a mixture of two deterministic η*-optimal policies that differ in at most one state.
  • Optimal-policy structure: The mixture weight is selected so that the average transmission constraint is met with equality.The resulting randomized policy remains optimal for the constrained problem.
  • Multiplier selection: As η increases, the optimal policy's average transmissions cannot increase, while its average AoI cannot decrease.The paper states C_η1 ≥ C_η2 and J_η1 ≤ J_η2 when η1 < η2.
  • Implementation: For practical implementation, the paper proposes a computationally efficient heuristic based on the general optimal-policy structure.The heuristic follows the structural results rather than replacing them with a different optimization objective.

IV. AN ITERATIVE ALGORITHM TO MINIMIZE THE AOI UNDER AN AVERAGE COST CONSTRAINT

The algorithm approximates the countably infinite constrained problem with a finite state space, solves each Lagrangian problem by RVI, and tunes the multiplier to meet the transmission constraint. Two nearby optimal policies are then mixed to satisfy the resource limit.

  • Finite-state approximation: The countably infinite state space is approximated by bounding the age and retransmission number, with convergence to the original optimal policy as bounds grow.The age is bounded by N and retransmissions by rmax; transitions leaving the constrained space are truncated.
  • Policy computation: RVI computes an approximately optimal deterministic policy for each fixed Lagrange multiplier η in the finite approximate MDP.The algorithm iterates over every bounded state-action pair until convergence.
  • Constraint enforcement: The multiplier η∗ is tuned iteratively so the resulting average transmission cost Cη approaches Cmax within a specified threshold.Each update requires running RVI to evaluate the current transmission cost.
  • Constraint enforcement: Because the relevant cost functions are piecewise constant in η, the step size must be large enough to change the average transmission cost.A fine grid of η values can be computationally demanding because every point requires an RVI run.
  • Policy mixing: Two deterministic policies computed at η∗−ξ and η∗+ξ are combined using a mixture coefficient to enforce the average transmission constraint.If policies differ in one state, randomization can occur there; otherwise, the policies are selected randomly after successful transmission.

V. AOI WITH CLASSICAL ARQ PROTOCOL UNDER AN AVERAGE COST CONSTRAINT

Under classical ARQ, the state reduces to the age because failed transmissions are discarded and retransmissions have the same success probability as new updates. This simplification yields a closed-form optimal randomized threshold policy under the average transmission constraint.

  • ARQ model: Classical ARQ reduces the state to the age and the action space to transmitting a new update or retransmitting, with fixed error probability p.Failed packets are discarded, and each retransmission is decoded as a new message.
  • ARQ optimization: The Bellman equations simplify under ARQ, enabling a closed-form characterization of the optimal policy.The action-value functions compare the expected costs of transmitting a new update and remaining with the current packet.
  • ARQ optimization: The η-optimal ARQ policy is deterministic and has a threshold structure, transmitting a new update or retransmitting according to whether age crosses ∆η.The threshold ∆η is an integer that depends on η.
  • Constrained optimum: The constrained optimum is a randomized threshold policy that mixes two neighboring thresholds to achieve the required average transmission cost.The mixture uses thresholds ∆1 and ∆2 around ∆Cmax and coefficient µ.
  • Constrained optimum: The constructed policy with mixture coefficient µ∗ is optimal for Problem 1 under the ARQ protocol.Its average transmission cost satisfies Cmax,µ∗ = Cmax.

VI. LEARNING TO MINIMIZE AOI IN AN UNKNOWN ENVIRONMENT

When HARQ error probabilities are unknown or changing, the source learns them online while minimizing average AoI under the resource constraint. The approach combines average-cost SARSA with softmax exploration and Lagrange-multiplier updates.

  • Unknown environment: The unknown-environment setting assumes the source lacks a priori information about channel error probabilities, which may also change over time.The learning algorithm therefore estimates the HARQ error function g(r) online.
  • Reported outcome: The paper states that online learning of g(r) can be performed without significantly degrading performance.
  • Learning algorithm: Average-cost SARSA with softmax recursively estimates state-action values and uses them to select actions without knowing transition probabilities.The Q-value update uses the observed next state and instantaneous cost.
  • Learning algorithm: The instantaneous Lagrangian cost is the destination AoI plus the transmission cost η · 1[an ≠ i], and it is known at the source after action selection.The source observes the next state and cost, then updates Qη using a learning rate.
  • Exploration: Softmax exploration assigns action probabilities according to estimated costs, with temperature controlling the exploration–exploitation balance.Higher temperature produces more uniform selection, while lower temperature favors the best action.
  • Constraint handling: The constrained learning procedure updates the Lagrange multiplier from empirical resource consumption to keep transmission cost close to Cmax.The policy applied at each stage is optimal for the Lagrangian MDP given observations so far.

VII. NUMERICAL RESULTS

Numerical results examine threshold policies, ARQ/HARQ performance, and learning-based scheduling under average transmission constraints. Feedback substantially reduces AoI, while HARQ gains depend on channel reliability, retransmission behavior, and the retransmission limit.

  • Policy structure: The final policies randomize between two deterministic policies selected for a target average transmission constraint.The deterministic policies are obtained using RVI and a search for η∗, then combined through a mixing coefficient.
  • Policy structure: As η increases, the resulting policy transmits less because the average cost constraint becomes more limiting.Policies with similar η∗ values and average transmission counts can nevertheless behave differently, especially for large Cmax.
  • ARQ and HARQ: Single-bit ACK/NACK feedback considerably decreases average AoI relative to periodic no-feedback transmission, even with ARQ.The no-feedback baseline periodically sends a fresh update every ⌈1/Cmax⌉ slots to satisfy the transmission constraint.
  • ARQ and HARQ: For p0 = 0.5 and λ = 0.5, HARQ improves only slightly over ARQ, while randomization forms the lower convex hull of deterministic ARQ performance.HARQ gains become more significant when error probability decreases faster with retransmissions or when more retransmissions are allowed.
  • ARQ and HARQ: HARQ performance differences across λ values are strongest when p0 is high or Cmax is low, because fewer resources remain to correct unsuccessful transmissions.For relatively reliable environments such as p0 = 0.3, performance gaps due to λ are not observable in the reported setting.
  • Reinforcement learning: Average-cost SARSA converges to the RVI performance in about 10000 iterations and remains close across Cmax values, but its variance increases when transmissions are limited.The larger variance under tighter transmission limits also limits the algorithm’s learning capability.

VIII. CONCLUSIONS

The paper addresses AoI minimization for time-sensitive updates over imperfect channels under transmission constraints. It develops ARQ/HARQ scheduling policies, identifies randomized threshold structure, and proposes reinforcement learning when channel characteristics are unknown.

  • VIII. CONCLUSIONS: The system transmits time-sensitive data over an imperfect channel and uses average AoI to quantify receiver timeliness.The optimization accounts for retransmissions and an average resource constraint.
  • VIII. CONCLUSIONS: The paper proposes preemptive scheduling policies for both classical ARQ and HARQ under an average transmission constraint.The policies explicitly account for retransmissions.
  • VIII. CONCLUSIONS: When error probabilities are known, the optimal policy has a randomized threshold structure.The policy characterization is presented for the constrained scheduling problem.
  • VIII. CONCLUSIONS: When system characteristics are unknown in advance, the paper presents an efficient reinforcement learning algorithm for practical applications.The algorithm addresses unknown error probabilities in the HARQ setting.
  • VIII. CONCLUSIONS: Numerical simulations demonstrate the effects of feedback and HARQ structure on average AoI.The methodology is also described as relevant to other systems concerned with information timeliness.

A. Verifying the assumptions of [21]

The section verifies the structural assumptions required for the constrained Markov decision process analysis. It establishes finite-state sublevel sets, recurrent-class properties, reachability, and a feasible policy with finite AoI and transmission cost.

  • A. Verifying the assumptions of [21]: The paper verifies that the relevant sublevel set G(b) is finite for every b > 0.This follows because any state (δ, r) in G(b) satisfies r < δ ≤ b.
  • A. Verifying the assumptions of [21]: A deterministic policy that always sends a new packet induces a single positive recurrent class containing (1, 0), with finite average AoI and transmission cost.The recurrent class is R = {(1, 0)} ∪ {(δ, 1): δ = 1, 2, ...}, while the remaining states are transient.
  • A. Verifying the assumptions of [21]: Every state can reach every other valid state under a constructed policy, establishing the required communication property.The construction uses idling, a new transmission, and retransmissions to steer the chain toward a target state.
  • A. Verifying the assumptions of [21]: Any positive recurrent class must contain (1, 0), so there can be only one positive recurrent class under a deterministic policy.The only way the AoI does not increase in one step is through a successful transmission returning the chain to (1, 0).
  • A. Verifying the assumptions of [21]: A feasible policy exists with Cπ = 1/(2⌈1/Cmax⌉) ≤ Cmax/2 < Cmax and finite average AoI.The policy sends a new packet when δ−1 is a multiple of 2⌈1/Cmax⌉ and idles otherwise.

B. Proof of Lemma 1

The lemma proves that transmission is monotone in the age: if an optimal policy transmits at one age, it also transmits at every larger age. The proof uses coupling and submodularity of the Q-function.

  • B. Proof of Lemma 1: If the optimal policy transmits at age δ1, it must also transmit at every age δ2 ≥ δ1.This is the monotonicity property established by the lemma.
  • B. Proof of Lemma 1: The monotonicity follows when the Q-function has a sub-modular structure, equivalently when the Q-action difference is monotone in age.The proof connects this condition to the monotonicity of the differential cost function hη(δ).
  • B. Proof of Lemma 1: The action-value difference is Qη(δ, n) − Qη(δ, i) = η + (1 − p)hη(1) − (1 − p)hη(δ + 1).This expression is used to establish the required ordering between transmitting and idling.
  • B. Proof of Lemma 1: The proof compares systems starting from two ages by coupling them under the same channel-error realization.This coupling is valid because channel states and errors are independent of ages and actions.
  • B. Proof of Lemma 1: The subsequent analysis computes steady-state age probabilities and a closed-form expected Lagrangian cost for integer threshold policies.Convexity in the threshold supports selecting an optimal integer threshold, after which the transmission cost is computed.

D. Proof of Theorem 2

The proof constructs an optimal policy under the transmission constraint by mixing two threshold policies and identifies their thresholds around the real-valued AoI minimizer. It also establishes deterministic optimal policies and supporting conditions for the unconstrained case.

  • Constrained problem: For Cπη∗ ≠ Cmax, the optimal policy is constructed as a mixture of two threshold policies that differ in at most one state.The construction uses Lagrange multipliers and deterministic threshold-policy solutions.
  • Constrained problem: The randomized policy has average transmission cost Cmax and is η∗-optimal, hence it is an optimal solution to Problem 1.The policy selects πη∗ with probability µ and π∗ otherwise before operation begins.
  • Threshold characterization: The minimizing integer thresholds are the closest integers above and below ∆Cmax, namely ∆η∗ = ∆1 = ⌊∆Cmax⌋ and ∆∗ = ∆2 = ⌈∆Cmax⌉.This follows from convexity of J∆ and the decreasing dependence of C∆ on the threshold.
  • Threshold characterization: Equivalent randomization can be performed at each visit to state (1, 0), and because the policies differ only in state δ = ∆2, randomization need occur only there.The recurrent-state construction preserves the expected AoI and transmission cost of randomization performed once at initialization.
Loading 1710.04971v3…