Exploring compact reinforcement-learning representations with linear regression

1 Introduction

• Earlier online regression approaches often lacked guarantees for the resulting agent or required strict assumptions, and model learning had focused on linear dynamics.The RL setting is non-i.i.d., and identifying which parts of a model need exploration is crucial to optimizing reward.Source: §1 · p. 1
• KWIK linear regression improves the sample and computational bounds of its predecessor and supports polynomially many suboptimal steps with high probability in the described settings.The applications include factored-MDP rewards and action-outcome probabilities in Stochastic STRIPS and Object Oriented MDPs.Source: §1 · p. 1
• The paper applies KWIK linear regression to compact RL model components not previously shown to be efficiently learnable in the RL setting.The named components are factored-MDP reward functions and transition probabilities in Stochastic STRIPS and Object Oriented MDPs.Source: §1 · p. 1
• The paper also discusses combining KWIK linear regression with other KWIK learners to learn more parameters of compact representations.The authors report experiments on learning factored-MDP transition and reward functions together.Source: §1 · p. 2

2 KWIK Linear Regression

• KWIK learners predict accurately when they know an input and otherwise abstain, bounding total abstentions; the earlier linear-regression algorithm used certainty measures based on sample coverage and suitability.Source: §2 · p. 2

2.1 A New KWIK Linear Regression Algorithm

• The new algorithm regularizes the regression system and uses prediction distortion as a confidence signal, abstaining when uncertainty exceeds a threshold.It updates sufficient quantities incrementally rather than storing growing sample matrices and vectors.Source: §2.1 · p. 2
• The method improves sample complexity by Θ(n^2/log^2 n) over Strehl & Littman’s KWIK online linear regression and requires Θ(n^2) operations per timestep instead of O(tn^2).With probability at least 1−δ, predictions made satisfy |ŷ_t−f(x_t)|≤ε.Source: §2.1 · p. 3

2.2 Proof sketch of Theorem 2.1

• The proof bounds large-uncertainty queries by tracking decreases in trace(Q_t) and controls noise in accepted predictions with Azuma’s inequality.Source: §2.2 · p. 3

3 Application 1: Learning Rewards in a Factored-State MDP

• The reward model is a sum of J local-scope functions, and when J > 1, learning their unknown values from observed reward sums requires online linear regression.The indicator encoding has Nr parameters, with Nr ≤ J|A|nnf.Source: §3 · p. 4
• Before this work, algorithms could learn factored-MDP transition probabilities and dependency structure, but not reward functions.Source: §3 · p. 4
• Optimistic initialization assigns unknown rewards a sufficiently high R0, while known states receive near-accurate predictions under KWIK guarantees, yielding the first efficient PAC-compact-MDP algorithm for this task.The approach combines a KWIK model learner with R-max-style exploration.Source: §3 · p. 4

3.1 Experiments

• In Stocks(3,2), Algorithms 1 and 2 were not significantly different, while Algorithm 3 and linear regression without exploration learned more slowly, the flat learner took far longer, and epsilon-greedy failed to explore.The comparison ran 20 times for 250 steps, updating models every 5 steps.Source: Figure 1 · p. 4, §3.1 · p. 4

4 Learning Transition Probabilities

• The transition-probability learner assumes known action effects, preconditions, and reward structure, then learns probabilities online using KWIK-LR on observed equivalence classes.An observed class may contain several effects, so its probability corresponds to the sum of their probabilities.Source: §4 · p. 5
• When effects are ambiguous, counting cannot determine which effect occurred, whereas KWIK-LR can learn class probabilities and preserve the PAC-compact-MDP guarantee for online exploration.Source: §4 · p. 5
• Planning uses modified value iteration that assigns remaining probability mass to the highest-value unknown effect, making the model optimistic; planning in the flat state space can require exponential time.Source: §4 · p. 5

4.1 Application 2: Stochastic STRIPS

• Across the Stochastic STRIPS experiment, Algorithm 3 learned much faster than Partition by sharing information between equivalence partitions.The comparison averaged 1,000 runs with randomized initial states; both learners received the same initial states and known preconditions and effects.Source: Figure 2 · p. 6, §4.1 · p. 6

4.2 Application 3: Stochastic Object Oriented RL

• Stochastic OOMDP results assume the conditions and possible effects are known in advance, with methods for relaxing those assumptions deferred to later sections.Source: §4.2 · p. 6
• In the Maze-domain experiment, KWIK-RL learned much faster than Partition by sharing information between equivalence partitions.Source: Figure 4 · p. 7, §4.2 · p. 7

5 Extensions

• The extensions outline combining KWIK learners to learn full fMDPs and larger portions of STRIPS and OOMDP models, with empirical support for the fMDP case.For STRIPS and OOMDPs, existing Noisy-Union adaptations can learn preconditions or conditional effects when their size is bounded by a known constant.Source: §5 · p. 7, §5.1 · p. 7

5.1 Combining with Other KWIK Learners

• For fMDPs, parallel reward learning and Noisy-Union learn transition structure, transition probabilities, and rewards, using only the parent-count bound and reward-function structure as prior knowledge.In Stocks experiments, the combined method learned all three quantities with small overhead relative to Noisy-Union given rewards a priori.Source: §5.1 · p. 7

5.2 Future Work: Learning Effects

• Because effect-learning variations require possible effects as input and stochastic effect learning is NP-hard, the paper proposes sparsifying probabilities across candidate effects as a heuristic extension.The proposed optimization constrains the number of nonzero probabilities and can be solved by linear programming; comparisons with other heuristic solutions remain future work.Source: §5.2 · pp. 7–8

• Earlier model-based RL work focused on linear transition functions in continuous spaces, often lacking guarantees or restricting noise and reward structure; this paper improves KWIK-LR and applies it beyond linear transitions.The authors identify expanded empirical and theoretical studies of their extensions as future work.Source: §6 · p. 8