<p>Not a solution to your question, just some general thoughts that maybe are relevant:</p>

<ul>
<li>One of the biggest obstacles to apply Reinforcement Learning in "real world" problems is the astoundingly large amount of data/experience required to achieve acceptable results. For example, <a href="https://openai.com/blog/openai-five/" rel="nofollow noreferrer">OpenAI in Dota 2</a> game colletected the experience equivalent to 900 years per day. In the <a href="https://www.nature.com/articles/nature14236" rel="nofollow noreferrer">original Deep Q-network paper</a>, in order to achieve a performance close to a typicial human, it was required hundres of millions of game frames, depending on the specific game. In <a href="https://arxiv.org/abs/1707.02286" rel="nofollow noreferrer">other benchmarks</a> where the input are not raw pixels, such as MuJoCo, the situation isn't a lot better. So, if you don't have a simulator that can generate samples (state, action, next state, reward) cheaply, maybe RL is not a good choice. On the other hand, if you have a ground-truth model, maybe other approaches can easily outperform RL, such as Monte Carlo Tree Search (e.g., <a href="https://papers.nips.cc/paper/5421-deep-learning-for-real-time-atari-game-play-using-offline-monte-carlo-tree-search-planning" rel="nofollow noreferrer">Deep Learning for Real-Time Atari Game Play Using Offline Monte-Carlo Tree Search Planning</a> or <a href="https://arxiv.org/abs/1803.07055" rel="nofollow noreferrer">Simple random search provides a competitive approach to reinforcement learning</a>). All these ideas a much more are discussed in <a href="https://www.alexirpan.com/2018/02/14/rl-hard.html" rel="nofollow noreferrer">this great blog post</a>.</li>
<li>The previous point is specially true for deep RL. The fact of approximatting value functions or policies using a deep neural network with millions of parameters usually implies that you'll need a huge quantity of data, or experience.</li>
</ul>

<p>And regarding to your specific question:</p>

<ul>
<li>In the comments, I've asked a few questions about the specific features of your problem. I was trying to figure out if you really need RL to solve the problem, since it's not the easiest technique to apply. On the other hand, if you really need RL, it's not clear if you should use a deep neural network as approximator or you can use a shallow model (e.g., random trees). However, these questions an other potential optimizations require more domain knowledge. Here, it seems you are not able to share the domain of the problem, which could be due a numerous reasons and I perfectly understand.</li>
<li>You have estimated the number of required episodes to solve the problem based on some empirical studies using a smaller version of size 20*10 matrix. Just a caution note: due to the <a href="https://en.wikipedia.org/wiki/Curse_of_dimensionality" rel="nofollow noreferrer">curse of the dimensionality</a>, the complexity of the problem (or the experience needed) could grow exponentially when the state space dimensionalty grows, although maybe it is not your case.</li>
</ul>

<p>That said, I'm looking forward to see an answer that really helps you to solve your problem.</p>
Optimize deep Q network with long episode
<p>I am working on a problem for which we aim to solve with deep Q learning. However, the problem is that training just takes too long for each episode, roughly 83 hours. We are envisioning to solve the problem within, say, 100 episode.</p>

<p>So we are gradually learning a matrix (100 * 10), and within each episode, we need to perform 100*10 iterations of certain operations. Basically we select a candidate from a pool of 1000 candidates, put this candidate in the matrix, and compute a reward function by feeding the whole matrix as the input:</p>

<p><a href="https://i.stack.imgur.com/Fklf7.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/Fklf7.jpg" alt="enter image description here"></a></p>

<p>The central hurdle is that the reward function computation at each step is costly, roughly 2 minutes, and each time we update one entry in the matrix. </p>

<p>All the elements in the matrix depend on each other in the long term, so the whole procedure seems not suitable for some "distributed" system, if I understood correctly. </p>

<p>Could anyone shed some lights on how we look at the potential optimization opportunities here? Like some extra engineering efforts or so? Any suggestion and comments would be appreciated very much. Thanks.</p>

<p>======================= update of some definitions =================</p>

<p><strong>0. initial stage:</strong></p>

<ul>
<li>a 100 * 10 matrix, with every element as empty</li>
</ul>

<p><strong>1. action space:</strong></p>

<ul>
<li>each step I will select one element from a candidate pool of 1000 elements. Then insert the element into the matrix one by one.</li>
</ul>

<p><strong>2. environment:</strong></p>

<ul>
<li><p>each step I will have an updated matrix to learn.</p></li>
<li><p>An oracle function <strong>F</strong> returns a quantitative value range from 5000 ~ 30000, the higher the better (roughly one computation of <strong>F</strong> takes 120 seconds). </p>

<p>This function <strong>F</strong> takes the matrix as the input and perform a very costly computation, and it returns a quantitative value to indicate the quality of the synthesized matrix so far.</p>

<p>This function is essentially used to measure some performance of system, so it do takes a while to compute a reward value at each step.</p></li>
</ul>

<p><strong>3. episode:</strong></p>

<p>By saying "we are envisioning to solve it within 100 episodes", that's just an empirical estimation. But it shouldn't be less than 100 episode, at least. </p>

<p><strong>4. constraints</strong></p>

<p>Ideally, like I mentioned, "All the elements in the matrix depend on each other in the long term", and that's why the reward function <strong>F</strong> computes the reward by taking the whole matrix as the input rather than the latest selected element. </p>

<p>Indeed by appending more and more elements in the matrix, the reward could increase, or it could decrease as well.</p>

<p><strong>5. goal</strong></p>

<p>The synthesized matrix should let the oracle function <strong>F</strong> returns a value greater than 25000. Whenever it reaches this goal, I will terminate the learning step.</p>