It is known that the competitive ratio of online algorithms for this problem depends on the deficiency $d$ of the graph, which is the minimum number of edges that must be added to make the graph Eulerian. We present the first deterministic online exploration algorithm whose competitive ratio is polynomial in $d$ (it is O(d^8)).