paper Link: https://arxiv.org/pdf/1205.2606.pdf

Exploring Compact Reinforcement-learning Representations with Linear Regression

• KWIK Linear Regression
  • KWIK (Knows What It Knows) is a framework for studying supervised learning algorithms and was designed to unify the analysis of model-based reinforcement-learning algorithms.
  • Formally, a KWIK learner operates over an input space $X$ and an output space $Y$. At every time step $t$, an input $x_t\in X$ is chosen and presented to the learner.
  • If the learner can make an accurate prediction on this input, it can predict ${\hat{y}}_t$, otherwise it must admit it does not know by returning $\perp$ (“I don’t know”), allowing it to see the true $y_t$ or a noisy version $z_t$.
    • $z_t\in \mathbb{R}$ and $y_t\in \mathbb{R}$
  • An algorithm is said to be KWIK if and only if, with high $(1-\delta )$ probability, $\Vert {\hat{y}}_t-y_t\Vert <ϵ$ and the number of $\perp$s returned over the agent’s lifetime is bounded by a polynomial function over the size of the input problem.
  • One of the first uses of the KWIK framework was in the analysis of an online linear regression algorithm used to learn linear transitions in continuous state MDPs.
    • This algorithm uses the least squares estimate of the weight vector for inputs where the output is known with high certainty.
      • Certainty is measured by two terms representing (1) the number and proximity of previous samples to the current point and (2) the appropriateness of the previous samples for making a least squares estimate.
    • When certainty is low for either measure, the algorithm reports $\perp$.
  • Some notation
    • Let $X:=\left\{\vec{x}\in {\mathbb{R}}^n\mid \Vert \vec{x}\Vert \le 1\right\}$, and let $f:X\to \mathbb{R}$ be a linear function with slope ${\theta }^{\ast }\in {\mathbb{R}}^n,\Vert {\theta }^{\ast }\Vert \le M$, i.e. $f(\vec{x}):={\vec{x}}^T{\theta }^{\ast }$.
    • Fix a timestep $t$.
    • For each $i\in \{1,\dots ,t\}$, denote the stored samples by ${\vec{x}}_i$, their (unknown) expected values by $y_i:={\vec{x}}_t^T{\theta }^{\ast }$, and their observed values by $z_i:={\vec{x}}_i^T{\theta }^{\ast }+{\eta }_i$
      • where the noise ${\eta }_i$ is assumed to form a martingale, i.e. $E\left({\eta }_i\mid {\eta }_1,\dots ,{\eta }_{i-1}\right)=0$, and bounded: $\left|{\eta }_i\right|\le S.$
    • Define the matrix $D_t:={\left[{\vec{x}}_1,{\vec{x}}_2,\dots ,{\vec{x}}_t\right]}^T\in {\mathbb{R}}^{t\times n}$ and vectors ${\vec{y}}_t:=\left[y_1;\dots ;y_t\right]\in {\mathbb{R}}^t$ and ${\vec{z}}_t:=\left[z_1;\dots ;z_t\right]\in {\mathbb{R}}^t$, and let $I$ be an $n\times n$ identity matrix.
  • Suppose that a new query $\vec{x}$ arrives. If we were able to solve the linear regression problem $D_t\theta ={\vec{z}}_t$, then we could predict $\hat{y}={\vec{x}}^T\theta$, where $\theta$ is the least-squares solution to the system.
    • However, solving this system directly is problematic because
      1. If $D_t$ is rank-deficient the least-squares solution may not be unique.
      2. Even if we have a solution, we have no information on its confidence.
    • We can avoid the first problem by regularization, i.e. by augmenting the system with Iθ = ~v, where ~v is some arbitrary vector. Regularization certainly distorts the solution, but this gives us a measure of confidence: if the distortion is large, the predictor should have low confidence and output ⊥. On the other hand, if the distortion is low, it has two important consequences. First, the choice of ~v has little effect, and second, the fluctuations caused by using ~zt instead of ~yt are also minor.

B) Related

• A Contextual-Bandit Approach to Personalized News Article Recommendation

C) References