# Computer Adaptive Testing Using Upper-Confidence Bound Algorithm for Formative Assessment
## Materials and Methods  
### Modelling Assessment as UCB Problem  
When tutoring, a teacher will often engage in a dialogue with a student. The teacher may ask the student a series of formative questions in order to diagnose the gaps in student's knowledge. Assume the material consists of two topics, and the teacher asked 5 questions on each topic. The knowledge about first topic appears to be in a worse shape, two incorrect answers, than the knowledge on the second topic, one incorrect answer (see Table 1). If there is time for five more questions before proceeding with didactic instruction, the teacher must face the dilemma of which topic should they explore with further questions? If the two incorrect answers to questions on first topic are attributable to bad luck due to small sample size, should the teacher explore first or second topic? What if there are more than two topics? The family of bandit algorithms are designed to cope with uncertainty by balancing exploration and exploitation [40]. However, when applied to formative assessment the exploitation component is non obvious, as ultimately the goal is to explore the knowledge of the student. The algorithm should probe and explore the different topics and engage in focused questioning, exploiting those which are possibly in most need of instruction. This presents an opaque bandit problem where a unique answer, reward, is observed at each round, in contrast with the transparent one where all rewards are observed [34]. Thus, in context of assessment, a sequential allocation problem is obtained when the assessor has to choose from many questions from multiple topics, bandits, and has to repeatedly choose a topic to explore, which bandit arm to pull. When choosing next question to ask the decision should depend on the history of already known answers. Then a policy is the mapping from the individual history of the student to actions (questions to be asked of the student). Suppose student's knowledge on number of topics \(T=\{1,\,2,\,\ldots,\,k\}\). The reward in case of a multiple-choice quiz with either correct on incorrect answer to each question \(X_{r}\in\{0,1\}\) is binary valued. Each topic corresponds to an unknown probability distribution. There exists a vector \(\mu\in[0,1]^{k}\) such that the probability that \(X_{r}=0\) given the algorithm chose topic \(T_{r}=t\) is \(\mu_{t}\). This kind of environment is called a stochastic Bernoulli bandit. If the mean vector associated with the environment was known, the optimal policy is to always choose a question on one topic \(t^{*}=\text{argmin}_{t\in T}\mu_{t}\). This will result in the exploration of the weakest area of student's knowledge, so as to aid in the further instruction. The regret over the \(n\) questions is  
\[R_{n}=E\left[\sum\
olimits_{t=1}^{n}X_{r}\right]-n\min_{t\in T}\mu_{t} \tag{1}\]  
where the expectation \(E\) is with respect to stochastic environment and policy. However, in practical setting, the number of questions on one topic is usually rather limited due to the scope of the curriculum \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Question** & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** \\ \hline Topic 1 & + & & + & – & & + & & & & – \\ Topic 2 & + & & & + & & + & – & + & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Rudimentary two topic quiz model. and the question pool. As is the length, or the horizon, of the quiz. Thus the value of calculated this way regret is of little practical value. The main challenge of the task is finding the weakest topic of a student. To do so the algorithm must explore different topics and exploit particular topic to obtain more accurate estimation of the student's level of knowledge on that subject. This basic exploration-exploitation dilemma is the key to obtaining a good strategy. A heuristic principle for dealing with this issue chosen in this paper is optimism in face of uncertainty and an algorithm which operates on this principle Upper-Confidence Bound (UCB).