Learning with Good Feature Representations in Bandits and in RL with a Generative Model

Tor Lattimore; Csaba Szepesvari; Gellert Weisz

Source-linked AI summary

Learning with Good Feature Representations in Bandits and in RL with a Generative Model

Tor Lattimore, Csaba Szepesvari, Gellert Weisz

arXiv:1911.07676v2Nov 18, 2019stat.MLcs.LG

TL;DR

The paper asks whether good linear features suffice for efficient learning when rewards or value functions are only approximately represented. Using Kiefer-Wolfowitz-based designs, it proves positive guarantees alongside worst-case lower bounds, with approximation-error blowup depending on feature dimension and, in RL, the discount factor.

Problem
The paper studies whether good linear feature representations are sufficient for efficient learning in bandits and reinforcement learning when approximation error is ε.
Method
The paper combines a negative construction using nearly orthogonal feature rows with Kiefer-Wolfowitz and least-squares methods for selecting informative actions.
Results
The paper obtains positive guarantees with approximation-error blowup O(ε√d), while also proving feature matrices for which near-optimal identification requires complexity as high as k.
Takeaways & Limitations
Good features are useful when the ε√d error blowup is acceptable; in discounted RL, the corresponding factor also includes 1/(1 − γ)^2.
Takeaways & Limitations
The misspecified contextual linear-bandit modification requires knowledge of the approximation error, and finding a comparable algorithm without that knowledge remains open.

Abstract

from arXiv · show

The construction by Du et al. (2019) implies that even if a learner is given linear features in $\mathbb R^d$ that approximate the rewards in a bandit with a uniform error of $ε$, then searching for an action that is optimal up to $O(ε)$ requires examining essentially all actions. We use the Kiefer-Wolfowitz theorem to prove a positive result that by checking only a few actions, a learner can always find an action that is suboptimal with an error of at most $O(ε\sqrt{d})$. Thus, features are useful when the approximation error is small relative to the dimensionality of the features. The idea is applied to stochastic bandits and reinforcement learning with a generative model where the learner has access to $d$-dimensional linear features that approximate the action-value functions for all policies to an accuracy of $ε$. For linear bandits, we prove a bound on the regret of order $\sqrt{dn \log(k)} + εn \sqrt{d} \log(n)$ with $k$ the number of actions and $n$ the horizon. For RL we show that approximate policy iteration can learn a policy that is optimal up to an additive error of order $ε\sqrt{d}/(1 - γ)^2$ and using $d/(ε^2(1 - γ)^4)$ samples from a generative model. These bounds are independent of the finer details of the features. We also investigate how the structure of the feature set impacts the tradeoff between sample complexity and estimation error.

1. Introduction

The paper asks whether good linear feature representations suffice for efficient learning in bandits and reinforcement learning, and develops positive and negative results around this question.

Motivation: Du et al. (2019) suggest that good feature representations are insufficient for efficient reinforcement learning and finite-armed bandits with misspecified linear models.Efficiency concerns learning a good policy with few environment interactions or simulator samples.
Motivation: A good linear feature representation uniformly approximates the value functions of all policies with small error.The same representation question applies to bandit learning.
Roadmap: The paper studies near-optimal action identification with side information about possible rewards, including negative and positive query-complexity results.The analysis begins with an abstract noiseless problem before applying the ideas to stochastic bandits and reinforcement learning with a generative model.

2. Problem setup

The setup formalizes noiseless identification of a near-optimal action under a known hypothesis class, while distinguishing action quality from full reward-vector estimation.

Abstract problem: A learner queries noiseless rewards from k actions and must eventually output an estimated optimal action and an estimation vector.Repeated queries are unnecessary, although the learner may randomize.
Abstract problem: An action is δ-optimal when its reward exceeds the maximum reward by less than δ below the optimum.The learner’s action-quality objective and reward-estimation objective are treated separately.
Soundness criteria: A learner is sound when its estimated reward vector has infinity-norm error below δ for every hypothesis in H.Max-soundness instead requires only that the output action be within δ of the best action.
Complexity measures: The minimax query complexities measure expected queries for max-sound and sound learners over reward vectors in the hypothesis class.Both complexities increase when the hypothesis class becomes larger.
Soundness criteria: A sound learner whose output action maximizes its estimate is also max-sound with tolerance 2δ.This links full reward estimation to near-optimal action identification.
Complexity measures: The section’s primary focus is the max-sound query complexity.The supplied passages introduce this focus without giving its complete formal expression.

3. Negative result

The negative result shows that some high-dimensional feature matrices cannot support efficient O(ε)-optimal action identification, even when rewards are uniformly close to the feature span.

Misspecified model: The hypothesis class consists of rewards within an ε-vicinity of range(Φ) in max-norm, represented as range(Φ) + B∞(ε).Here B∞(ε) is the k-dimensional hypercube [−ε, ε]^k.
Query lower bound: When δ is smaller than the ε√d scale, some feature matrices require query complexity as high as k.Thus, near-optimal action identification may require examining essentially all actions.
Proof construction: The construction embeds each standard basis vector within ε in max-norm of the feature span, enabling the lower-bound argument.Choosing θ as a feature row makes one component equal to one while the others remain below ε in absolute value.
Scope: The negative result is worst-case: the zero feature matrix has zero max-sound query complexity when ε < 1.A hard matrix can nevertheless arise with non-negligible probability from uniformly sampled spherical rows.
Rescaling: For all δ > ε and sufficiently large k, another feature-matrix construction yields the stated rescaled lower bound.The proof follows by rescaling the features in Proposition 3.2.

4. Positive result

The positive result uses optimal experimental designs from the Kiefer–Wolfowitz theorem to identify near-optimal actions from a small core set, trading query complexity against estimation error.

Positive result: δ = Ω(ε√d) yields query complexity independent of the number of actions k and roughly linear in feature dimension d.This complements the negative result, which is exponential in d when δ is not much larger than ε.
Positive result: The method assumes Φ has unique rows whose span is all of R^d, then evaluates rewards on the support of a suitable distribution over feature rows.The resulting least-squares estimator predicts the action maximizing the estimated reward.
Optimal design: The Kiefer–Wolfowitz theorem equates minimizing worst-case variance with maximizing log det G(ρ), and guarantees an optimal design with a small support.The support is called the core set and lies on the boundary of a minimum-volume central ellipsoid containing the feature rows.
Error guarantee: The resulting estimation error is bounded by the approximation error plus an additional term determined by the design and any perturbation magnitude β.When an additive perturbation η is present, the bound incurs an additional dependence on β.
Feature-dependent tradeoff: The tradeoff is sharp: demanding error close to ε can require many queries, whereas accepting a factor of √d in estimation error makes query complexity practically linear in d.For feature-dependent query budgets, Proposition 4.6 characterizes the tradeoff through λ_q(Φ), with δ1 = ε(1+λ_q(Φ)) and δ2 > ε(1+2λ_q(Φ)).
Comparison to supervised learning: Unlike supervised learning, the bandit objective evaluates the worst-case action error, so its approximation-error dependence includes a factor of d.In supervised learning, actions are sampled from a distribution and the cited comparison has no d multiplying the approximation-error dependence.

5. Misspecified linear bandits

The section develops phased elimination for stochastic bandits with nearly linear mean rewards, using experimental designs to estimate and eliminate actions. It establishes regret guarantees, discusses tightness and extensions, and identifies limitations for contextual settings.

Model: The bandit model assumes mean rewards are nearly linear in distinct action features.The misspecification is represented as µ = Φθ + ∆ with ||∆||∞ ≤ ε.
Algorithm: The algorithm computes a near-optimal design over plausibly optimal actions, samples proportionally to that design, and eliminates sufficiently suboptimal arms.The design-based sampling supports least-squares estimation within each episode.
Results: Proposition 5.1 gives an expected regret bound with estimation and misspecification terms, including a logarithmic factor in the second term.The logarithmic factor arises because episodes may eliminate the best remaining arm while retaining one at most O(ε√d) worse.
Results: The regret bound is tight up to logarithmic factors when the number of arms is comparable to the horizon.For very large action sets, covering arguments can yield a bound independent of the number of arms.
Algorithm: O(d log log d) well-chosen actions suffice for the underlying design-based reward investigation.The implementation uses m = ⌈4d log log d⌉ + 16 and a design support bounded by 4d log log(d) + 16.
Limitations: Contextual adaptations remain limited because the supplied modification requires knowledge of the approximation error, leaving an open algorithmic question.The paper reports a negative result for standard LinUCB-style behavior in the contextual setting and proposes a data-dependent correction.

6. Reinforcement learning

The section applies design-based estimation and approximate policy iteration to discounted reinforcement learning with a generative model. Sampling only core state-action pairs yields a nearly optimal policy under uniformly approximate linear features.

Setting: The learner can sample next-states and rewards for any chosen state-action pair in a discounted finite-state MDP.The setting uses discount factor γ ∈ (0, 1) and bounded rewards.
Setting: The feature matrix approximates Qπ uniformly for all policies, with state-action features in R^d.The approximation assumption applies to vectorised action-value functions.
Method: Approximate policy iteration estimates Qπk on a design core set using roll-outs, extends the estimate with features and least squares, then takes a greedy policy.The procedure repeats this process across policy-iteration steps.
Results: The total number of generative-model samples is independent of the state-space and action-space sizes.The sample count is expressed as kmn|C| when the design support is the core set C.
Analysis: The policy-iteration analysis combines error propagation with a greedy-policy value bound to control the final suboptimality.The resulting norm bound includes both estimation error and a term decreasing with the number of iterations.

7. Conclusions

The conclusions state that good representations support efficient learning only when accepting a dimension-dependent approximation-error blowup. They separate query complexity from value estimation and identify unresolved computational and scope limitations.

Main conclusion: Features are useful if and only if an O(√d) approximation-error blowup is acceptable.The conclusion contrasts this with supervised learning, where the blowup does not appear.
Main conclusion: Discounted reinforcement learning incurs an additional factor of 1/(1 − γ)^2 in the approximation-error blowup.The authors state that this factor is believed not to be improvable.
Interpretation: The analysis separates identifying a near-optimal action from estimating an action or policy value using roll-outs.The authors suggest this decomposition may help analyze more nonlinear reward-function classes.
Open questions: Computing an approximate optimal design requires the algorithm to examine all features.This is listed as an open question concerning the method’s computational requirements.
Open questions: The reinforcement-learning argument relies heavily on uniform contraction, and its extension to finite-horizon or average-cost settings remains unresolved.The online regret setting is also identified as an open question.

A. Proof of Lemma 2.2

The proof establishes the query complexity of identifying a near-optimal action in a noiseless coordinate problem. A random query order achieves the lower-bound expectation, while Yao’s principle proves no deterministic strategy can do better on average.

Conclusion: Averaging these positions gives expected query complexity (k + 1)/2.Thus the random-order upper bound matches the lower bound.
Upper bound: A random query order stops after finding a nonzero reward and has expected query count (k + 1)/2.The algorithm then knows the reward vector and an optimal action.
Lower bound: Yao’s principle reduces the lower bound to a uniform distribution over coordinate-vector instances.The proof analyzes deterministic algorithms under this distribution.
Lower bound: Any nondominated deterministic algorithm queries each coordinate at most once and stops immediately after observing a nonzero answer.Its query count on instance ei equals the position of i in its fixed permutation.

B. Proof of Corollary 3.3

The proof constructs a feature matrix whose rows are unit vectors with small pairwise inner products, yet approximate many distinct reward vectors within ε.

The feature matrix Φ′ has unit-norm rows with pairwise inner products at most ε/δ.This near-orthogonality enables many actions to remain difficult to distinguish from the available features.
Each basis reward vector δe_i lies within ε of the feature-induced hypothesis class H_ε.
The proof then applies the resulting construction to establish the stated lower-bound quantity, which is at least (k + 1)/2.

C. Proof of Proposition 4.6

The proposition is established with matching upper- and lower-bound arguments. Algorithm 2 estimates rewards from a queried core set, while soundness forces sufficiently many queries in the worst case.

Upper bound: Algorithm 2 probes μ on C, fits θ̂ with ||Φ_C θ̂ − μ_C||∞ ≤ ε, and returns μ̂ = Φθ̂.The procedure uses observations on C followed by a constrained least-squares-style approximation.
Upper bound: Because μ ∈ Hε_Φ, it can be represented as Φθ + Δ with Δ ∈ B∞(ε), enabling the upper-bound analysis.
Lower bound: The lower bound considers any sound algorithm and constructs a reward vector for which halting after at most q queries leads to a contradiction.The argument examines rewards consistent with the observations made on the queried action set.
Lower bound: Soundness therefore implies that an algorithm must query more than q actions whenever it halts with non-zero probability in the constructed instance.The contradiction uses the symmetry of the plausible reward set, including that ν implies −ν is also plausible.

D. Details for proof of Proposition 5.1

The section develops proof details for the bandit results, including episode-wise elimination, contextual-bandit modifications, lower bounds, and computational costs. It also identifies limitations involving unknown approximation error and state-space-dependent computation.

In-episode behaviour: The elimination rule may discard the optimal action, but it retains at least one action whose reward is nearly optimal.The proof combines the non-elimination of the empirically best action with the elimination condition to show that substantially worse arms are removed.
Combining episodes: With probability at least 1−kαL, the good events hold across all episodes, allowing episode-wise suboptimality and regret bounds to be combined.The analysis defines δℓ as the best-arm suboptimality at the start of episode ℓ and uses geometrically increasing sample sizes mℓ.
Combining episodes: The regret contribution from failed confidence intervals is at most L ≤ log2(n), making it negligible relative to the principal regret term.
Contextual bandits: The modified contextual algorithm uses an additional optimism-inducing bonus, and its regret satisfies the bound stated in Theorem E.1.The proof sketch applies the standard regret calculation after establishing optimism.
Limitations and computation: A similar bound is not known when ε is unknown, and RL computation remains state-space dependent despite state-space-independent sample complexity.Near-optimal-design computation is the main computational bottleneck, with the bandit algorithm requiring O(kd^2 log log(d) log(n) + nd^2) computation.
Contextual bandits: For contextual bandits, the unmodified elimination algorithm can choose the same action for all later rounds and incur regret at least n/2.The failure arises in an instance where the feature matrix changes across rounds; a modified LinUCB algorithm is proposed when ε is known.