1. Ultimate Jedi Challange - the core
Background story
You 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 fail (0) 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 failes (0) 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 definition in technical terms
Consider 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 state $S_i(t)$ of that process. Knowing that the amount of remaining probing action is given by: $$h(t+1) = \left\{ \begin{array}{rl} h(t)-1 &\mbox{ if $i \in U(t), S_i(t) = 1$} \\ h(t)-1+f(h(t)) &\mbox{ otherwise} \end{array} \right. $$
where the function $f$ is one of the input variables, propose a probing policy maximizing 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}), \quad t_{stop} : h(t_{stop}) = 0$$
My ideas of approaching this problem
As a special case of Non-Bayesian Binary Restless Multi-armed Bandit (RMBA) with Non-Identical Arms (some reading one, [two][3], [three][4]) meaning :
- Restless - reward probability evolves over time
- Non-Bayesian - underlying Markov transitions are not known
- Non-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.
How can YOU help Luke to become an awesome Jedi?
- By helping to assemble a list of similar problems/areas to explore.
- By providing references to solutions of similar problems.
- By suggesting algorithms/policies or their parts
- By throwing ideas on how to:
- improve the definition of the problem
- model how Luke might be learning - adjust the belief vector (our prediction of the states of the processes/abilities) after each probe
- By up-voting this question so more people can see it and help
- By providing references to similar cases of RMBA (please do not list purely theoretical papers with algorithms that have only theoretical value of proving asymptotic regret but are not suited for implementation)
- By suggesting RMBA algorithms that could perform well in this application
- By providing references or good (concise) introductory materials for someone to understand RL (fast!)
- By suggesting areas of RL that will come in handy
- By suggesting RL algorithms that will help to solve this problem
2. A list of sub-problems
- in progress...
Thank you in advance and may the force be with you.
