Relative Loss Bounds for Temporal-Difference Learning
Machine LearningPublished 21 March 2003
Jürgen Forster, Manfred K. Warmuth
Citations6
SJR quartileQ1
SJR score1.15
SNIP2.14
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Foster and Vovk proved relative loss bounds for linear regression where the total loss of the on-line algorithm minus the total loss of the best linear predictor (chosen in hindsight) grows logarithmically with the number of trials. We give similar bounds for temporal-difference learning. Learning takes place in a sequence of trials where the learner tries to predict discounted sums of future reinforcement signals. The quality of the predictions is measured with the square loss and we bound the total loss of the on-line algorithm minus the total loss of the best linear predictor for the whole sequence of trials. Again the difference of the losses is logarithmic in the number of trials. The bounds hold for an arbitrary (worst-case) sequence of examples. We also give a bound on the expected difference for the case when the instances are chosen from an unknown distribution. For linear regression a corresponding lower bound shows that this expected bound cannot be improved substantially.
Keywords
Computer ScienceDecision Sciences
MIT Press eBooksIntroduction to Reinforcement Learning
6,868 Citations1998Richard S. Sutton, Andrew G. Barto
In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning.
Adaptive Signal Processing
5,121 Citations1991
This volume discusses three recently developed general methodologies for designing signal predictors under nonclassical operating conditions, namely the robust predictor, the high-speed Levinson modeling, and the approximate conditional mean nonlinear predictor.
Machine LearningLearning to Predict by the Methods of Temporal Differences
3,894 Citations1988Richard S. Sutton
This article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior, and proves their convergence and optimality for special cases and relate them to supervised-learning methods.
IEEE Computational Science and EngineeringAn introduction to wavelets
1,732 Citations1995A. L. Graps
The mathematics have been worked out in excruciating detail, and wavelet theory is now in the refinement stage, which involves generalizing and extending wavelets, such as in extending wavelet packet techniques.
Information and ComputationExponentiated Gradient versus Gradient Descent for Linear Predictors
880 Citations1997Jyrki Kivinen, Manfred K. Warmuth
The bounds suggest that the losses of the algorithms are in general incomparable, but EG(+/-) has a much smaller loss if only a few components of the input are relevant for the predictions, which is quite tight already on simple artificial data.
ePrints Soton (University of Southampton)Ridge Regression Learning Algorithm in Dual Variables
802 Citations1998Craig Saunders, Alex Gammerman +1 more
A regression estimation algorithm which is a combination of the dual version of Ridge Regression is applied to the ANOVA enhancement of the infinitenode splines and the use of kernel functions, as used in Support Vector methods is introduced.
Machine LearningLinear Least-Squares algorithms for temporal difference learning
639 Citations1996Steven J. Bradtke, Andrew G. Barto
Two new temporal diffence algorithms based on the theory of linear least-squares function approximation, LS TD and RLS TD, are introduced and prove probability-one convergence when it is used with a function approximator linear in the adjustable parameters.
Machine LearningRelative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions
292 Citations2001Katy S. Azoury, Manfred K. Warmuth
This work considers on-line density estimation with a parameterized density from the exponential family and uses a Bregman divergence to derive and analyze each algorithm to design algorithms with the best possible relative loss bounds.
Survey of Applicable Mathematics
276 Citations1994Karel Rektorys
Least-Squares Temporal Difference Learning
260 Citations1999Justin A. Boyan
This paper presents a simpler derivation of the LSTD algorithm, which generalizes from = 0 to arbitrary values of ; at the extreme of = 1, the resulting algorithm is shown to be a practical formulation of supervised linear regression.
Additive versus exponentiated gradient updates for linear prediction
226 Citations1995Jyrki Kivinen, Manfred K. Warmuth
The main methodological idea is using a distance function between weight vectors both in motivating the algorithms and as a potential function in an amortized analysis that leads to worst-case loss bounds.
IEEE Transactions on Neural NetworksWorst-case quadratic loss bounds for prediction using linear functions and gradient descent
150 Citations1996Nicolò Cesa‐Bianchi, Philip M. Long +1 more
This work studies the performance of gradient descent when applied to the problem of online linear prediction in arbitrary inner product spaces and proves worst-case bounds on the sum of the squared prediction errors under various assumptions concerning the amount of a priori information about the sequence to predict.
Neural Information Processing SystemsCompetitive On-line Linear Regression
58 Citations1997Vladimir Vovk
It is shown that the Aggregating Algorithm attains the optimal constant in the authors' bound, whereas the constant attained by the ridge regression procedure in general can be 4 times worse.
Lecture notes in computer scienceOn relative loss bounds in generalized linear regression
41 Citations1999Jürgen Forster
This paper reconsiders a result by Vovk, namely an upper bound on the on-line relative loss for linear regression with square loss - here the experts are linear functions, and gives a shorter and simpler proof of this result.
Machine LearningOn the worst-case analysis of temporal-difference learning algorithms
35 Citations1996Robert E. Schapire, Manfred K. Warmuth
Lower bounds on the performance of any algorithm for this learning problem are proved, and a similar analysis of the closely related problem of learning to predict in a model in which the learner must produce predictions for a whole batch of observations before receiving reinforcement is given.
Tracking the best regressor
33 Citations1998Mark Herbster, Manfred K. Warmuth
This paper develops the methodology for lifting known static bounds to the shifting case and obtains bounds when the comparison class consists of linear neurons (linear combinations of experts).