---
kind: concept
slug: lyapunov-optimization
title: Lyapunov optimization
summary: >-
  Lyapunov drift-plus-penalty turns a long-run cost minimisation under queue stability into one decision per time slot. Each slot minimises a weighted penalty plus the drift of a queue-based Lyapunov function. The weight trades cost against queue growth. One source so far, a reinforcement-learning offloading paper, with author-reported simulation results only and several undefined terms.
tags: [optimization, queueing, stochastic-control, edge-computing]
papers: ["2011.08430"]
related: [computation-offloading, policy-gradient]
status: draft
updated_at: 2026-10-18
---

## 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 [arxiv: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](/papers/2011.08430). It applies the technique to [computation offloading](/concepts/computation-offloading). The card attributes the drift-plus-penalty method to a cited prior work and does not restate it [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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.

| Situation | Use | Why |
|---|---|---|
| Queues must stay stable under random arrivals, and the cost is a long-run average | Drift-plus-penalty, with V as the cost-versus-queue weight | The per-slot problem is what the method yields. Queue stability is the stated constraint [arxiv:2011.08430 §2.2, eq. 7] |
| You need the per-slot decision fast, and the channel changes often | A learned policy trained to output the per-slot decision | The authors report this avoids re-solving per slot. The reported gain is from simulation only [arxiv:2011.08430 §3.2, §5] |
| You need a value of V or the perturbation to implement | Not known from this wiki | The card leaves V and eta prime unspecified [arxiv:2011.08430 §5, eq. 17, eq. 19] |

## 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.

```pseudocode
# 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](/papers/2011.08430): 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.