(This is an attempt to reformulate this question more concisely.)


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 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 definition

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, 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: $g_i$ offset on the learning curve at time $t_0$ 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 problem

We can try to model this problem in at least two ways:

  1. 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 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.
  2. 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.


What 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.

  • 4
    $\begingroup$ As a general issue, you should understand that what you need is not a “problem definition in technical terms,” but a precise definition. Of course, to state a precise definition, you usually need some technical terms, but using technical terms is not a goal. $\endgroup$ Aug 15 '12 at 19:19
  • 4
    $\begingroup$ As a specific issue, specifying that S_i(t) is binary does not define what the value of S_i(t) is: it only says that it is either 0 or 1. If it is chosen randomly, you have to specify the probability distribution. If it is chosen adversarially, you have to specify what the constraint on the choice is. With the current formulation, I cannot rule out the possibility that no matter what I do, I receive S_1(t_stop) = … = S_n(t_stop) = 0, completely unrelated to the values of S_i(t) for t<t_stop. $\endgroup$ Aug 15 '12 at 19:19
  • 3
    $\begingroup$ @Johnny, I think your title is more like keywords and doesn't state your question. The general advice is to make your question the title. I suggest using the tags in place of the title for listing keywords. (Or you can list them inside the question.) $\endgroup$
    – Kaveh
    Aug 15 '12 at 23:55
  • 3
    $\begingroup$ When revising the question, please also check the following page, which contains useful advice from many people on asking questions about how to model something: meta.cstheory.stackexchange.com/questions/514/…. Such questions can become great questions which connect theoretical computer science to other fields. But in its current form, I am afraid that your question is an example of the bad scenario which Scott described: if the only answer to your question you could reasonably expect from a TCS expert is "I dunno," why are you asking it here? :) $\endgroup$ Aug 16 '12 at 12:10
  • 2
    $\begingroup$ I suppose, as a first approximation, $S_i(t)$ is a bernoulli random variable s.t. the probability of getting one is a function of the number "probes". I.e. we can think of $p_i:\mathbb{N} \rightarrow [0, 1]$, which is a decreasing function, and when $i$ has been probed $x = x_i(t)$ times up to step $t$, $S_i(t) = 1$ w.p. $p_i(x)$. Is this fair? $\endgroup$ Aug 17 '12 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.