Value Generalization Pattern Analysis
Representation Learning, Advanced Theory & Miscellaneous DS practice problem on Onlearn.
Difficulty: medium.
Topics: Value Generalization Pattern Analysis, Bellman Residual Minimization, Rademacher Complexity, Mutual Information Bottleneck, Mercer Kernel Mapping, Universal Approximation Theorem, Reinforcement Learning, Statistical Learning Theory, Information Theory, Functional Analysis, Computational Complexity, Temporal Difference Learning, PAC Learning Framework, Representation Entropy, Reproducing Kernel Hilbert Spaces, Approximation Theory.
In reinforcement learning with function approximation, updating the value estimate for one state inevitably affects the estimates for other states. This phenomenon, known as value generalization, is fundamental to understanding both the benefits and pitfalls of function approximation in RL. Implement a function value generalization analysis that analyzes how a single semi gradient TD update at a target state propagates value changes across all states through a linear function approximation. Given: features: a numpy array of shape (num states, feature dim) where each row is the feature vector for a state. weights: a numpy array of shape (feature dim,) representing the current weight vector of the linear value function. target state: an integer index of the state where the TD update is applied. td error: a float representing the temporal difference error observed at the target state. alpha: a float representing the learning rate. The linear value function is defined as V(s) = features[s] dot weights. A semi gradient TD update modifies the weight vector based on the TD error and the feature vector of the target state. Your function should return a dictionary with: 'values before': a list of floats, the estimated value of each state before the update, rounded to 4 decimal places. 'values after': a list of floats, the estimated value of each state after the update, rounded to 4 decimal places. 'value changes': a list of floats, the change in value for each state, rounded to 4 decimal places. 'generalization ratios': a list of floats, for each state the ratio of its value change to the target state's value change. If the target state's value change is zero, all ratios should be 0.0. Rounded to 4 decimal places.