We study the $K$-armed contextual dueling bandit problem, a sequential\ndecision making setting in which the learner uses contextual information to\nmake two decisions, but only observes \\emph{preference-based feedback}\nsuggesting that one decision was better than the other. We focus on the regret\nminimization problem under realizability, where the feedback is generated by a\npairwise preference matrix that is well-specified by a given function class\n$\\mathcal F$. We provide a new algorithm that achieves the optimal regret rate\nfor a new notion of best response regret, which is a strictly stronger\nperformance measure than those considered in prior works. The algorithm is also\ncomputationally efficient, running in polynomial time assuming access to an\nonline oracle for square loss regression over $\\mathcal F$. This resolves an\nopen problem of Dud\\'ik et al. [2015] on oracle efficient, regret-optimal\nalgorithms for contextual dueling bandits.\n