# Soma 2018 - No-regret algorithms for online k-submodular maximization

## One-paragraph Summary

Day la paper dua `k`-submodular maximization vao online learning. Thay vi co mot objective co dinh, moi round adversary dua ra mot ham `f_t`, nguoi choi phai chon mot `k`-subpartition truoc khi biet `f_t`. Ket qua chinh noi tiep rat dep tu offline theory: online non-monotone dat no-`1 / 2`-regret, con online monotone dat no-`k / (2k - 1)`-regret, cung voi bound `O(n k sqrt(T))`. Phan ky thuat hay nhat la reduction tu online `k`-submodular maximization sang `k`-submodular selection game, roi giai selection game bang Blackwell approachability + online linear optimization.

## Setup

- Moi round `t`:
  - player chon `x_t in (k + 1)^V`;
  - adversary reveal `f_t : (k + 1)^V -> [0, 1]`;
  - player nhan reward `f_t(x_t)`.
- Vi offline problem NP-hard, performance duoc do bang `alpha`-regret thay vi regret chinh xac.

## Main Results

1. Non-monotone online:
   expected `1 / 2`-regret duoc chan boi `O(n k sqrt(T))`.
2. Monotone online:
   expected `(k / (2k - 1))`-regret cung `O(n k sqrt(T))`.
3. Theorem 3.2:
   ton tai `1`-selection algorithm cho `k`-submodular selection game voi rate `O(k sqrt(T))`.
4. Theorem 3.6:
   ghep `n` selection algorithms de thu duoc no-`1 / (alpha + 1)` regret cho full online maximization protocol.
5. Remark 3.5:
   neu dung online gradient descent ben trong, guarantee giu duoc ngay ca voi adaptive adversary.

## Core Algorithmic Idea

- Tach problem thanh `n` micro-decisions, moi decision quan ly viec gan label cho mot phan tu.
- Moi micro-decision tro thanh mot `k`-submodular selection game:
  player chi chon mot probability vector `p` tren `k` labels.
- Dinh nghia vector reward `ell(p, y)` sao cho viec approach negative orthant `R_-^k` chinh la dieu kien can de one-step inequality cua offline proof dung trong trung binh online.
- Dung Blackwell approachability theorem:
  neu negative orthant response-satisfiable, co the thiet ke no-regret selection algorithm.
- Dung duality Abernethy-Hazan de bien Blackwell thanh mot bai toan OLO, roi giai bang online gradient descent.

## Proof / Analysis Strategy

- Lemma cua offline randomized greedy cho `k`-submodularity duoc viet lai thanh mot inequality vector-valued.
- Negative orthant approachable trong Blackwell instance tuong duong ton tai selection strategy dung.
- OLO regret `O(k sqrt(T))` keo theo selection regret cung cap do.
- Tong hop `n` selection games tra lai regret `O(n k sqrt(T))` cho full online algorithm.

## Key Techniques

- approximate regret
- k-submodular selection game
- Blackwell approachability
- halfspace oracle via LP
- online gradient descent
- offline-to-online reduction

## Delicate Points / Caveats

- Paper xu ly online unconstrained case; cac rang buoc nhu cardinality / knapsack nam o line sau nay cua Spaeh-Ene-Nguyen 2025.
- Bound la polynomial-time nhung khong practical nhu greedy offline; dong gop chinh la conceptual bridge sang online learning.
- Guarantee la approximate regret, khong phai true regret, vi offline benchmark da la NP-hard approximation problem.

## Extraction To Concepts

- Khong can tao note rieng luc nay, nhung `concepts/k-submodularity.md` nen co bullet cho online / Blackwell branch.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them paper nay vao online line va nhan manh no noi tiep derandomization / randomized-greedy proof skeleton.