I have a strategy with at most $50$ tries and $22449/1000=22.449$ expected tries.
$$
\begin{align}
443, 796, 869, 101, 230, 577, 314, 022, 965, 656, \\
588, 757, 875, 213, 140, 331, 689, 998, 404, 410, \\
134, 303, 241, 886, 555, 667, 779, 421, 599, 000, \\
432, 202, 897, 768, 044, 033, 695, 342, 011, 976, \\
678, 959, 112, 858, 987, 224, 123, 320, 566, 785\phantom{,}
\end{align}
$$
This was obtained by starting from the unordered set of these words (given by a covering code) and then ordering them using a greedy computer search; more details below.
First, I'll get some ideas by considering another problem, optimizing the number of tries needed for the worst case, which has a known solution for this case. A covering code $C$ with alphabet size $q=10$, length $n=3$, and covering radius $R=1$ is a set of $3$-tuples (called words) of length $3$ over $\{0,1,\dots,9\}$ such that every possible $3$-tuple differs from one in $C$ in at most one position. This is exactly what we need.
The minimal size with these parameters is $50$ [1]. It contains these words:
$$
\begin{array}{|ccccc|}
\hline
000 & 011 & 022 & 033 & 044 \\
101 & 112 & 123 & 134 & 140 \\
202 & 213 & 224 & 230 & 241 \\
303 & 314 & 320 & 331 & 342 \\
404 & 410 & 421 & 432 & 443 \\
\hline
555 & 566 & 577 & 588 & 599 \\
656 & 667 & 678 & 689 & 695 \\
757 & 768 & 779 & 785 & 796 \\
858 & 869 & 875 & 886 & 897 \\
959 & 965 & 976 & 987 & 998 \\
\hline
\end{array}
$$
For any two columns, the upper half contains a word for all $25$ pairs of symbols in $\{0,1,2,3,4\}$ that can occur there, and the lower half contains all $25$ pairs of symbols in $\{5,6,7,8,9\}$ that can occur there. The correct combination has to contain at least two symbols from either set, so it is opened by entering one of these words.
[1] Some sources refer to "J. G. Kalbfleisch and R. G. Stanton, A combinatorial theorem of matching, J. London Math. Soc. (1), 44 (1969), 60–64; and (2), 1 (1969), 398", but I can't find the paper. However, the value is listed in the fourth PDF listed at the top of this page by Gerzson Kéri.
Now back to the original problem, optimizing the expected number of tries required. My idea is to try to take these words and optimize the order somehow. This of course doesn't guarantee that we have an optimal solution.
I tried a greedy random approach: Choose words one by one. At each step, for each possible new word $c$, find the number of previously uncovered words that would be covered by $c$. Then among the ones that cover the most, choose one by random. After some time, the best that I could find was the order given at the top of this answer, with $22449/1000$ as the expected number.
The thief is able to determine the digits, but not their multiplicities.
Let $m$ be the number of distinct digits, with $m\le n\le t$.
Without loss of generality, we can assume the digits are $1,...,m$.
Let $P(m,n)$ be the number of $n$-tuples with each component in $\{1,...,m\}$ such that each of the values$\;1,...,m\;$occurs at least once.
For example, for $n=4$, we have
$$P(1,4)=1,\;\;\;\;P(2,4)=14,\;\;\;\;P(3,4)=36,\;\;\;\;P(4,4)=24$$
For each positive integer $n$, let $f(n)$ be the least positive integer $m\le n$ such that $P(m,n)$ is as large as possible.
For $1\le n \le 20$, here are the values of $f(n)$, computed via Maple . . .
$$
\begin{array}
{
|c
|c|c|c|c|c|c|c|c|c|c|
|c|c|c|c|c|c|c|c|c|c|
}
\hline
n
& 1
& 2
& 3
& 4
& 5
& 6
& 7
& 8
& 9
& 10
& 11
& 12
& 13
& 14
& 15
& 16
& 17
& 18
& 19
& 20
\\
\hline
f(n)
&1
&2
&2
&3
&4
&5
&5
&6
&7
&8
&8
&9
&10
&10
&11
&12
&13
&13
&14
&15
\\
\hline
\end{array}
$$
For example, the result $f(20)=15$ means that for $n=20$, an optimal strategy is to choose $a_1,...,a_5$ independently and uniformly at random from $\{1,...,15\}$, and then let the combination be a random reordering of the $20$-tuple$\;(1,...,15,a_1,...,a_5)$.
From the data, it appears that
- $f(n)$ is approximately ${\large{\frac{3}{4}}}n$.$\\[4pt]$
- If $n$ is a multiple of $4$, $f(n)$ is exactly ${\large{\frac{3}{4}}}n$.
Best Answer
If repetition of digits is not allowed, then @anorton's answer does it. If repeated digits are allowed, then imagine 9 bars: $$|||||||||$$ Between successive bars you have areas that represent a digit: $$0|1|2|3|4|5|6|7|8|9$$ You need to put the four digits from the combination into these 10 areas. For example, 0-1-2-3 can be represented as: $$*|*|*|*||||||$$ and 1-2-2-9 as: $$|*|**|||||||*$$ Any arrangement of 9 bars and 4 stars provides you with a unique combination (since order is ignored). Thus with 13 things to set as either a star or a bar, and the requirement that four of them must be stars, there are $\binom{13}{4}=715$ possibilities.