- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper studies RL for high-dimensional MDPs, in which explicit reward is not present. It claims to develop accelerated training using tools, more specifically the uncertainty principle from harmonic analysis. It provides theoretical and empirical results in support of its claims. More specifically, an algorithm is proposed that randomly removes some components. This is supposed to yield randomization, which is supposed to convert to a better sample complexity and robust policy. Main results are Propositions 3.3 and 3.5.
Critical strengths
This work does not seem to be strong. The theoretical results do not support the claims. The only silver lining seems to be that an attaempt is made to borrow tools from distant fields. The experimental results seem to show that the method is effective.
Critical weaknesses
Parts of the paper are quite wrong. Generally, the paper is not well-written and cryptic. I am highlighting some of the issues below:
-
" a fundamental assumption persists in reinforcement learning: that the agent has direct access to the reward function of the MDP," --> not really. As long as some form of "noisy" and "partial information" about the rewards is revealed to the agent (this could be after some delay too), efficient learning can occur.
-
" from bee foraging to human decision making, i"--> in all these cases there is some reward which is observed by the agent (this could be function also of the noise, in addition to state and actions).
-
Explain the equation on Line 93. Additionally give some reference, or derive it. ("In settings where the state or action space have high-dimensional representations, the state-action value function is approximated via a deep neural network......").
-
Several important works which use Linear programming approach to solve MDPs/RL, are missing.
-
what exactly is meany by instability in the context of RL. E.g. explain in one paragrapg, or define this explicitly near "In this line of research some studies tried to further identify these instabilities".
-
Definition 3.1 is not clear. Is the value function time-dependent? Is it episodic MDP (what is H??) ?
-
The logic behind algorithm 1 is not clear. Take the simple case of 2 armed bandit. Algorithm 1 in this case eseentially sets to 0 the reward estimate of the arm that was selected in the current round. Since the estimate of the oher arm will be positive (with high probability), this essentially reduces to \epsilon_t exploration policy.
-
Explain the stable basis assumption in more detail, and show what does it mean for the simplest of all settings (N-armed bandit or 2-armed bandit). It seems very restrictive.
-
The results (Proposition 3.3, 3.5) do not say anything about the sample complexity, or regret , or the convergence rates. Hence, the claimed gains are not really proved.
-
The experimental section is rather limited. It does not compare with the state-of-the-art policies.
Questions for authors
-
Please explain the stable basis assumption in more detail, and show what does it mean for the simplest of all settings (N-armed bandit or 2-armed bandit). It seems very restrictive. Canyou please workout the calculations and show that this could hold in this case?
-
Please show the working of the proposed algorithm for the finite-arms bandit case. If my understanding is correct, it reduces to the \epsilon exploration strategy.
-
The main results (Proposition 3.3 amd 3.5) do not prove sample complexity or regret bounds. Hence, how does one judge the efficiency of the proposed algorithm?
2 comments
Response read
I thank the authors for their effort in responding to my concerns. However, these are not satisfactory, and did not address my concerns. Though this does improve the standing of the paper, its not enough in order for the score to be changed. Consequently, I would stick to my score.
The stable basis assumption is an assumption about properties of the space of features used by the value function. In particular, it only requires that the value function and state-action feature vectors are spread out with respect to the stable basis, as this is a standard feature with the Fourier basis or other Harmonic analytic bases. We now provide a fully worked out example for n-armed bandits.
In the n-armed bandit setting, let ϕk∈Rn denote the feature vector corresponding to the k-th arm, and let θ∈Rn be the parameter vector of the optimal Q function. Let v1,…,vn be an orthonormal basis. Then we can write each feature vector for the k-th arm with coefficients cik from this basis i.e. ϕk=∑icikvi. We can similarly write the optimal parameter vector θ with coefficients bik in this basis i.e. θ=∑ibikvi. Because the vi basis is orthonormal we have that the dot product which defines the Q-value of the k-th arm is equal to Q(k)=ϕk⋅θ=∑icikbik. In this case, the vi form a stable basis if each term contributes approximately equally to the above sum. That is it means that cikbik≈ϵ1/nQ(k) where ≈ϵ means that the two sides of the equation are within ϵ of each other.
For a simple example, let vi be the Hadamard basis in Rn. This is an orthornormal basis where every coordinate of each vi is either 1/n or −1/n. Next, let the feature vectors for arm k be the Euclidean standard basis vectors ϕk=ek. Similarly, let θ be an s-sparse vector which has only s<n non-zero coordinates, each of which is equal to 1. Hence, Q(k)=1 for s of the arms, and Q(k)=0 for the rest. Further, the bounded coordinates of the Hadamard basis guarantee that ∣cik∣≤1/n and ∣bik∣≤ns. Hence, for each term we have ∣cikbik∣<s/n. If we let ϵ=s/n then our condition of a stable basis is satisfied both when Q(k)=1 (because 1/n is within ϵ of s/n) and when Q(k)=0 (because 1/n⋅0=0 is within ϵ of s/n).
This understanding is not correct, the definition of a stable basis depends on the feature representation chosen for each state-action pair. For finite-armed bandits, the working of the algorithm is completely dependent on the feature representation, and does not reduce to ϵ-greedy exploration. Take the example described above for instance. In that case, the algorithm adds noise by dropping a single Hadamard basis vector. Each time an arm k is selected, and we update the estimated value function, the estimated value of Q(k) gets closer to the true value. Now because the Hadamard basis is a stable basis, we know that the true Q-function changes very little when we drop a single Hadamard basis vector. Thus, the noise added to Q(k) decreases as arm k is visited more often and the value of Q(k) gets more accurate. That is: the value function exploration noise is automatically decreased for arms that are closer to optimal, while it remains larger for arms that have not yet been accurately estimated.
The goal of this paper is to introduce a theoretically grounded learning paradigm that could be immediately applied to more general settings. Our method indeed has a strong theoretical motivation which suggests using the Fourier basis as a stable basis, and our empirical analysis shows that our algorithm learns substantially high performing policies in high-dimensional MDPs with neural-network function approximators.
Yes, Definition 3.1 is in the setting of an episodic, finite horizon MDP with horizon H. This setting was chosen as it is the same as the prior theoretical work on value function randomization. There, purely for generality, the value function is allowed to be time dependent. Of course, this analysis can equally well be specialized to the time-invariant value function setting.