Lyapunov optimization

Overview

Many systems must choose an action in every time slot while random arrivals and changing channels keep moving the state. The goal is a low long-run average cost, and the queues in the system must stay stable. The shared idea is to bound the one-slot change ("drift") of a quadratic function of the queue lengths, add a weighted copy of the cost ("penalty"), and minimise that sum in each slot. The result is a per-slot problem that does not need future arrivals 2011.08430 §3.2, eq. 16, eq. 17.

The only card on wikillm that uses this technique is Deep Reinforcement Learning for Stochastic Computation Offloading in Digital Twin Networks. It applies the technique to computation offloading. The card attributes the drift-plus-penalty method to a cited prior work and does not restate it 2011.08430 §3.2. Everything below is what that card states or reports.

Variants

There is one variant on wikillm so far, so the comparison is limited.

Drift-plus-penalty with a per-device perturbation

• Queue-based Lyapunov function. The paper uses a quadratic function of the device queues, shifted by a perturbation vector beta, plus the edge queues 2011.08430 eq. 15.
• Drift, then penalty. The one-slot drift is bounded, and V times the expected energy-efficiency metric is added as the penalty. V is the weight that sets the trade-off 2011.08430 eq. 16, eq. 17, eq. 18.
• Per-slot problem. Each slot the paper minimises the resulting objective, labelled P2, over the bandwidth, power, offloaded amount and CPU share 2011.08430 eq. 20, alg. 1.
• Perturbation. The perturbation is set per device as V times a term written eta prime plus the maximum departure 2011.08430 eq. 19. Eta prime is not defined anywhere in the paper, so this variant is incomplete as written (see Caveats).

Caveats the card records, each to check before implementing:

• The energy weight cancels as written. The energy-efficiency metric is defined as energy divided by the same bit sum that appears in the bracket of the penalty. Read literally, the bracket is zero, so V has no effect 2011.08430 eq. 13, eq. 17, eq. 20, eq. 22. The paper gives no other definition.
• Eta prime is undefined, and the maximum departure depends on the action being chosen, so the perturbation is not known before the decision it should inform 2011.08430 eq. 19, alg. 1.
• Who solves the per-slot problem is not stated. The algorithm says the digital twin solves it, while the learning section says the reinforcement-learning agent finds the solution 2011.08430 alg. 1, §3.2, §4. The paper does not give a solver.
• Re-solving is the cost the method avoids. The authors say conventional per-slot solvers that alternate between sub-problems must be re-run whenever the channel or the queues change. They propose a learned policy to make the per-slot decision instead 2011.08430 §3.2, §4.1.

When to use which

Only one variant is documented, so no choice between variants can be made from wikillm content. The constraints below are what the card's setting exposes.

Implementation sketch

The core loop of the drift-plus-penalty method, as the card describes it. The perturbation and the solver are the open parts, and the comments mark them.

# One time slot of drift-plus-penalty control  [§3.2] [eq. 16]-[eq. 20]
# Input: queue state Q (device and edge queues), new arrivals A, weight V

def drift_plus_penalty_slot(Q, A, V):
    # Perturbation per queue, from the digital twin  [eq. 19]
    # Open: the term eta prime is not defined in the paper
    beta = V * eta_prime(Q) + max_departure(Q)  # eq. 19, see Caveats
    # Pick the action that minimises the per-slot objective  [eq. 20] [alg. 1]
    # Open: the paper does not say whether an optimiser or a learned policy solves it
    action = solve_per_slot(Q, A, beta, V)
    # Advance the queues with arrivals and departures  [eq. 5] [eq. 6]
    Q = update_queues(Q, A, action)
    return action, Q

Contradictions

None known. Only one card on wikillm uses this concept. The problems listed under Caveats are internal to that paper, not disagreements with another paper.

Papers

• Deep Reinforcement Learning for Stochastic Computation Offloading in Digital Twin Networks: applies Lyapunov drift-plus-penalty to per-slot offloading decisions in a digital-twin network and trains an asynchronous actor-critic agent to make them. Results are simulation plots reported by the authors.