Technical Report Series in Neural and Computational Learning

[John Shawe-Taylor]

The European Community ESPRIT Working Group in Neural and Computational 
       Learning Theory (NeuroCOLT): two new reports available

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-001:
----------------------------------------
Worst-Case Analysis of the Bandit Problem
by  Peter Auer, Technische Universit\"{a}t Graz, Klosterwiesgasse 32/2,
       A-8010 Graz, Austria.
    Nicol\`o Cesa-Bianchi, DSI, University of Milan, Via Comelico 39,
       I-20135 Milano, Italy.

Abstract:
The multi-armed bandit is a classical problem in the area of sequential
decision theory and has been studied under a variety of statistical
assumptions. In this work we investigate the bandit problem from a
purely worst-case standpoint.  We present a randomized algorithm with
an expected total reward of $G-O(G^{4/5}K^{6/5})$ (disregarding log
factors), where $K$ is the number of arms and $G$ is the (unknown)
total reward of the best arm.  Our analysis holds with no assumptions
whatsoever on the way rewards are generated, other than being
independent of the algorithm's randomization.  Our results can also be
interpreted as a novel extension of the on-line prediction model, an
intensively studied framework in learning theory.

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-004:
----------------------------------------
Degree of Approximation Results for Feedforward Networks Approximating 
   Unknown Mappings and Their Derivatives
by Kurt Hornik, Technische Universit\"at Wien,
   Maxwell Stinchcombe, University of California, San Diego,
   Halbert White, University of California, San Diego,
   Peter Auer, Technische Universit\"at Graz  

Abstract:
Barron (1993) has given rates for hidden layer feedforward
networks with sigmoid activation functions approximating a class
of functions satisfying a certain smoothness condition.  These
rates do not depend on the dimension of the input space.  We
extend Barron's results to feedforward networks with possibly
non-sigmoid activation functions approximating mappings and their
derivatives simultaneously.  Our conditions are similar but not
identical to Barron's, but we obtain the same rates of
approximation, showing that the approximation error decreases at
rates as fast as $n^{-\frac{1}{2}}$, where $n$ is the number of
hidden units.  The dimension of the input space appears only in
the constants of our bounds.  


-----------------------
The Report NC-TR-95-001 can be accessed and printed as follows 

% ftp cscx.cs.rhbnc.ac.uk  (134.219.200.45)
Name: anonymous
password: your full email address
ftp> cd pub/neurocolt/tech_reports
ftp> binary
ftp> get nc-tr-95-001.ps.Z
ftp> bye
% zcat nc-tr-95-001.ps.Z | lpr -l

Similarly for the other technical report.

Uncompressed versions of the postscript files have also been
left for anyone not having an uncompress facility.

A full list of the currently available Technical Reports in the 
Series is held in a file `abstracts' in the same directory.

Best wishes
John Shawe-Taylor