(This is an attempt to reformulate this question more concisely.)ContextYou are a Jedi master who wants to prepare a training program (online-algorithm) for his apprentice, Luke. Luke needs to practice several (10-20) abilities. You can train Luke by preparing challenges, each connected to one ability.The outcome of each challenge is binary: Luke succeeds (1) or Luke fails (0). If Luke fails a challenge in an ability, you give him a lecture that you can assume will improve his chance of succeeding in next challenge in this ability.You have a limited number (~50) of challenges to use before Luke has to take a test. However, if Luke fails at some challenge during practice you receive extra challenges. The goal of your training program is to maximize the outcome of the test. The test is a set of (about 20-25) challenges uniformly distributed between abilities.Problem definitionConsider a problem of probing a set $P = \{p_0,...,p_n\}$ of $N$ independent processes which resemble human learning (practice makes perfect). At each time the program chooses one process $i$ to probe, denoted by the action $U(t)$, and receives an information of the current, binary state $S_i(t)$ of that process. The probability of $S_i(t)$ = 1 is defined by $$ p(S_i(t) = 1) = g_i(c_i(t))$$ Where $g_i$ is a non-decreasing function and $c_i(t)$ describes how many times proces $p_i$ was probed so far. We can assume $g_i$ ressembles the learning curve, but each $g_i$ can have an arbitraty offset at $t_0$ ie: Knowing that the amount of remaining probing action is given by$$h(t+1) = \begin{cases}            h(t)-1\,, &\text{ if $i \in U(t)$ and $S_i(t) = 1$;} \\            h(t)-1+f(h(t))\,, &\text{ otherwise,}\end{cases}$$where the function $f$ is one of the input variables — propose a probing policy which maximizes a testing function $q$ that will evaluate the state of all processes when there are no more remaining probes, namely:$$q(t_{stop}) = \sum_{i = 0}^{N}S_i(t_{stop}),$$where $t_{stop}$ is such that $h(t_{stop}) = 0$.My ideas of approaching this problemWe can try to model this problem in at least two ways:As a special case of Non-Bayesian Binary Restless Multi-armed Bandit (RMBA) with Non-Identical Arms (some reading one, two, three) meaning :Restless - reward probability evolves over time Non-Bayesian - underlying Markov transitions are not knownNon-Identical Arms - each arm is an independent Markov process We would assume that the algorithm receives a reward each time it probes a process that will return 0 (Luke fails a challenge). I would start by adopting some policy similar to $\epsilon$-greedy.As a case for Reinforcement Learning .I'm just starting to familiarize myself with these areas of research so I can't provide any insight here, although according to my initial reading it seems very promising. I will update the question once I learn anything meaningful.QuestionWhat would you recommend as the best references for this problem, or closely related problems? I'm interested primarily in approaches which are not just theoretically feasible, but which would be effective in practise.Can you suggest a policy that would be effective with these constraints? I am especially interested in good ways to update the belief vector.
Ultimate Jedi Challenge - Multiarmed Bandit / Reinforcment Learning / advanced AI problem
ds.algorithms;reference request;machine learning;ai.artificial intel;genetic algorithms