Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?
The recent survey Two-Way Finite Automata: Old and Recent Results by Pighizzini states in the introduction:
The costs of the simulations of 1NFAs by 2DFAs and of 2NFAs by 2DFAs are still unknown. The problem of stating them was raised in 1978 by Sakoda and Sipser , with the conjecture that they are not polynomial. In spite of all attempts to solve it, this problem is still open.
As explained in section 6 of that survey, the question relates to the L vs. NL problem, so it may be not surprising that the problem remains unresolved. Concerning lower bounds, section 5 states the following:
The question 1NFAs versus 2DFAs has been solved in the unary case in  by showing that the tight cost is polynomial, more precisely Θ(n²). This gives also the best known lower bound for the general case.
EDIT (2017/09/18): Concerning upper bounds, the PhD thesis of Christos Kapoutsis provides a valuable source (thanks goes to András Salamon for his valuable comment below). Section 2 of the PhD thesis mentions the following:
Second, it is even conjectured that this alleged exponential difference in size between 1NFAs and 2DFAs covers the entire gap from n to $2^n - 1$ which is known to exist between 1NFAs and 1DFAs ² In other words, according to this conjecture, a 2DFA trying to simulate a 1NFA may as well drop its bidirectionality, since it is going to be totally useless: its optimal strategy is going to be the well-known brute-force one-way deterministic simulation . So, once more we have an instance of the claim that the obvious, highly inefficient solution is also the optimal one. [...]
² As with 2DFAS (cf. Footnote 1 on page 8), a 1DFA is allowed to reject by just hanging anywhere along its input. Without this freedom, the gap would actually be from $n$ to $2^n$.
Pighizzini, Giovanni: Two-Way Finite Automata: Old and Recent Results. In: E. Formenti (Ed.), Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, AUTOMATA & JAC 2012, pp.3-20.
Kapoutsis, Christos: Algorithms and lower bounds in finite automata size complexity. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA 2006.