PaperlayerView exact revision on arXiv

Source-linked AI summary

Cheap Bandits

Manjesh Kumar Hanawal, Venkatesh Saligrama, Michal Valko, R\' emi Munos

arXiv:1506.04782v2cs.LGstat.ML

TL;DR

Group-average rewards can make sensing cheaper than observing individual actions, motivating bandits that balance regret and sensing cost. The paper proposes CheapUCB for smooth graph rewards; it matches SpectralUCB’s regret order while achieving linear-in-time cost savings, and establishes a lower bound for a class of graphs.

  • Problem

    In monitoring and surveillance, observing average rewards for groups of actions can cost less than observing individual rewards, raising the question of how to learn high-reward actions while limiting sensing cost.

    Source: §1 · p. 1

  • Method

    CheapUCB models group and node observations as graph-signal arms in a linear bandit and uses reward smoothness over the graph to balance sensing cost and regret.

    Source: §1 · p. 2, §3.1 · p. 3, §5.3 · p. 6

  • Results

    CheapUCB achieves regret of the same order as SpectralUCB with sensing-cost savings linear in T, and the analysis establishes an Ω(sqrt(dT)) regret lower bound for a class of graphs.

    Source: §2 · p. 2, §7 · p. 8

  • Takeaways & Limitations

    For smooth graph rewards, group observations can reduce sensing cost while retaining state-of-the-art regret guarantees in effective dimension.

    Source: §1 · pp. 1–2, §7 · p. 8

    The reward model’s smoothness depends on penalizing spectral coefficients; neighboring-node rewards are more similar when the smoothness parameter c is small.

    Source: §3.1 · p. 3, §4 · p. 4

Abstract

from arXiv · show

We consider stochastic sequential learning problems where the learner can observe the \textit{average reward of several actions}. Such a setting is interesting in many applications involving monitoring and surveillance, where the set of the actions to observe represent some (geographical) area. The importance of this setting is that in these applications, it is actually \textit{cheaper} to observe average reward of a group of actions rather than the reward of a single action. We show that when the reward is \textit{smooth} over a given graph representing the neighboring actions, we can maximize the cumulative reward of learning while \textit{minimizing the sensing cost}. In this paper we propose CheapUCB, an algorithm that matches the regret guarantees of the known algorithms for this setting and at the same time guarantees a linear cost again over them. As a by-product of our analysis, we establish a $\Omega(\sqrt{dT})$ lower bound on the cumulative regret of spectral bandits for a class of graphs with effective dimension $d$.

1. Introduction

Cheap bandits study settings where observing the average reward of a group of actions costs less than observing a single action. The paper models actions as graph-node groups and seeks high-reward nodes while limiting sensing cost.

1. Introduction

  • The setting targets group actions that return average rewards, which can be cheaper to observe than individual-action rewards.The graph represents the geometric structure of the data, and the objective is to locate nodes with the largest rewards.Source: §1 · p. 1
  • Sensor networks and aerial reconnaissance illustrate the cost–ambiguity tradeoff: broader group sensing can reduce cost while making target identification less precise.The paper also cites social networks and recommender systems as settings where smooth graph signals arise.Source: §1 · p. 1
  • For smooth graph signals, sampling a node’s neighborhood can provide information about its reward, and the goal here is locating maxima rather than reconstructing the signal.The paper notes that smooth, band-limited rewards occur in applications including sensor networks, social networks, and recommender systems.Source: §1 · pp. 1–2
  • The paper seeks algorithms that minimize sensing cost while retaining state-of-the-art regret guarantees, using graph-signal arms that trade precise, costly node feedback against cheaper, cruder group averages.It models sequential node discovery as a linear bandit linking node rewards through an unknown parameter.Source: §1 · p. 2

2. Related Work

The paper distinguishes cheap bandits from prior cost-aware bandit settings and graph bandits. It presents CheapUCB as achieving SpectralUCB-order regret with linear-in-time cost savings, and reports a regret lower bound for a class of graphs.

2. Related Work

  • Unlike budgeted bandits, which generally minimize regret against a budget or under budget constraints, this work seeks to minimize both budget and regret over time.Other cited cost settings concern observing prediction features or switching actions.Source: §2 · p. 2
  • The paper builds on Valko et al. (2014) and distinguishes its group-action setting from graph bandits that reveal neighboring rewards or use gangs or online clustering of bandits.Source: §2 · p. 2
  • CheapUCB’s regret bound is of the same order as SpectralUCB’s, while its sensing cost is lower by a saving linear in T.The bound uses effective dimension d, which the paper says is typically smaller than the number of nodes N in real-world graphs.Source: §2 · p. 2
  • The analysis establishes an Ω(sqrt(dT)) lower bound on cumulative regret for a class of graphs with effective dimension d.Source: §2 · p. 2

3. Problem Setup

The setup treats graph-neighborhood probes as actions with different sensing costs: the learner seeks low cumulative cost while keeping regret low, balancing cheaper group observations against more precise node observations.

3. Problem Setup

  • The setup represents the action space as an undirected graph with bounded node degree and uses its Laplacian eigendecomposition.The graph has N nodes, and the Laplacian eigenvectors form the spectral basis used in the setup.Source: §3 · p. 2

3.1. Reward function

  • Node rewards are represented as linear combinations of graph eigenvectors, with the unknown parameter penalized to control reward smoothness.Large coefficients on eigenvectors with small eigenvalues yield a smooth graph signal.Source: §3.1 · p. 3

3.2. Probes

  • A probe averages rewards over its support, and the considered probes use uniform weights on neighborhoods of nodes.Probe width is the number of supported nodes.Source: §3.2 · p. 3, §3.1 · p. 3

3.3. Cost of probes

  • Probe costs are defined spectrally and are quadratic in graph Fourier coefficients; probes covering smaller sets of neighbors cost more.The paper motivates the cost design from sensor networks, where wider probes are relatively cheap.Source: §3.3 · p. 3

3.4. Learning setting and performance metrics

  • The learner minimizes total sensing cost while keeping cumulative regret low; group probes cost less but provide less precise reward information than node probes.The proposed algorithm aims to match node-action regret while reducing total sensing cost through group actions.Source: §3.4 · p. 4

4. Node Actions: Spectral Bandits

For node-only actions, SpectralUCB assumes a smooth reward function and has regret scaling with effective dimension when that dimension is small. Its cumulative sensing cost is T.

4. Node Actions: Spectral Bandits

  • SpectralUCB uses only node actions, each with cost C(e_i) = 1, and is analyzed under a smooth-reward assumption.The smoothness parameter c is small when neighboring-node rewards are more similar.Source: §4 · p. 4
  • O(d sqrt T) regret is reported for a large range of T when effective dimension d is small, while SpectralUCB incurs total cost CT = T.The regret bound applies across a large range of T when the eigenspectrum has large gaps.Source: §4 · p. 4
  • Effective dimension depends on T and the rate of eigenvalue growth; small d occurs when the eigenspectrum has large gaps.The cited section identifies large eigengaps as the condition associated with small effective dimension.Source: §4 · p. 4

5. Group Actions: Cheap Bandits

This section develops group-action learning for smooth rewards on graphs, aiming to reduce sensing cost without compromising regret. CheapUCB uses group probes and achieves SpectralUCB-order regret with a cost gain of order T.

5.1. Lower bound

  • The section establishes a worst-case cumulative-regret lower bound for any policy using action space SD on graphs with effective dimension d.The proof constructs d disjoint cliques with piecewise-constant rewards, reducing the problem to identifying the highest-reward clique.Source: §5.1 · p. 5

5.2. Local smoothness

  • Under the stated eigenvalue-gap condition, smoothness links a node’s reward to the average reward of its neighborhood, making group probes informative about the optimal node.For general graphs without that gap, the section assumes a weaker smoothness condition; the required inequalities relax as T and neighborhood width increase.Source: §5.2 · pp. 5–6

5.3. Algorithm: CheapUCB

  • CheapUCB expands the action space to include subsets of nodes and moves from less costly, wider probes to more costly, narrower probes over successive stages.Node probes provide more precise reward information but cost more than group probes.Source: §5.3 · p. 6
  • CheapUCB matches SpectralUCB’s regret performance while reducing total cost by at least T/4 + 1/2, achieving a cost reduction of order T.Source: §5.3 · p. 6

5.4. Computational complexity and scalability

  • CheapUCB’s computational and scalability requirements are essentially those of SpectralUCB, including computing the graph Laplacian eigenbasis, matrix inversions, and UCBs.Despite its larger probe sets, it computes only N UCBs; each probe can be computed in order N log N operations.Source: §5.4 · pp. 6–7

6. Experiments

Experiments compare CheapUCB with SpectralUCB and LinUCB on random graphs, stochastic block models, and forest cover data. CheapUCB’s regret is close to SpectralUCB’s while its sensing cost is lower.

6.1. Random graphs models

  • The random-graph experiments used Erdős–Rényi graphs with edge probability 0.05 and Barabási–Albert graphs with degree parameter 3, with results averaged over 100 runs.The plotted regime used N = 250, T = 150, and k = 5.Source: §6.1 · p. 7
  • On random graphs, CheapUCB’s regret is slightly worse than SpectralUCB’s but significantly better than LinUCB’s, while its cost is at least 30% lower than both.The reported comparisons are from the Erdős–Rényi and Barabási–Albert graph experiments.Source: §6.1 · p. 7

6.2. Stochastic block models

  • For the stochastic block model, CheapUCB matches SpectralUCB’s performance at significantly lower cost.The experiment used 250 nodes in four blocks, with a large gap between the fourth and fifth eigenvalues.Source: §6.2 · p. 7, Figure 2 · p. 8

6.3. Forest Cover Type data

  • The forest evaluation clustered normalized samples into 2,000 groups and defined each cluster’s reward as the fraction of its samples belonging to a given cover type.Cluster centers were connected to similar-reward neighbors using a 10-nearest-neighbors graph.Source: §6.3 · p. 8
  • For Cottonwood, CheapUCB’s cumulative regret saturates faster than LinUCB’s and is similar to SpectralUCB’s, while its total cost is 35% lower than both.Figure 2 panels (c) and (d) show Cottonwood regret and cost, respectively.Source: §6.3 · p. 8, Figure 2 · p. 8
  • Across all seven forest cover types, CheapUCB’s cumulative regret is smaller than LinUCB’s and close to SpectralUCB’s, with the same cost gain as for Cottonwood.Figure 3 shows cumulative regret for the seven cover types.Source: §6.3 · p. 8, Figure 3 · p. 8

7. Conclusion

The conclusion introduces cheap bandits to reduce sensing cost for group actions while preserving state-of-the-art regret guarantees in effective dimension. It also reports a lower bound for spectral bandits on a class of graphs.

7. Conclusion

  • CheapUCB aims to minimize group-action sensing cost while attaining state-of-the-art regret guarantees in terms of effective dimension.For stochastic rewards, the algorithm guarantees a cost gain linear in time.Source: §7 · p. 8
  • The analysis establishes an Ω(√(dT)) lower bound on cumulative regret for spectral bandits on a class of graphs with effective dimension d.Source: §7 · p. 8
  • The paper identifies contextual, combinatorial, and non-stochastic bandits with limited feedback as settings for future extensions.Source: §7 · p. 8

8. Proof of Proposition 1

The proof constructs graphs with effective dimension d and rewards that reduce the action problem to selecting among d cliques. It then uses a Gaussian reward construction to lower-bound expected regret.

8. Proof of Proposition 1

  • The proof constructs a graph from d disjoint connected subgraphs, with rewards constant within each subgraph, so the reward parameters occupy a d-dimensional space.The construction chooses subgraphs with sufficiently large first nonzero eigenvalues; cliques are given as an example.Source: §8 · p. 10
  • With piecewise-constant rewards on cliques, node and group actions within each clique are indistinguishable, reducing the problem to selecting the highest-reward clique among d arms.Source: §8 · pp. 10–11
  • The lower-bound argument adapts Auer et al. (2002) by assigning Gaussian rewards with a mean advantage ξ to one good cluster and using Gaussian KL divergence.It sets ξ = d/T and bounds the mean-reward L2 norm by c for an appropriate λ.Source: §8 · p. 11

9. Proof of Proposition 2

The proof uses graph expansion and eigenvalue relations to obtain a partition, then bounds reward variation on induced subgraphs. Its definitions specify the expansion quantities used in that argument.

Definition 2 (k-way expansion constant (Lee et al., 2012))

Definition 3 (Isoperimetric number)

10. Analysis of CheapUCB

The analysis bounds CheapUCB’s regret by breaking it into stage-wise terms and treats both high- and lower-minimum-degree graphs. For the lower-degree setting, it reports the same cumulative regret and cost bounds as in the preceding case.

10. Analysis of CheapUCB

  • Lemma 5 states that, under the condition ∥α*∥2 ≤ c, α* belongs to Ct with probability at least 1−δ for all t ≥ 0.The lemma also states a condition for any x ∈ Rn, but the supplied passage does not include its full bound.Source: §10 · p. 12

10.1. Proof of Theorem 2

  • For stages before the last, the proof expresses instantaneous regret using the selected probe’s confidence term and a stage-dependent term h(j).The proof considers probes of width J−j+1; the last stage uses width 1 and does not require inequalities (9)/(10) to bound instantaneous regret.Source: §10.1 · pp. 12–13

10.3. For the case when λd+1/λd ≥O(d2)

  • When minimum node degree is 1 < a ≤ log T, CheapUCB uses width-a signals initially, then reduces signal width by one per stage, obtaining the same cumulative regret and cost bounds.When a = 1, CheapUCB is the same as SpectralUCB, so their total cost and regret are the same.Source: §10.3 · p. 13
Loading 1506.04782v2…