  We investigate the following version of the well-known R\'enyi-Ulam game. Two
players - the Questioner and the Responder - play against each other. The
Responder thinks of a number from the set $\{1,\ldots,n\}$ and the Questioner
has to find this number. To do this, he can ask if the sought number is an
element of a subset of $\{1,\ldots,n\}$ with at most $k$ elements. The
Responder answers with YES or NO immediately, but during the game he may lie at
most $\ell$ times. The minimal number of queries needed for the Questioner to
find the unknown element in the worst case is denoted by $RU_\ell^k(n)$. First,
we develop a highly effective tool, which we call Convexity Lemma. Using this,
we give a general lower bound of $RU_\ell^k(n)$ with an error at most
$2\ell+1$, and we also give its exact value when $n$ is sufficiently large with
respect to $k$. With this, we manage to improve and generalize the results
obtained by Meng, Lin and Yang in a 2013 paper about the case $\ell=1$.
